遺傳節約綜合算法在配送路線優化中的應用

喻　偉　何其超　張增棨

摘要：文章針對配送路線問題進行研究，首先提出配送路線優化的原則，在此基礎上提出了解決配送路線問題的遺傳節約綜合算法的流程和步驟，最后通過一個算例實現了本文提出的算法，并與其它方法的計算結果進行了比較，從而證實了遺傳節約綜合算法的優越性。

關鍵詞：物流；配送路線；遺傳算法；節約算法

中圖分類號：U116.2文獻標識碼：A

Abstract: In studying the distribution routes, the paper first introduces the principle of distribution route optimization, and then presents the process and steps of saving hybrid genetic algorithm solving the distribution issue, and last realizes the algorithm raised in this paper by an algorithm example. Compared to the calculated results of other methods, it proves the superiority of saving hybrid genetic algorithm.

Key words: logistics; distribution route; genetic algorithm; saving algorithm

0 引言

配送是近距離、小批量、多品種的物資，根據用戶需要，把貨物從配送中心送到所需的各個用戶手中的物流過程。配送路線優化問題主要是指在保證商品準時到達客戶指定點的前提下，如何盡可能地減少運輸的車次和運輸的總路程[1]。目前解決此問題主要采用節約啟發式算法(通常稱為節約法)、遺傳算法、禁忌搜索算法等單一算法，各種算法均存在一定的缺陷[2]。本文主要通過將遺傳算法和節約法兩種算法進行結合產生的遺傳節約綜合算法來解決配送路線優化問題。

1 配送路線優化原則

進行配送路線優化時，必須有明確的目標，遵循基本的原則。配送路線方案目標的選擇可以從以下幾個方面來考慮：

(1)配送效益最高或配送成本最低；

(2)配送里程最短；

(3)配送服務水準最優。

在滿足客戶需求的前提下，配送車輛行駛的路程越短，配送的成本越低、效益越高，因此配送成本最低和配送里程最短兩個目標選擇其中一個即可，本文以配送里程最短為優化目標。

2 配送路線優化的遺傳節約綜合算法

采用遺傳節約綜合算法解決以上模型，即在進程層次上，依次進行全局的遺傳搜索和局部的節約搜索，是一種兩層串行結構。其中，節約操作的個體對象來自遺傳的進化結果，而經過節約操作得到的解群又成為新遺傳操作的進一步進化的種群對象，這個過程反復迭代，直到滿足終止條件為止，終止條件作為基本參數，在運行前輸入，可以包括：目標函數滿意值、一定的遺傳代數、連續多次運算結果均一致不再出現優化值等。遺傳節約綜合算法主要步驟如下。以下步驟可通過VB等軟件編程實現。

step2：設置參數。遺傳參數包括群體規模n，適當大的數M，遺傳操作的類型(確定型和自適應型選一)，并設置控制參數；

以下首先進行遺傳操作過程：

step3：令t=0，隨機產生初始群體p0，群體中包括n條染色體，每個染色體表示一條可行的配送線路；

step4：將群體pt中n條染色體解碼為線路，計算其目標函數，即運輸成本；

step5：尋找群體pt中最優染色體bestt，即目標函數最小的線路；

step6：計算pt中n條染色體的適應度；

step7：若滿足終止條件之一，則停止運算，結束程序，輸出pt中的最優染色體bestt作為滿意解；否則，繼續；

step13：根據各輛車所承擔的貨運任務總量，進行從大到小的排序，并將相應的車輛重新編號為L-m；

stepl4：令當前車輛號mo=1，待選池A1=空集；

step15：針對第mo輛車所承擔的各個任務節點，計算費用節約值，并進行從大到小的排序；

step16：進行第mo輛車的原始子路徑Ra安排。按照費用節約值從大到小的順序，將各個貨運節點插入，產生原始子路徑Ro；

step17：第mo輛車的原始子路徑Ro安排中，若有不滿足容量約束的節點，則將此節點放入待選池A1；

step18：計算待選池A0中的各個待選節點與原始子路徑Ro的起點、終點之間的費用節約值（不包括待選節點相互之間），并進行從大到小的排序；

step19：按照step18中費用節約值從大到小的順序，將各個待選節點嘗試接入原始子路徑Ro。若滿足容量和時間約束，則插入，并從A0中刪除該節點；否則繼續，直至A0所有待選節點考察完畢，得到第mo輛車的子路徑R；

step20：令A0=A0+A1，A1=空集，即將A0和A1合并為A0，同時清空A1；

step2l：令mo=mo+1，若mo≤m(車輛總數)，則轉step15；否則，將m輛車的子路徑合并到一起。形成第j條完整的配送線路，并繼續；

step22：令j＝j+1，若j≤n(群體規模)，則轉step12，否則繼續；

step23：將n條配送線路編碼為n條染色體，形成新的群體pt+1，令t=t+l轉step4。

3 算法的實現

某配送中心使用載重量為4噸的廂式貨車向其13個客戶(C1—C13)配送物資，各點間單位運費均一樣，配送中心（C0）和各客戶間距離如表1所示，各客戶配送量如表2所示。

根據以上數據，采用節約法優化配送路線，其結果如表3。

采用遺傳節約綜合算法求解基本過程如下，最終結果如表4。

4 結論

將節約法和遺傳節約綜合算法的計算結果進行對比，派車數二者均為4輛，總行駛距離綜合遺傳算法的結果較節約法少29公里，且車輛實載率有三車達到97.5％，較節約法結果也更優。

通過以上分析，遺傳節約綜合算法將遺傳算法和節約算法相結合，相互補充，較好地解決了配送路線優化的問題。但由于該算法需要進行一定數量的迭代計算，因此需要通過計算機編程實現，存在不適合于手工計算的情況。

參考文獻：

[1] 李永生，鄭文嶺． 倉儲與配送管理[M]． 北京：機械工業出版社，2005．

[2] 徐天亮． 運輸與配送[M]． 北京：中國物資出版社，2002．

[3] 李軍，郭耀煌． 物流配送車輛調度優化理論與方法[M]． 北京：中國物資出版社，2001．

[4] 趙家俊，于寶琴． 現在物流配送管理[M]． 北京：北京大學出版社，2004．

[5] 朱德通． 最優化模型與實驗[M]． 上海：同濟大學出版社，2003．

[6] 《運籌學》教材編寫組． 運籌學[M]． 北京：清華大學出版社，2008.

[7] 龔沛曾，陸慰民，楊志強． Visual Basic程序設計教程[M]． 北京：高等教育出版社，2003．

“注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”。