齊心

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

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

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

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

1 問題描述及模型的建立

1.1 問題描述

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

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

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

模型建立：

（1）參數(shù)說明

2.2 算法設(shè)計(jì)

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

本文在掃描法的基礎(chǔ)上，結(jié)合最近插入法的思想來制定一種相應(yīng)的插入準(zhǔ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）適應(yīng)度函數(shù)。本文適應(yīng)值函數(shù)為目標(biāo)函數(shù)的倒數(shù)。

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

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

3 實(shí)例驗(yàn)證與結(jié)果分析

3.1 實(shí)例驗(yàn)證

3.2 結(jié)果分析

運(yùn)行遺傳算法程序，最終得到如圖2所示的結(jié)果：

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

-1-2-0。

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[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]. 武漢：武漢理工大學(xué)（碩士學(xué)位論文），2004.

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

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

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

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

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

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

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

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