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

孫　焰　張　喆

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

關鍵詞:C-W節(jié)約算法;車輛調度問題;AK算法

中圖分類號:TP301.6文獻標識碼: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)中的一個重要環(huán)節(jié)。配送是將貨物從物流節(jié)點送達收貨人的過程。合理選擇配送路徑,對加快配送速度、提高服務質量、降低配送成本及增加經濟效益都有較好的影響。配送規(guī)劃問題可以簡化為貨運車輛優(yōu)化調度問題(Vehicle Scheduling Problem,VSP),是指對一系列裝貨點和卸貨點,組織適當?shù)男熊嚲€路,使車輛有序地通過它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下,達到一定的目標(如里程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等)。

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

1問題描述與模型建立

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

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

minZ=FP∪P|j∈I

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

I=N每個需求點必須至少有一輛車送貨

I∩I=Φ, i≠j, 1≤i, j≤m每個需求點最多只需一輛車送貨

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

FP∪P|j∈I≤L, i∈N每輛車總行程不超過最大運距

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

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

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

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

改進的C-W算法:

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

輸出:各車輛配送點集I,I,…,I。

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

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

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

Step3:求初始可行解。首先采取單點配送,令I=j, j=1,2,…,n,令初始總運距為minz。

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

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

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

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

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

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

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

3算例

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

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

4結束語

本文在對VSP問題進行簡單描述的基礎上,對AK算法與傳統(tǒng)的C-W節(jié)約算法進行有效的結合,提出了求解該問題的一種改進算法,通過這種方法能夠避免在某些情況下C-W節(jié)約算法求解結果與最優(yōu)解相差較大的問題。然而,本算法計算復雜度為Okn,較C-W節(jié)約算法的計算次數(shù)多,k的取值可根據(jù)問題的規(guī)模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)代物流管理技術[M]. 上海:同濟大學出版社,2004.

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

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

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