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

（1山東大學(xué)財務(wù)部，山東濟(jì)南 250100；2濟(jì)南歷城黃河河務(wù)局，山東濟(jì)南 250108；3山東省冶金科學(xué)研究院，山東濟(jì)南 250014）

信息化建設(shè)

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

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

（1山東大學(xué)財務(wù)部，山東濟(jì)南 250100；2濟(jì)南歷城黃河河務(wù)局，山東濟(jì)南 250108；3山東省冶金科學(xué)研究院，山東濟(jì)南 250014）

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

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

1 物流配送的定義

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

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

工業(yè)生產(chǎn)的快速發(fā)展，對高效物流的需求量越來越大，帶時間窗的物流優(yōu)化問題是當(dāng)前物流配送系統(tǒng)研究中的熱點(diǎn)問題，被廣泛應(yīng)用于包括工業(yè)生產(chǎn)、商品配送等生產(chǎn)、流通經(jīng)濟(jì)活動中。但是該問題具有NP-hard性質(zhì)，難以求得最優(yōu)解或滿意解。

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

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

2.1 配送問題假設(shè)

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

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

2.2 參數(shù)定義

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

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

配送車輛時間計算函數(shù)C1：

配送車輛載重懲罰函數(shù)C2：

時間懲罰函數(shù)C3：

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

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

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

目標(biāo)函數(shù)Minimize:

3 遺傳算法優(yōu)化方案設(shè)計

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

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

3.1 參數(shù)選擇

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

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

圖1 遺傳算法流程

3.2 求解質(zhì)量及穩(wěn)定性評價

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

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

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

圖2 不同種群規(guī)模下最短配送時間

圖3 不同種群規(guī)模下各種群計算時間

由圖4可知，種群為300時，5 800代后產(chǎn)生最高適應(yīng)度值，曲線趨于平穩(wěn)，顯示5 800代后運(yùn)算過程趨于穩(wěn)定且收斂。

4 結(jié)語

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

圖4 種群=300適應(yīng)度與收斂性

［1］國家發(fā)展和改革委員會經(jīng)濟(jì)運(yùn)行局，南開大學(xué)現(xiàn)代物流研究中心.中國現(xiàn)代物流發(fā)展報告［M］.北京：電子工業(yè)出版社，2008.

［2］曹陽，方強(qiáng)，王國仁，等.基于遺傳算法的多連接表達(dá)式并行查詢優(yōu)化［J］.軟件學(xué)報，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年畢業(yè)于山東大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院。現(xiàn)為山東大學(xué)財務(wù)部信息科副科長，工程師，從事財務(wù)信息化工作。