1 概述

物流配送路徑最短問題是典型的旅行商（Traveling Salesman Problem，TSP）問題。車輛從配送中心出發(fā)，將車上貨物分別送到本轄區(qū)內(nèi)的其它分發(fā)點（簡稱節(jié)點）1,2,3,…,n，車輛在一次配送任務(wù)中，只經(jīng)過各節(jié)點一次。由于交通管制和道路方面的原因，可能存在各節(jié)點間并不完全互通，個別節(jié)點間可能還存在單向性通行，如圖1物流配送路線示意圖。

對于這樣一個典型的TSP問題，隨著節(jié)點數(shù)目的增加，其可能的配送路線數(shù)目與節(jié)點數(shù)目n是成指數(shù)型增長的，是一個NP難題，所以很難精確的求出其最優(yōu)解，因此尋找有效的近似求解算法就具有重要的現(xiàn)實意義。遺傳算法是一種仿生算法，核心思想起源于對生物進化過程的認(rèn)識。通過模仿生物的進化，利用達爾文的進化論和孟德爾遺傳變異思想對研究問題進行數(shù)學(xué)抽象和建模。

遺傳算法是通過模仿生物的繁殖、基因變異、物種間競爭和自然選擇對研究問題采取適當(dāng)?shù)挠嬎悴呗?，最終得到研究問題的滿意解。遺傳算法只利用研究問題的目標(biāo)滿意度評價信息，是一種多條并行的隨機搜索優(yōu)化方法，適用于大規(guī)模、高度非線性以及無解析表達式的問題，有很強的通用性[1]。物流配送的路線最短選擇問題采用該方法非常合適。

圖1 物流配送路線示意圖

2 數(shù)學(xué)建模及求解方法

（1）路線信息。對于從物流配送中心出發(fā)，將貨物分別投送至各分發(fā)點的配送路線之間的關(guān)系，可以用表1物流配送節(jié)點信息表進行表達（假定11個節(jié)點）。對于路線的單向性或節(jié)點彼此不通的路線，設(shè)值一個比正常路徑大幾個數(shù)量級的值，如表1中設(shè)定1 000。對各分發(fā)點進行節(jié)點編號。表1中列表示出發(fā)，行表示到達，如：第2列第3行取值為3，表示從節(jié)點2出發(fā)，到達3節(jié)點路程為3個單位。

（2）創(chuàng)建初始種群。對于物流配送車輛所經(jīng)過的各節(jié)點編號所構(gòu)成的一條路線為一個個體（稱染色體），節(jié)點編號在個體中稱基因?；蛟趥€體中的位置不同，個體的表現(xiàn)（路程大?。┎煌榱嗽黾觽€體進化效率和多樣性，初始個體數(shù)量一般選擇得都比較多，這些初始個體所構(gòu)成的集合稱為初始種群。對于本問題，選擇初始種群的規(guī)模為100個。初始種群可借由MATLAB的randperm函數(shù)產(chǎn)生。由randperm函數(shù)按照分發(fā)點的節(jié)點編號所產(chǎn)生的一個個體形如：5 11 4 8 10 9 2 6 1 7 3。個體中節(jié)點編號是隨機排列的，每次調(diào)用randperm函數(shù)所生產(chǎn)的個體都可能互不相同。

表1 物流配送節(jié)點信息表

（3）個體評價和選擇。對于創(chuàng)建的初始種群需要對每個個體進行評價，好的個體和差的個體應(yīng)當(dāng)通過適當(dāng)規(guī)則進行保留和淘汰。依據(jù)節(jié)點信息（表1）對創(chuàng)建的初始種群中每個個體按節(jié)點編號順序所構(gòu)成的路線的路程值大小作為個體的適應(yīng)度評估函數(shù)，越小表明個體的適應(yīng)度越好，反之越差。在個體保留和淘汰方法上有多種策略，最常見的有輪盤賭法、隨機聯(lián)賽法、無回放余數(shù)比例隨機法等，本文選擇隨機聯(lián)賽法。隨機聯(lián)賽法是隨機抽取種群中兩個個體，比較其路程值，路程小的個體被保留，路程大的個體被淘汰。選擇后的種群規(guī)模和選擇前的種群規(guī)模保持相同。

（4）染色體編碼。遺傳算法運行過程不對所求解問題的實際決策變量直接操作，而是對表示可行解的個體的編碼進行交叉和變異操作。編碼就是把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法[1]。對物料配送路線的編碼方法比較多，本文選取Grefenstette等提出的編碼方法。對上述個體5 11 4 8 10 9 2 6 1 7 3采用Grefenstette編碼方法得到的染色體為：5 10 4 6 7 6 2 3 1 2 1。

（5）染色體交叉。染色體交叉是將種群中的染色體（種群中的個體）按照交叉概率，隨機選取染色體，隨機對染色體基因位置之前或之后的基因進行互換操作。本文采用隨機交叉點之前的基因?qū)﹄S機選取的兩條染色體進行交叉操作。

（6）基因變異。基因變異是將對構(gòu)成染色體的基因，按照變異概率，隨機選擇染色體上的基因進行隨機改變的操作。由于染色體的編碼方法決定了不同位置基因的可能取值，因此基因變異后，在該位置上的基因值應(yīng)保證是有效的基因改變。

（7）解碼和新個體評價。在染色體交叉、變異完成后，得到下一代新的種群。為了評價新種群中個體（染色體）的優(yōu)劣，需要首先將編碼的染色體按編碼的逆過程進行解碼。對解碼后的染色體按照適應(yīng)度進行評估，并按上述所確定的個體選擇規(guī)則保留或淘汰。

（8）計算進化代數(shù)和差異。計算種群中適應(yīng)度最好的個體，即路程最短的個體，并將該個體與上一代表現(xiàn)最好的個體進行對比，計算他們之間的差異值；同時計算種群進化的代數(shù)，當(dāng)兩條件都達到程序結(jié)束運行條件時程序就停止計算，并將優(yōu)化結(jié)果輸出。

3 求解及結(jié)果分析

按照遺傳算法的計算策略，采用MATLAB編制的求解程序框圖如圖2所示。

經(jīng)過幾次運行其計算結(jié)果如下：

進化第116代，當(dāng)前最小值61.000，共有1個最小值解；

群體中第64個個體，最小值61.000，2→3→4→5→11→10→9→8→6→7→1；

進化第385代，當(dāng)前最小值61.000，共有51個最小值解；

群體中第2個個體，最小值61.000，11→10→9→8→6→7→1→2→3→4→5。

從優(yōu)化計算的結(jié)果看，雖然得到最優(yōu)解的進化代數(shù)各不相同，但都能得到相同的結(jié)果。上述求解得到的路線2→3→4→5→11→10→9→8→6→7→1與路線 11→10→9→8→6→7→1→2→3→4→5在形式上不完全相同，但所確定的路線是完全一致的。結(jié)果表明，從配送中心出發(fā)，遍歷各分發(fā)點的最優(yōu)路線為：1→2→3→4→5→11→10→9→8→6→7，總路程為61個單位。

4 結(jié)論

采用遺傳算法求解物流配送路線最優(yōu)選擇是可行有效的方法。遺傳算法只與求解問題的目標(biāo)函數(shù)取值信息有關(guān)，而與實際所研究問題的類型和數(shù)學(xué)特性無關(guān)，因此具有廣泛的普適性。對于多節(jié)點遍歷問題或多孔加工路線最優(yōu)選擇等實際問題都可以利用遺傳算法進行求解。

圖2 遺傳算法求解物流配送路徑最短流程圖

參考文獻：

[1]周明，孫樹棟.遺傳算法原理與應(yīng)用[M].北京：國防工業(yè)出版社，1999:143-157.