齊心

摘 要：物流配送是現(xiàn)代物流的一個核心內(nèi)容，文章以物流配送的總花費最小構建目標函數(shù)，建立了物流配送路徑優(yōu)化模型，并對所建立的模型進行分析，為避免遺傳算法在求解該類問題有可能陷入局部最優(yōu)解的情況，設計了基于遺傳算法和模擬退火算法的綜合啟發(fā)式算法，最后通過實例驗證了該模型和算法的優(yōu)勢。

關鍵詞：物流配送；路徑優(yōu)化；啟發(fā)式算法

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

Abstract： Logistics distribution is a core content of modern logistics. In this paper， the mathematical model of logistics distribution path optimization is established by taking the minimum total cost of logistics distribution as the objective function. In order to avoid the possibility that the genetic algorithm will fall into the local optimal solution， a comprehensive heuristic algorithm based on genetic algorithm and simulated annealing algorithm is designed. Finally， an example is given to demonstrate the superiority of the model and algorithm.

Key words： logistics distribution； routing optimization； heuristic algorithm

0 引 言

目前很多物流有限公司存在的問題主要是配送成本過高，隨著物流信息的加強，各分店對業(yè)務時間的要求越來越高，公司配送系統(tǒng)的不完善性使公司有時無法滿足顧客的時間窗要求，車輛的載重量過小，有時為滿足分店的時間要求，只能對某些分店進行專車配送，但這樣的配送方式往往存在成本過高、運距過遠等問題。物流公司迫切的希望優(yōu)化配送系統(tǒng)，通過整合各分店的配送信息，從整體上分析建立配送系統(tǒng)，盡可能降低配送的成本，提高顧客滿意度，增加企業(yè)的競爭力。針對物流公司存在的問題，本文以物流配送的總花費最小為目標函數(shù)，構建合理的模型，并對所建立的模型進行了分析，通過運用掃描法和遺傳算法，對數(shù)學模型求解出最優(yōu)的配送方案，這可以給相關配送路徑優(yōu)化問題作為參考。

1 問題描述及模型的建立

1.1 問題描述

通過對物流公司的調(diào)研和數(shù)據(jù)采集，發(fā)現(xiàn)對軟時間窗單向配送車輛優(yōu)化調(diào)度問題的研究更符合實際，配送方案由k條簡單的回路組成，最終目標是通過合理安排配送車輛的行駛路線，在滿足各分店需求的條件下，使總的配送成本最小，說明如下：（1）單配送中心由一個配送中心對多個需求點的貨物進行配送。（2）純送貨問題，只從配送中心送貨到各分店，而不取貨，屬于單向配送。（3）帶軟時間窗，客戶對時間的要求越來越高，而由于配送條件限制，很難滿足硬時間窗的要求，因此軟時間窗的模型更符合實際情況，且其條件相對寬松，容易找到可行解。

1.2 物流配送路徑優(yōu)化模型的建立

為了方便建立模型，先對以下幾點進行假設：（1）配送中心無缺貨情況；（2）需求點的需求量、地理位置、時間要求等為已知，配送中心的位置已知；（3）配送車輛的數(shù)量和容量已知；（4）配送車輛從配送中心發(fā)出，在完成配送任務后必須返回；（5）一條回路上的所有客戶需求量之和不能超過配送車輛的裝載能力；（6）配送車輛一次配送的最大行駛距離要大于每條配送路徑的長度；（7）車速為某一固定的平均值；（8）每輛車只有一條行駛路線，且每個需求點的貨物只能由一輛配送車輛配送。

模型建立：

（1）參數(shù)說明

2.2 算法設計

2.2.1 初始可行解的產(chǎn)生

本文在掃描法的基礎上，結合最近插入法的思想來制定一種相應的插入準則，形成一種新的掃描插入法。利用掃描插入法得到初始配送方案，如圖1所示：

由圖中可得到初始遺傳算法種子，即：0-7-6-1-0-5-3-0-8-0-11-4-0

-10-9-0-2-0。

2.2.2 遺傳算法求解

（1）使用自然數(shù)編碼方式。比如染色體0230450670，它包含3條子路徑，分別為0-2-3-0， 0-4-5-0， 0-6-7-0，也表示需要車輛為3輛。

（2）適應度函數(shù)。本文適應值函數(shù)為目標函數(shù)的倒數(shù)。

（3）選擇算子：為避免產(chǎn)生局部收斂的情況，選擇混合模擬退火算法的兩點變異算子。

（5）終止循環(huán)的條件，由迭代的次數(shù)決定，本文中進化代數(shù)為G=500。

3 實例驗證與結果分析

3.1 實例驗證

3.2 結果分析

運行遺傳算法程序，最終得到如圖2所示的結果：

分析結果，可知：最優(yōu)解配送結果是總配送成本為4 430元，其對應的染色體為：0-6-8-0-5-0-4-0-10-9-0-7-11-3-0

-1-2-0。

可知染色體中安排的車輛數(shù)為6，可得6個閉合路徑，具體如圖3所示。

隨機生成初始解后的遺傳算法的運行結果，由于初始解的隨機性，最終結果也不穩(wěn)定。經(jīng)過計算，隨機求解，連續(xù)運行10次，將得到的結果進行統(tǒng)計，如表5所示。

得到的最優(yōu)結果如圖4所示。

根據(jù)上面的結果可知：

由隨機生成初始解的遺傳算法和掃描插入法形成的初始種群，得出的結果如表6所示。

經(jīng)計算可知，用掃描插入法生成初始解，違約時間減少了3.5小時，優(yōu)化了77.35%；在總里程上，節(jié)省了60km的運距，優(yōu)化了3.56%；在總成本費用上，節(jié)省了856元，優(yōu)化了16.19%。

4 結束語

本文通過將具體的配送線路問題和限制條件轉變?yōu)閹r間窗的配送數(shù)學模型，然后用掃描法和插入法進行了綜合并改進，求出初始可行解，并以它為種子，進行百分百變異，得到新的初始化種群，再通過遺傳算法的算法設計，用MATLAB進行求解，最終結果大大改善了遺傳算法的效率和尋找滿意解的能力。隨著現(xiàn)代物流技術的更加成熟，各企業(yè)也應該跟隨技術的發(fā)展，致力于基于電子商務的物流配送，應該充分的利用物流技術及相關理論，因地制宜地尋求更加合理、科學、高效的運營方法。為了提高物流公司的運營效率，第三方物流的研究也是當前的熱點，因此在以后的學習和研究中，基于第三方物流研究將是重要的方向。

參考文獻：

[1] Y. Dumas， F. Soumis， J. Desrosiers. Optimizing the Schedule for a Fixed Vehicle Path with Convex Inconvenience costs[J]. Transportation， 1990，24（2）：145-152.

[2] T. Sexton &， Y. Choi. Pickup and Delivery of Partial Loads with “Soft” Time Windows[J]. Am. J. Math. Mgmt. Sci， 1986，6（3-4）：369-398.

[3] 夏新海. 物流配送車輛調(diào)度優(yōu)化研究[D]. 武漢：武漢理工大學（碩士學位論文），2004.

[4] 林珊，段復建. 一個物流配送中心選址模型及其算法[J]. 吉首大學學報（自然科學版），2012，33（6）：29-32.

[5] 陽永生. 基于分支定界算法的物流配送網(wǎng)絡優(yōu)化研究[J]. 數(shù)學理論與應用，2010（1）：57-61.

[6] 樊蓉. 物流配送中車輛調(diào)度算法的比較研究[D]. 南京：南京農(nóng)業(yè)大學（碩士學位論文），2013.

[7] 柳林，朱建榮. 基于遺傳算法的物流配送路徑優(yōu)化問題的研究[J]. 計算機工程與應用，2005（27）：227-229.

[8] 許歡. 多目標進化算法在物流配送車輛路徑問題中的應用研究[D]. 廣州：廣東工業(yè)大學（碩士學位論文），2013.

[9] 李義華. 基于多智能體的物流配送車輛調(diào)度決策方法研究[D]. 長沙：中南大學（博士學位論文），2012.

[10] 馬彥東. 配送中心車輛調(diào)度模型及遺傳算法設計[J]. 物流科技，2008，31（5）：79-82.

[11] 張之富，余靜，凌鐳，等. 基于改進遺傳算法的車輛優(yōu)化調(diào)度研究[J]. 中國水運，2009，9（4）：73-75.