一種解決配送規(guī)劃問(wèn)題的改進(jìn)節(jié)約算法

孫　焰　張　喆

摘要:車輛優(yōu)化調(diào)度問(wèn)題(VSP)是物流配送中廣泛存在的一類問(wèn)題,VSP問(wèn)題屬于NP-困難問(wèn)題。在描述了簡(jiǎn)單VSP模型的基礎(chǔ)上,對(duì)啟發(fā)式算法中的C-W節(jié)約算法進(jìn)行改進(jìn),將AK算法的思想運(yùn)用其中,使計(jì)算結(jié)果的優(yōu)化程度明顯提高。

關(guān)鍵詞:C-W節(jié)約算法;車輛調(diào)度問(wèn)題;AK算法

中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A

Abstract: Vehicle scheduling problem is a widespread problem in losgistic distribution, it's a NP-hard problem. The description of VSP model was given and an improvement of a heuristic method called C-W algorithm was made based on it. The optimization results was impoved significantly after using the thinking of AK algorithm.

Key words: C-W algorithm; vehicle scheduling problem; AK algorithm

物流配送是現(xiàn)代化物流系統(tǒng)中的一個(gè)重要環(huán)節(jié)。配送是將貨物從物流節(jié)點(diǎn)送達(dá)收貨人的過(guò)程。合理選擇配送路徑,對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較好的影響。配送規(guī)劃問(wèn)題可以簡(jiǎn)化為貨運(yùn)車輛優(yōu)化調(diào)度問(wèn)題(Vehicle Scheduling Problem,VSP),是指對(duì)一系列裝貨點(diǎn)和卸貨點(diǎn),組織適當(dāng)?shù)男熊嚲€路,使車輛有序地通過(guò)它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下,達(dá)到一定的目標(biāo)(如里程最短、費(fèi)用最少、時(shí)間盡量少、使用車輛數(shù)盡量少等)。

Dantzing和Ramser于1959年首次提出該問(wèn)題[1]。由于VSP問(wèn)題屬于NP-困難問(wèn)題,因此在實(shí)際中常采用啟發(fā)式算法來(lái)求解。啟發(fā)式算法的種類也很多,常見的有構(gòu)造算法(如Clarke和Wright的C-W節(jié)約算法),兩階段算法和亞啟發(fā)式算法(如模擬退火算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法等)。C-W節(jié)約算法是Clarke和Wright于1964年提出的,由于其簡(jiǎn)單性和一定程度的實(shí)用性,成為廣泛使用的配送規(guī)劃近似算法。然而,有些時(shí)候C-W算法的求解結(jié)果可能與最優(yōu)解相差較大距離(見算例)。本文結(jié)合AK算法的思路對(duì)C-W節(jié)約算法進(jìn)行改進(jìn),期望使節(jié)約算法更加實(shí)用。

1問(wèn)題描述與模型建立

問(wèn)題描述:有一個(gè)車場(chǎng)0,擁有m輛容量為W的車輛,第k輛車的最大運(yùn)距為L(zhǎng),現(xiàn)有i項(xiàng)貨運(yùn)任務(wù)需要完成,每輛車所運(yùn)送的貨物量不超過(guò)其載重量并且走行路程不超過(guò)其運(yùn)距,每個(gè)需求點(diǎn)必須有且只需一輛車送貨。設(shè)N=1,2,…,n, N=1,2,…,m,I,I,…I是自然數(shù)集N=1,2,…,n的一個(gè)分劃(I為第j輛車的送貨點(diǎn)集),FP,P,…,P為過(guò)P,P,…,P個(gè)點(diǎn)的最小回路長(zhǎng)。

配送規(guī)劃的集合劃分模型表示[2]為:

minZ=FP∪P|j∈I

s.t.I?奐N, j∈N

I=N每個(gè)需求點(diǎn)必須至少有一輛車送貨

I∩I=Φ, i≠j, 1≤i, j≤m每個(gè)需求點(diǎn)最多只需一輛車送貨

R≤W, i∈N 每輛車總載重不超過(guò)載重限制

FP∪P|j∈I≤L, i∈N每輛車總行程不超過(guò)最大運(yùn)距

其中,用車數(shù)k=SignI;第j輛車的送貨點(diǎn)為I, j=1,2,…,m; 初始載貨為R。

2改進(jìn)的C-W節(jié)約算法

AK算法是一種啟發(fā)式的搜索算法,一般被用來(lái)解決0-1背包問(wèn)題。算法的基本思想是,首先將最多k件物品放入背包,如果這k件物品的總重大于包裹容量,則放棄它。否則,剩余容量再按物品重量從大到小的順序裝

入[3]。C-W節(jié)約算法中合并配送路徑是從節(jié)約里程最大的點(diǎn)對(duì)開始合并,現(xiàn)將AK算法運(yùn)用其中,首先選擇任意小于等于k對(duì)的點(diǎn)對(duì),如滿足合并條件則進(jìn)行合并,而后再按節(jié)約里程從大到小的順序合并其他點(diǎn)對(duì)。針對(duì)從點(diǎn)對(duì)集中挑出不超過(guò)k對(duì)的點(diǎn)對(duì)的不同組合形成不同的方案,并比較每個(gè)方案的目標(biāo)值,選擇其中的最優(yōu)的一個(gè)形成最終配送方案。

改進(jìn)的C-W算法:

輸入:需求點(diǎn)集N=1,2,…,n,各點(diǎn)需求量為R,各點(diǎn)間最短距離C,首先考慮合并的點(diǎn)對(duì)最大個(gè)數(shù)k,車輛集合N=1,2,…,m,各車輛最大載重量W,最大運(yùn)距L;

輸出:各車輛配送點(diǎn)集I,I,…,I。

Step1:將N按W從大到小排序,使得:W≥W≥…≥W,若m

Step2:對(duì)于所有的客戶對(duì)i,j,采用下式計(jì)算節(jié)約里程S的值:S=C+C-C,令M

=S|S>0; i,j=1,2,…,n,并把集合M內(nèi)的元素S按從大到小的順序排列。

Step3:求初始可行解。首先采取單點(diǎn)配送,令I(lǐng)=j, j=1,2,…,n,令初始總運(yùn)距為minz。

Step4:從集合M中任意取出不多于k個(gè)的元素組成子集T,若M中元素個(gè)數(shù)為r,則子集T共有q=C+C+…+C種,對(duì)于每種子集T執(zhí)行下面的步驟:

(1)對(duì)于子集T中的每個(gè)S,判斷i和j合并的可能性(是否滿足裝載限制條件、最大運(yùn)輸距離約束、不在同一路徑內(nèi)以及合并次數(shù)不超過(guò)2),若不滿足則跳出本次循環(huán),繼續(xù)從下一個(gè)子集T開始判斷,若所有S均滿足,則分別合并各個(gè)S中的i和j,構(gòu)成新組合線路。

(2)考慮集合M中除去子集T后的第一個(gè)元素S,判斷i和j合并的可能性,若不滿足則從集合M中消去

S,若滿足則合并i和j,若M=Φ,則轉(zhuǎn)到步驟(3),否則重新執(zhí)行步驟(2)。

(3)計(jì)算總運(yùn)距Z=FP∪P|j∈I。

(4)如果minz>Z,則令minz=Z,并記錄此時(shí)各車輛的配送點(diǎn)集I,I,…,I。

Step4執(zhí)行q次后算法結(jié)束。此算法的時(shí)間復(fù)雜度為Okn。

3算例

某配送中心某天有6個(gè)客戶的配送任務(wù),各任務(wù)貨運(yùn)量為R(見圖1、表1),配送中心現(xiàn)有載重量為4t的貨車5輛,最大運(yùn)距為45km,車輛由配送中心0出發(fā),各點(diǎn)之間的距離由表2給出。

用傳統(tǒng)C-W節(jié)約算法計(jì)算,合并2、3點(diǎn),最終得到0-2-3-0、0-1-6-0、0-4-0、0-5-0,共用4輛車,總里程為109km。用改進(jìn)后的方法計(jì)算,得到0-3-4-0,0-1-2-0,0-5-6-0,共用3輛車,總里程為96km。改進(jìn)后的算法在優(yōu)化程度上明顯提高。

4結(jié)束語(yǔ)

本文在對(duì)VSP問(wèn)題進(jìn)行簡(jiǎn)單描述的基礎(chǔ)上,對(duì)AK算法與傳統(tǒng)的C-W節(jié)約算法進(jìn)行有效的結(jié)合,提出了求解該問(wèn)題的一種改進(jìn)算法,通過(guò)這種方法能夠避免在某些情況下C-W節(jié)約算法求解結(jié)果與最優(yōu)解相差較大的問(wèn)題。然而,本算法計(jì)算復(fù)雜度為Okn,較C-W節(jié)約算法的計(jì)算次數(shù)多,k的取值可根據(jù)問(wèn)題的規(guī)模n和計(jì)算機(jī)的速度來(lái)確定。

參考文獻(xiàn):

[1]Clarke G, Wright J. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operation Re, earch, 1964,12(4):12-18.

[2] 孫焰. 現(xiàn)代物流管理技術(shù)[M]. 上海:同濟(jì)大學(xué)出版社,2004.

[3] 游維. 基于貪婪的0/1背包問(wèn)題算法研究[J]. 計(jì)算機(jī)與現(xiàn)代化,2007(4):11-12.

[4] 朱曉蘭,趙一飛. C-W節(jié)約算法在裝配企業(yè)采購(gòu)物流中的應(yīng)用[J]. 上海交通大學(xué)學(xué)報(bào),2007,41(9):1422.

[5] 張建勇,郭耀煌,李軍. 一種具有模糊費(fèi)用系數(shù)的VSP的修正C-W節(jié)約算法[J]. 西南交通大學(xué)學(xué)報(bào),2004,39(3):281-282.