張國英 林賢茂
摘要:配送是物流系統(tǒng)中一個直接與消費(fèi)者相連的重要環(huán)節(jié),對配送系統(tǒng)進(jìn)行優(yōu)化,可以提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化,因此配送系統(tǒng)的優(yōu)化問題顯得尤為重要。進(jìn)行配送系統(tǒng)優(yōu)化,主要是配送車輛調(diào)度的優(yōu)化。文章在全面分析研究物流配送業(yè)務(wù)特點(diǎn)的基礎(chǔ)上,針對配送中的核心問題——車輛調(diào)度優(yōu)化問題進(jìn)行了深入的研究,建立了單源點(diǎn)物流配送車輛調(diào)度優(yōu)化問題的數(shù)學(xué)模型,并運(yùn)用遺傳算法對其進(jìn)行求解,仿真實(shí)例證明了該方法的有效性。
關(guān)鍵詞:物流配送;車輛調(diào)度;遺傳算法
中圖分類號:U116.2文獻(xiàn)標(biāo)識碼: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)度問題于1959年由Dantzig和Ramser提出,國外一般稱之為Vehicle Routing Problem(VRP)[1]。車輛調(diào)度問題是指為服務(wù)于已知的一組顧客的一個車隊,設(shè)計一組開始和結(jié)束于一個中心出發(fā)點(diǎn)的最小費(fèi)用路徑。每個顧客只能被服務(wù)一次,而且一個車輛服務(wù)的顧客數(shù)不能超過它的能力。VRP已被證明是一個NP問題。
VRP問題的研究起步較早,求解方法也非常豐富,基本上可以分為精確算法和啟發(fā)式算法兩大類[2]。由于VRP問題是強(qiáng)NP難題,高效的精確算法存在的可能性不大,所以尋找近似算法是必要和現(xiàn)實(shí)的,本論文在建設(shè)物流配送體系、改進(jìn)遺傳算法的應(yīng)用等方面進(jìn)行了新的探索與嘗試,主要工作在于:
(1)將改進(jìn)遺傳算法應(yīng)用于物流配送優(yōu)化中實(shí)際問題的求解,并采用計算機(jī)語言完成對其算法的實(shí)現(xiàn);
(2)通過實(shí)證分析,改進(jìn)遺傳算法用于物流配送優(yōu)化的效果。
1問題描述
典型的VRP問題可以描述為:從某物流中心用多臺配送車輛向多個客戶送貨,每個客戶的位置和貨物需求量一定,每輛配送車輛的載重量一定,其一次配送的最大行駛距離一定,要求合理安排車輛配送路線,使目標(biāo)函數(shù)得到優(yōu)化。
2掃描法和遺傳算法介紹
制定從一個物流中心向多個用戶運(yùn)送貨物的配送計劃時,必須考慮每輛車的運(yùn)載能力和行駛距離及時間等的限制。掃描法是一種能較好地解決配送路線問題的方法。
遺傳算法最早由美國密切根大學(xué)(Michigan)的Holland教授提出,主要特點(diǎn)是群體搜索策略和群體(population)中個體(individual)之間的信息交換。它實(shí)際上是模擬由個體組成的群體的整體學(xué)習(xí)過程,其中每個個體對應(yīng)研究問題的一個解。
鑒于以上算法的特點(diǎn),本文將掃描法和遺傳算法結(jié)合以來,將VRP問題轉(zhuǎn)換為TSP問題求解,并且對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)。
3算法的設(shè)計
{輸入車輛調(diào)度問題的己知條件:
輸入運(yùn)行參數(shù),如群體規(guī)模N,終止進(jìn)化代數(shù)T和最優(yōu)染色體保留代數(shù)N,交叉概率pc,變異概率pm,執(zhí)行變異操作時的基因換位次數(shù)J,對不可行路徑的懲罰權(quán)重Pw等;
采用掃描法進(jìn)行配送線路分區(qū),確定每個客戶點(diǎn)屬于哪輛車,車輛編號為1-m;
Whilei≤mdo
隨機(jī)產(chǎn)生初始化群體P0,當(dāng)前進(jìn)化代數(shù)t=0;
計算P0中每個個體的適應(yīng)度;
whilet<指定進(jìn)化終止代數(shù)Tdo
{將本代中適應(yīng)度最高的個體復(fù)制一個,直接進(jìn)入到新群體Pt+1中;
根據(jù)本代個體的適應(yīng)度,計算群體內(nèi)每個個體的選擇概率pi;然后根據(jù)輪盤賭方式選擇染色體復(fù)制到新群體Pt+1,使新群體的規(guī)模為N;
根據(jù)選擇概率pc,從Pt+1中隨機(jī)生成兩條染色體作父代,交叉操作生成兩條新染色體,計算四條染色體適應(yīng)度,保留兩條最優(yōu)染色體在Pt+1中;
根據(jù)選擇概率pm,從Pt+1中隨機(jī)生成一條染色體作父代,變異操作生成新染色體,計算父代和子代染色體適應(yīng)度,保留最優(yōu)染色體在Pt+1中;
計算Pt+1中每個個體的適應(yīng)度和成本;
t=t+1;
}
輸出最優(yōu)染色體的編碼和染色體的成本;
i=i+1;
計算并輸出各輛車最優(yōu)染色體的成本和。
}
4仿真實(shí)驗
實(shí)驗:現(xiàn)假設(shè)有n個貨物需求點(diǎn)和一個為這些需求點(diǎn)提供貨物的配送中心,配送中心有m輛汽車用于各需求點(diǎn)的貨物配送,每輛車的載重量皆為定值,假設(shè)車輛的容量為10 000,每個客戶的需求為0~10 000/7的一個隨機(jī)數(shù)。
通過實(shí)驗遺傳算法和節(jié)約型算法的比較(如表1所示),可知:
(1)采用首先掃描后遺傳算法進(jìn)行配送路徑優(yōu)化,隨客戶點(diǎn)的增加,計算時間有所增加,但是時間變化近似線性變化,而節(jié)約型的算法,隨客戶點(diǎn)的增加,計算時間呈幾何級增長,當(dāng)客戶點(diǎn)在一千個左右的時候,運(yùn)行時間超過半個小時;
(2)通過試驗可以得出這樣的結(jié)論:若車的容量一定,使每輛車配送的客戶點(diǎn)一定,增加客戶點(diǎn)的個數(shù)對程序運(yùn)行時間影響不是很大。但是若每輛車的配送點(diǎn)增加,這樣程序的運(yùn)行時間會顯著增加,當(dāng)每輛車的客戶點(diǎn)超過500時,程序在十分鐘內(nèi)運(yùn)行不出結(jié)果。對于單車來講,采用此算法最適合的配送點(diǎn)在10, 200區(qū)間;
(3)采用不同的交叉和變異對于程序的收斂速度以及程序的準(zhǔn)確性有很大的影響;對于不同規(guī)模的線路優(yōu)化問題,應(yīng)當(dāng)選取不同的參數(shù)值。
5結(jié)論
遺傳算法與傳統(tǒng)的算法相比的優(yōu)越性有:(1)遺傳算法能以很大的概率找到問題的最有解,遺傳算法具有并行性,能有效地處理大規(guī)模的優(yōu)化問題。(2)遺傳算法的結(jié)構(gòu)是開放式的,與問題本身無關(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]. 北京:中國物資出版社,2001.
注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文