基于遺傳算法的帶時間窗物流配送研究

尹作海，朱海，盧新宇，崔明

（1山東大學財務部，山東濟南 250100；2濟南歷城黃河河務局，山東濟南 250108；3山東省冶金科學研究院，山東濟南 250014）

信息化建設

基于遺傳算法的帶時間窗物流配送研究

尹作海1，朱海2，盧新宇3，崔明3

（1山東大學財務部，山東濟南 250100；2濟南歷城黃河河務局，山東濟南 250108；3山東省冶金科學研究院，山東濟南 250014）

針對帶時間窗的物流配送的特性，設計了基于遺傳算法的配送模型，以實際的配送任務作為實例，驗證了配送路徑設計方案，證實了遺傳算法模型和優化方案的可行性。

物流配送；遺傳算法；軟時間窗

1 物流配送的定義

物流配送是現代化物流系統的一個重要環節，它是指按用戶的訂貨要求，在配送中心進行分貨、配貨，并將配好的貨物及時送交收貨人。物流配送按客戶對送貨時間的要求分類，可分為帶時間窗和不帶時間窗兩種。所謂帶時間窗的物流配送，是指在制定配送路線時，不僅考慮客戶的貨物需求數量約束和配送車輛一次配送的最大行駛距離約束，而且要考慮客戶對貨物送到時間的要求。隨著企業的發展，零庫存成為許多企業追求的目標，于是客戶對貨物的送到時間提出了更高要求?？梢娧芯繋r間窗物流配送問題具有十分重要的現實意義［1］。

在帶時間窗物流的配送中，由于交通等方面的原因，可能無法在約定的時間窗內將貨物送到目的地，所以硬時窗實用性不高，代之以軟時間窗限制。軟時窗限制允許配送車輛的到達時間在時間窗之外，但是必須受到懲罰，懲罰點隨著超出時間窗范圍的增大而增大。

工業生產的快速發展，對高效物流的需求量越來越大，帶時間窗的物流優化問題是當前物流配送系統研究中的熱點問題，被廣泛應用于包括工業生產、商品配送等生產、流通經濟活動中。但是該問題具有NP-hard性質，難以求得最優解或滿意解。

2 帶時間窗物流配送模型的建立

根據帶時間窗物流配送過程中對時間等限制條件的特殊要求，以車輛路徑問題為方法和手段，將傳統物流中普遍使用的配送模型進行適當改進，使其適用于帶時間窗的物流配送，即將傳統物流配送模型加上時間和載重量限制等約束條件。

2.1 配送問題假設

帶時間窗物流配送的模型假設為一個配送中心為多個客戶派送貨品，配送的貨品類型單一，同時滿足以下條件：

1）物品流向為單向，即純送貨；2）運輸工具為m輛汽車，每輛車都有一定的裝載能力限制，滿足單車的容量大于運輸路線上客戶的總需求量；3）每個客戶的需求量是已知的，所需貨物只能由一輛汽車完成，且所有客戶都應該得到服務；4）每條線路的開始和結束位置都在配送中心，所有車輛必須在規定的時間內返回配送中心；5）每個客戶都有一個指定的服務時間窗，送貨必須在此時間范圍內進行；6）目標為多目標：車輛運輸費用最小、車輛運輸時間及全部客戶的等待時間最短；7）配送中心與客戶之間，以及兩兩客戶之間的最優配送線路已知。

2.2 參數定義

假設共有m輛車（k=1，2，…，m），n個客戶（i=1，2，…，n），第i個客戶的需求量為wi，并且己知各個客戶互相間的相對距離矩陣以及客戶位置分布圖。給所有參與配送的車輛下達配送任務，在時間窗限制以及車載重量限制內，產生考慮時間窗限制以及車載重量限制的最短配送時間目標數學模型，這樣的任務安排能完成所有配送任務并且總懲罰點數最少。

設N={1，2，…，n}，K={1，2，…，m}，Sij為從客戶i到客戶j的最短配送時間；Xijk=（0，1）為由客戶i由車輛k行駛至客戶j之二元變量；Yki=客戶i由第k輛車服務，?i∈N，k∈K；wi：第i個客戶的配送重量，?i∈N；WL=車輛載重上限；ETi：任務i的最早開始時刻，i∈N；LTi：任務i的最遲開始時刻，i∈N；ui：i的服務時間，i∈N；Xijk=1時車輛k從任務i行駛到任務j，或Xijk= 0時車輛k不從任務i行駛到任務j，i，j∈N，k∈K；Yijk=1時任務i由車輛k完成，或Yijk=0時任務i不由車輛k完成，j∈N，k∈K。

配送車輛時間計算函數C1：

配送車輛載重懲罰函數C2：

時間懲罰函數C3：

其中：M1、M2、M3分別為早到懲罰系數、遲到懲罰系數和超過T的懲罰系數。

限制條件：某一配送車輛的總載重量不大于配送車輛載重量上限

總配送時間為每輛車程的總和

目標函數Minimize:

3 遺傳算法優化方案設計

物流配送是中國整個物流系統中的薄弱環節，由于現有的配送方案不合理，造成了配送過程中效率低，耗損率過高等現象。因此只有對物流配送方案進行合理的優化設計，才能有效彌補物流系統中存在的上述不足。然而由于帶時間窗的物流配送模型求解是一個NP-hard問題，使得傳統的精確求解方式并不適用。而遺傳算法做為一種啟發式算法，是通過模仿自然界的生物進化機制，發展起來的一種全局隨機搜索和優化方法，具有更好的全局搜索特性。

本研究針對帶時間窗的物流配送的特性，站在實際需求的角度，對帶有時間窗的配送模式進行分析，以一個配送中心和63個客戶的每日配送任務為實例，使用改進的配送模型和遺傳算法對配送方案進行優化設計。采用Matlab7.1，對物流配送模型進行求解［2］。物流分配的遺傳算法設計流程見圖1。

3.1 參數選擇

前提條件：1）相同車型；2）同一時間配送；3）相同客戶服務時間；4）相同配送車輛載重上限。設定遺傳算法內部參數，分別計算5個種群，每種群體規模均運算10次，尋找最優解。

1）g_max（最大遺傳代數）=6 000；2）Size（種群規模）=100，200，…，500；3）變異概率=0.1；4）載重限制=5 t；5）車輛設置輛數=16；6）M1（早到懲罰點數）=3；7）M2（遲到懲罰點數）=10；8）M3（每條路線超過180 min懲罰數）=10；9）D（超重懲罰點數）=10；10）fwsj（服務時間）=10。

圖1 遺傳算法流程

3.2 求解質量及穩定性評價

實驗中，每一代的每個體都被評估，并通過計算適應度函數得到一個適應度數值。種群中的個體被按照適應度排序，最好的個體有更多機率被選擇去產生下一代，適應度低的個體逐漸被淘汰掉。

由于遺傳算法是基于全局搜索的啟發式解法，也就是在操作過程中會運算所有種群，所以造成運算前期會劇烈波動，但是隨著代數的增加而逐漸穩定，并最終下降收斂。

最后，分別繪制不同種群規模下最短配送時間見圖2，計算時間見圖3，并進行比較。得知Size= 100，群體規模較小時，父代進入選擇、交叉、變異過程的種群少，因此求解的速度較快，達到收斂狀態；也因為較低的群體多樣性，求解過程容易出現“早熟”現象，求解質量不高。而隨著種群規模的不斷擴大，運行時間明顯增加，算法的運行效率大大降低。綜合考慮，種群為300時，具有較佳的求解品質與最有效率的運行時間。

圖2 不同種群規模下最短配送時間

圖3 不同種群規模下各種群計算時間

由圖4可知，種群為300時，5 800代后產生最高適應度值，曲線趨于平穩，顯示5 800代后運算過程趨于穩定且收斂。

4 結語

研究了帶軟時間窗的物流配送方案的優化設計問題，考慮了帶時間窗配送的時間要求和載重量限制這兩方面的因素。在常溫條件下物流配送模型的基礎上，加入了帶時間窗物流配送的時間窗限制和載重量限制，并以實際的配送任務做為實例，驗證了文中提出的配送路徑設計方案，證實了遺傳算法模型和優化方案的可行性。

圖4 種群=300適應度與收斂性

［1］國家發展和改革委員會經濟運行局，南開大學現代物流研究中心.中國現代物流發展報告［M］.北京：電子工業出版社，2008.

［2］曹陽，方強，王國仁，等.基于遺傳算法的多連接表達式并行查詢優化［J］.軟件學報，2002，13（2）：250-257.

Research on Logistics Distribution with Time Window Based on Genetic Algorithm

YIN Zuohai1,ZHU Hai2,LU Xinyu3,CUI Ming3

（1 Finance Department，Shandong University,Jinan 250100,China;2 Yellow River Jinan Licheng Bureau,Jinan 250108,China; 3 Shandong Metallurgical Research Institute,Jinan 250014,China）

According to the feature of logistics distribution with time window,the thesis designs distribution model based on genetic algorithm.Taking the actual distribution task for example,the thesis verifies the distribution path design plan and confirms the feasibility of genetic algorithm model and optimization plan.

logistics distribution;genetic algorithm;soft time window

F253.9

A

1004-4620（2015）03-0054-03

2015-05-15

尹作海，男，1980年生，2009年畢業于山東大學計算機科學與技術學院?，F為山東大學財務部信息科副科長，工程師，從事財務信息化工作。