基于物流車輛調度算法的研究

摘 要: 物流車輛優(yōu)化調度問題是一個研究熱點，學者們采用了各種優(yōu)化方法來解決實際問題。本文簡述了物流配送車輛調度問題的常見算法，對求解車輛優(yōu)化調度問題的步驟作了說明，并在結論中提出了算法的不足之處，以使大家根據(jù)實際情況選擇最佳的車輛調度算法，提高經(jīng)濟效益。

關鍵詞: 物流車輛調度 蟻群算法 遺傳算法 神經(jīng)網(wǎng)絡算法

1.蟻群算法

螞蟻在路徑上前進時會根據(jù)前邊走過的螞蟻所留下的分泌物選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強度成正比。因此，由大量螞蟻組成的群體的集體行為實際上構成一種學習信息的正反饋現(xiàn)象:某一條路徑走過的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個體間通過這種信息的交流尋求通向食物的最短路徑。蟻群算法就是根據(jù)這一特點，通過模仿螞蟻的行為，從而實現(xiàn)尋優(yōu)。

采用蟻群算法求解車輛優(yōu)化調度問題的步驟:

1.1將任務點分派到車輛上:

1.1.1選擇未用的車輛K;

1.1.2在未分派的任務點在中從角度最小的開始為車輛K指定任務點，直到容量限制不滿足為止，如果有剩余任務點，則重復前兩個步驟，直到所有任務點都被分配到車輛上。

1.2所分派的任務點集合記為v，而v=m設定有m只螞蟻，按照蟻群算法求解TSP問題算法的步驟執(zhí)行。

1.3按照各任務點的極坐標中角度的大小依次和車場來確定n條掃描線，重復n次step1和step2來得到n種調度方案，比較得到最佳的方法就是問題的解。

2.遺傳算法

遺傳算法是上世紀60年代由美國J.Holland教授首先在《自然結合人工智能系統(tǒng)的適應性》一書中提出的，是一種新興的自適應隨機搜索方法，具有極強的魯棒性和內在的并行計算機制。遺傳算法主要由選擇、交叉和變異三個算子組成，分別模仿自然界進化過程中的自然選擇和群體遺傳過程中發(fā)生的交配和突變等現(xiàn)象。

采用遺傳算法求解車輛優(yōu)化調度問題時，一般按照以下步驟進行。

2.1確定染色體的編碼和初始群體

采用自然數(shù)對可行線路進行編碼，如長度為l+m的染色體可寫為:

(0，i11，i12，…，i1s，0，i21，…，i2t，0，…，0，im1，…，imn)

其中，ikj表示第ikj項任務，這樣的染色體結構可理解為車輛從車場0出發(fā)，經(jīng)過任務i11，i12，…，i1s后回到車場0，形成子路徑1;然后又從車場0出發(fā)，經(jīng)過任務i21，…，i2t后返回車場，形成路徑2，如此反復，直到所有的m項任務全部被完成為止。在子路徑1內交換i11和i12的位置表示行走路徑的改變，也使函數(shù)目標改變。這樣，下面的遺傳疊代可使函數(shù)目標最小，也即趨向于最佳或較佳的路徑。初始群體的產生采用隨機方法，隨機產生l個城市的全排列，根據(jù)任務的源點和匯點將0標準插入排列中，形成一條初始染色體。如此反復，直到滿足群體數(shù)，群體數(shù)一般大于20個。

2.2確定適應度函數(shù)

車輛調度的優(yōu)化目標有多種多樣，常見的目標有總運費最小，總運輸時間最短，空載車總運行時間最小，完成任務所需的車輛最小總運輸時間最短，空載車總運行時間最小，完成任務所需的車輛最小等，以總運費最小為例，其目標函數(shù)為:C=minCX。該式中，Cij為從源點i到匯點j每輛車的單位費用，Xij為每班從源點i到匯點j的滿載車的數(shù)量。m，n為源點和匯點的數(shù)目。

2.3處理約束

為保證車輛調度優(yōu)化的正確性，約束往往必不可少，常見的約束有匯點處理能力約束，非負約束，車流連續(xù)性約束。

一般采用懲罰的方法來處理約束，如果一個染色體對應的解違反了某個約束，根據(jù)其違反程度給予一定的懲罰，使其具有較小的適應度值。這樣在不損失群體數(shù)目的基礎上，隨著疊代的進行，使不可行解的數(shù)目在群體中所占比例越來越小，可行解的數(shù)目則逐漸增加，并趨向最優(yōu)解。

2.4遺傳算子

經(jīng)典的遺傳算子包括復制、交叉、變異。復制算子的目的是保留優(yōu)良個體，避免基因缺失，提高全局收斂性和效率。目前常用的復制算子有放回式隨機復制又稱輪盤賭復制，無放回式隨機復制等十幾種。

2.5確定調度方案

通過上述的遺傳操作，產生性能最優(yōu)的染色體串，根據(jù)初始的編碼規(guī)定將該串解碼成最優(yōu)調度方案。

3.神經(jīng)網(wǎng)絡算法

人工神經(jīng)網(wǎng)絡是對人腦功能的簡單和近似模擬，它由大量具有某種傳遞函數(shù)的神經(jīng)元相互連接而成。人們經(jīng)常采用Hopfield網(wǎng)絡和自組織特征映射神經(jīng)網(wǎng)絡來解決車輛的優(yōu)化調度問題。在Hopfield網(wǎng)絡中，系統(tǒng)能夠從初始狀態(tài)，經(jīng)過一系列的狀態(tài)轉移而逐漸收斂于平衡狀態(tài)，此平衡狀態(tài)是局部極小點。采用神經(jīng)網(wǎng)絡來求解車輛調度問題時一般按下列步驟進行。

3.1產生鄰接矩陣

將車輛的源點、所經(jīng)過的各個匯點和停點抽象成網(wǎng)絡的結點，它們之間的有向路徑抽象成網(wǎng)絡的邊，由此構成一個有向圖G=(N，L，D)，其中N表示結點數(shù)，L表示邊數(shù)，D為N×N的矩陣，可根據(jù)優(yōu)化的目標分別是邊(i，j)對應的長度、費用或時間，這樣可定義距離鄰接矩陣、費用鄰接矩陣和時間鄰接矩陣。如果兩個結點間存在路徑，則相應矩陣元素的值為路徑的長度或運費或運時;如果兩個結點間不存在路徑，則相應矩陣元素的值為∞。

3.2約束的處理

對于車輛調度中的約束，將其作為神經(jīng)網(wǎng)絡的一個能量項來處理，將其施加一個懲罰項后加入到網(wǎng)絡的能量方程式中，這樣隨著網(wǎng)絡的收斂，約束的能量也逐漸趨于穩(wěn)態(tài)，使約束得到體現(xiàn)。

3.3神經(jīng)網(wǎng)絡計算

設鄰接矩陣中的每個元素對應著一個神經(jīng)元，定義位于位置(x，i)的神經(jīng)元的輸出為Vxi。首先確定網(wǎng)絡的能量函數(shù)，該能量函數(shù)包括網(wǎng)絡的輸出能量函數(shù)和各個約束轉化的能量函數(shù)，進而，確定神經(jīng)元的傳遞函數(shù)和狀態(tài)轉移方程，經(jīng)過網(wǎng)絡的反復演化，直至收斂。

當網(wǎng)絡經(jīng)過演化最終收斂時，可形成一個由0和1組成的換位陣，陣中的1所在位置即表示所經(jīng)過的結點，這些結點間的距離、費用和運時之和即為最短距離、最少運費和最小運時。

3.4調度方案的形成

根據(jù)換位陣所形成的最短距離、最小運費和最小運時路徑，最終來確定車輛調度的方案。

4.結語

蟻群算法有較強的魯棒性，只要對該算法模型稍加修改，便可以應用于其它問題，但是由于需要較長的計算時間，容易出現(xiàn)停滯現(xiàn)象，而且沒有考慮當連續(xù)空間優(yōu)化問題轉換到有向圖搜索問題時，信息素分配給可行解帶來的尺度變化對于連續(xù)解空間搜索效率的影響。遺傳算法只有與其他方法如啟發(fā)式方法和模擬退火算法雜合，以及將調度專家經(jīng)驗融入模型和遺傳操作中，才能提高求解的效果。神經(jīng)網(wǎng)絡的問題是對某一個問題構建網(wǎng)絡所定義的條件不足而有太多因素需要考慮:訓練的算法、體系結構、每層的神經(jīng)元個數(shù)、有多少層、數(shù)據(jù)的表現(xiàn)等，還有其它更多因素，因此應用于車輛調度不是那么容易。就目前情況而言，我國的VRP研究仍然有限，可以說仍未能滿足經(jīng)濟發(fā)展的需要。首先是起步較晚，通用理論研究較少;其次，對于具體問題提出的應用研究相對較多，但多為對具體算法的部分改進，且限于各自的適用條件，局限性較強。因此，如何針對各地地形條件、各行業(yè)物流配送運輸?shù)奶攸c，結合不同的算法進行優(yōu)勢互補和消除缺陷，設計出通用性好、運算速度快、精度高的優(yōu)良算法，將是研究發(fā)展的方向，還有待于各學科專家學者們作深入細致的研究。

指導老師:洪玲