遺傳算法在物流配送線(xiàn)路選擇方面研究

1 概述

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

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

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

圖1 物流配送路線(xiàn)示意圖

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

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

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

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

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

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

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

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

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

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

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

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

經(jīng)過(guò)幾次運(yùn)行其計(jì)算結(jié)果如下：

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

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

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)：

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