張國(guó)英　林賢茂

摘要：配送是物流系統(tǒng)中一個(gè)直接與消費(fèi)者相連的重要環(huán)節(jié)，對(duì)配送系統(tǒng)進(jìn)行優(yōu)化，可以提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化，因此配送系統(tǒng)的優(yōu)化問(wèn)題顯得尤為重要。進(jìn)行配送系統(tǒng)優(yōu)化，主要是配送車輛調(diào)度的優(yōu)化。文章在全面分析研究物流配送業(yè)務(wù)特點(diǎn)的基礎(chǔ)上，針對(duì)配送中的核心問(wèn)題——車輛調(diào)度優(yōu)化問(wèn)題進(jìn)行了深入的研究，建立了單源點(diǎn)物流配送車輛調(diào)度優(yōu)化問(wèn)題的數(shù)學(xué)模型，并運(yùn)用遺傳算法對(duì)其進(jìn)行求解，仿真實(shí)例證明了該方法的有效性。

關(guān)鍵詞：物流配送；車輛調(diào)度；遺傳算法

中圖分類號(hào)：U116.2文獻(xiàn)標(biāo)識(shí)碼：A

Abstract: Distribution is an important link in logistics, which is joined to consumers directly. Vehicle Routing Problem（VRP）is the main part of optimizing the distribution system. It can advance the economic benefits and make logistics scientific. Firstly, the paper analyzes VRP, and sorts it according to given conditions. Secondly, it chooses a typical one to analyze. It sets a model of the problem, and settles it with a genetic algorithm that is fast and accurate. Lastly, the paper illustrates the process of using the method referred in the paper by an example.

Key words: distribution; VRP; genetic algorithm

0引言

物流配送車輛優(yōu)化調(diào)度問(wèn)題于1959年由Dantzig和Ramser提出，國(guó)外一般稱之為Vehicle Routing Problem（VRP）[1]。車輛調(diào)度問(wèn)題是指為服務(wù)于已知的一組顧客的一個(gè)車隊(duì)，設(shè)計(jì)一組開(kāi)始和結(jié)束于一個(gè)中心出發(fā)點(diǎn)的最小費(fèi)用路徑。每個(gè)顧客只能被服務(wù)一次，而且一個(gè)車輛服務(wù)的顧客數(shù)不能超過(guò)它的能力。VRP已被證明是一個(gè)NP問(wèn)題。

VRP問(wèn)題的研究起步較早，求解方法也非常豐富，基本上可以分為精確算法和啟發(fā)式算法兩大類[2]。由于VRP問(wèn)題是強(qiáng)NP難題，高效的精確算法存在的可能性不大，所以尋找近似算法是必要和現(xiàn)實(shí)的，本論文在建設(shè)物流配送體系、改進(jìn)遺傳算法的應(yīng)用等方面進(jìn)行了新的探索與嘗試，主要工作在于：

（1）將改進(jìn)遺傳算法應(yīng)用于物流配送優(yōu)化中實(shí)際問(wèn)題的求解，并采用計(jì)算機(jī)語(yǔ)言完成對(duì)其算法的實(shí)現(xiàn)；

（2）通過(guò)實(shí)證分析，改進(jìn)遺傳算法用于物流配送優(yōu)化的效果。

1問(wèn)題描述

典型的VRP問(wèn)題可以描述為：從某物流中心用多臺(tái)配送車輛向多個(gè)客戶送貨，每個(gè)客戶的位置和貨物需求量一定，每輛配送車輛的載重量一定，其一次配送的最大行駛距離一定，要求合理安排車輛配送路線，使目標(biāo)函數(shù)得到優(yōu)化。

2掃描法和遺傳算法介紹

制定從一個(gè)物流中心向多個(gè)用戶運(yùn)送貨物的配送計(jì)劃時(shí)，必須考慮每輛車的運(yùn)載能力和行駛距離及時(shí)間等的限制。掃描法是一種能較好地解決配送路線問(wèn)題的方法。

遺傳算法最早由美國(guó)密切根大學(xué)（Michigan）的Holland教授提出，主要特點(diǎn)是群體搜索策略和群體（population）中個(gè)體（individual）之間的信息交換。它實(shí)際上是模擬由個(gè)體組成的群體的整體學(xué)習(xí)過(guò)程，其中每個(gè)個(gè)體對(duì)應(yīng)研究問(wèn)題的一個(gè)解。

鑒于以上算法的特點(diǎn)，本文將掃描法和遺傳算法結(jié)合以來(lái)，將VRP問(wèn)題轉(zhuǎn)換為TSP問(wèn)題求解，并且對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)。

3算法的設(shè)計(jì)

{輸入車輛調(diào)度問(wèn)題的己知條件：

輸入運(yùn)行參數(shù)，如群體規(guī)模N，終止進(jìn)化代數(shù)T和最優(yōu)染色體保留代數(shù)N，交叉概率pc，變異概率pm，執(zhí)行變異操作時(shí)的基因換位次數(shù)J，對(duì)不可行路徑的懲罰權(quán)重Pw等；

采用掃描法進(jìn)行配送線路分區(qū)，確定每個(gè)客戶點(diǎn)屬于哪輛車，車輛編號(hào)為1-m；

Whilei≤mdo

隨機(jī)產(chǎn)生初始化群體P0，當(dāng)前進(jìn)化代數(shù)t=0；

計(jì)算P0中每個(gè)個(gè)體的適應(yīng)度；

whilet<指定進(jìn)化終止代數(shù)Tdo

{將本代中適應(yīng)度最高的個(gè)體復(fù)制一個(gè)，直接進(jìn)入到新群體Pt+1中；

根據(jù)本代個(gè)體的適應(yīng)度，計(jì)算群體內(nèi)每個(gè)個(gè)體的選擇概率pi；然后根據(jù)輪盤賭方式選擇染色體復(fù)制到新群體Pt+1，使新群體的規(guī)模為N；

根據(jù)選擇概率pc，從Pt+1中隨機(jī)生成兩條染色體作父代，交叉操作生成兩條新染色體，計(jì)算四條染色體適應(yīng)度，保留兩條最優(yōu)染色體在Pt+1中；

根據(jù)選擇概率pm，從Pt+1中隨機(jī)生成一條染色體作父代，變異操作生成新染色體，計(jì)算父代和子代染色體適應(yīng)度，保留最優(yōu)染色體在Pt+1中；

計(jì)算Pt+1中每個(gè)個(gè)體的適應(yīng)度和成本；

t=t+1；

}

輸出最優(yōu)染色體的編碼和染色體的成本；

i=i+1；

計(jì)算并輸出各輛車最優(yōu)染色體的成本和。

}

4仿真實(shí)驗(yàn)

實(shí)驗(yàn)：現(xiàn)假設(shè)有n個(gè)貨物需求點(diǎn)和一個(gè)為這些需求點(diǎn)提供貨物的配送中心，配送中心有m輛汽車用于各需求點(diǎn)的貨物配送，每輛車的載重量皆為定值，假設(shè)車輛的容量為10 000，每個(gè)客戶的需求為0~10 000/7的一個(gè)隨機(jī)數(shù)。

通過(guò)實(shí)驗(yàn)遺傳算法和節(jié)約型算法的比較（如表1所示），可知：

（1）采用首先掃描后遺傳算法進(jìn)行配送路徑優(yōu)化，隨客戶點(diǎn)的增加，計(jì)算時(shí)間有所增加，但是時(shí)間變化近似線性變化，而節(jié)約型的算法，隨客戶點(diǎn)的增加，計(jì)算時(shí)間呈幾何級(jí)增長(zhǎng)，當(dāng)客戶點(diǎn)在一千個(gè)左右的時(shí)候，運(yùn)行時(shí)間超過(guò)半個(gè)小時(shí)；

（2）通過(guò)試驗(yàn)可以得出這樣的結(jié)論：若車的容量一定，使每輛車配送的客戶點(diǎn)一定，增加客戶點(diǎn)的個(gè)數(shù)對(duì)程序運(yùn)行時(shí)間影響不是很大。但是若每輛車的配送點(diǎn)增加，這樣程序的運(yùn)行時(shí)間會(huì)顯著增加，當(dāng)每輛車的客戶點(diǎn)超過(guò)500時(shí)，程序在十分鐘內(nèi)運(yùn)行不出結(jié)果。對(duì)于單車來(lái)講，采用此算法最適合的配送點(diǎn)在10, 200區(qū)間；

（3）采用不同的交叉和變異對(duì)于程序的收斂速度以及程序的準(zhǔn)確性有很大的影響；對(duì)于不同規(guī)模的線路優(yōu)化問(wèn)題，應(yīng)當(dāng)選取不同的參數(shù)值。

5結(jié)論

遺傳算法與傳統(tǒng)的算法相比的優(yōu)越性有：（1）遺傳算法能以很大的概率找到問(wèn)題的最有解，遺傳算法具有并行性，能有效地處理大規(guī)模的優(yōu)化問(wèn)題。（2）遺傳算法的結(jié)構(gòu)是開(kāi)放式的，與問(wèn)題本身無(wú)關(guān)，所以容易和其他的算法相結(jié)合，共同得到性能更好的混合算法。

參考文獻(xiàn)：

[1] Dantzig G., Ramser J. The Truck Dispatching Problem[J]. Management Sci, 1959(6):80-91.

[2] 李軍. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國(guó)物資出版社，2001.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文