車輛路徑問題的連接點選擇節(jié)約算法①

邵俊崗，鄭芳瑜

(上海海事大學(xué)水運經(jīng)濟科學(xué)研究所 上海201306)

0 引 言

在商品經(jīng)濟高速發(fā)展的今天，高效的集中、分銷、配送顯得尤為重要.不同的商品必須由倉庫分銷到各個零售商:牛奶企業(yè)到不同的奶農(nóng)處收購牛奶，面包必須從倉庫發(fā)出到不同的零售商店或超市，不同小區(qū)的垃圾也要由車輛運送至垃圾處理廠.因此，若能對貨物做到有效地集中和配送便能使庫存保持在一個較低的水平，更能節(jié)省資源和能源，使世界發(fā)展更加可持續(xù)化.

根據(jù)最新口徑下的《2013 年中國物流運行情況通報》［1］，2013 年全國范圍內(nèi)消耗的物流總費用約10.2 萬億元，同比上年增長了9.3%，約占GDP的18%.特別突出的是運輸費用一項，高達(dá)5.4 萬億元，在物流總費用中的占比搞到52.25%之多.由此，降低物流成本顯得重要且迫切，而對車輛運輸路徑的優(yōu)化正可以降低運輸費用.

如果面包廠要向11 個不同的雜貨店配貨，理論上可能的不同路徑可達(dá)39 916 800(=11!)，在短時間內(nèi)很難找到最經(jīng)濟的優(yōu)化方案.當(dāng)只看線路圖可以排除過長的路線，但要想找到最短路線是遠(yuǎn)遠(yuǎn)無法達(dá)到的.本文介紹了著名的運用于運輸路線優(yōu)化問題的傳統(tǒng)Clarke－Wright 節(jié)約算法和允許分割配送的節(jié)約算法，針對Clarke－Wright 節(jié)約算法下運輸車輛數(shù)目已經(jīng)最優(yōu)的情況，允許分割配送的節(jié)約算法不再適用，本文提出了對傳統(tǒng)節(jié)約算法進行連接點優(yōu)化的方法來解決這一問題.

1 傳統(tǒng)節(jié)約算法

1.1 節(jié)約算法原理

Clarke G.和Wright J.W.在1964 年率先提出了Clarke－Wright 節(jié)約算法，目標(biāo)為路徑最短的條件下提出了運輸路徑優(yōu)化問題的解決方案.但是此方法只適用于車輛載重能滿足兩個目標(biāo)客戶的總需求.如圖1，有兩個目標(biāo)客戶的情況下，車輛的配送總路徑為L=2(L01+L02);如圖2，若將兩個目標(biāo)客戶串到相同的路徑中，且用同一輛車進行配送，則總路徑為L=L01+L02+L12.圖2 的配送方式比圖1 的共節(jié)約的里程△L=L01+L02－L12.如圖3，將第三個目標(biāo)客戶串到圖2 所示的配送路徑中，節(jié)約的配送里程為△L=L02+L03－L23.

1.2 傳統(tǒng)節(jié)約算法計算實例

有一家電生產(chǎn)公司，需對附近的11 個城市提供洗衣機、冰箱等.以家電公司為坐標(biāo)原點，各需求點信息如下表1:

在每輛車只能出車一次的情況下，每趟最多可以裝載16 個單位，求解最優(yōu)配送路徑.

圖1 單獨配送

圖2 混載配送

圖3 多客戶混載配送

采用節(jié)約算法求解步驟如下:根據(jù)表1 中給出的各個目標(biāo)客戶的坐標(biāo)(X，Y)(其中X 表示目標(biāo)客戶的橫坐標(biāo)，Y 表示目標(biāo)客戶的縱坐標(biāo))，利用歐式距離公式計算出配送中心與目標(biāo)客戶間的歐式距離distance，(distance =［(Xi－Xj)2+(Yi－Yj)2］1/2，其中Xi表示目標(biāo)客戶i 的橫坐標(biāo)，Yi表示目標(biāo)客戶i 的縱坐標(biāo)，i =0 表示原點);再通過Clarke－Wright 節(jié)約算法計算任意兩個目標(biāo)客戶的節(jié)約里程savingvalue(savingvalue=di0+dj0－dij，其中，dij表示目標(biāo)客戶i 和j 之間距離，i=0 表示原點)，并依照從大到小的次序進行排列，得到節(jié)約里程順序表;最后遍歷節(jié)約里程順序表，并針對車輛總載重是否超出上限來判斷是否應(yīng)該將相應(yīng)的客戶并入到配送路徑中，如果沒有超出上限，則將該客戶并入配送路徑中;否則，該配送路徑規(guī)劃結(jié)束，開始下一輛車的配送.

表1 家電公司與需求點的坐標(biāo)及需求量

第一步，根據(jù)各目標(biāo)客戶的坐標(biāo)，用Matlab7.0編程計算出各目標(biāo)客戶之間的歐式距離(在此已取整)，結(jié)果見表2:

表2 距離矩陣

第二步，由上一步得到的距離矩陣中的距離來計算，得出目標(biāo)客戶兩兩之間的節(jié)約行程，結(jié)果見表3:

表3 節(jié)約值矩陣

第三步，對節(jié)約行程按從大到小的順序進行排序，如表4 所示:

表4 節(jié)約值表

第四步，按節(jié)約值表，采用并行方式組合形成配送路線圖.

表5 傳統(tǒng)節(jié)約算法下的配送路徑

第五步，按表5 的結(jié)果，利用OriginPro 8.0 作出如下的圖4 傳統(tǒng)節(jié)約算法配送路徑圖.

圖4 傳統(tǒng)節(jié)約算法配送路徑圖

2 允許分割節(jié)約算法

2.1 節(jié)約算法的改進思路

通過上述實例可以發(fā)現(xiàn)，Clarke－Wright 節(jié)約算法在算法上有重大的缺陷:Clarke－Wright 節(jié)約算法不允許訂貨量分割.Clarke－Wright 節(jié)約算法是通過判斷串聯(lián)之后的訂貨量總和是否已經(jīng)超過車輛最大載重來決定是否進行調(diào)整.然而，這種判斷可能導(dǎo)致某條線路的配送車輛的載重量并未達(dá)到滿載，同時任何其他目標(biāo)客戶都會因為超過載重上限而不能串聯(lián)進去［2］.但是，當(dāng)貨物總量大于車輛最大載重額度時，允許分割的節(jié)約算法仍會將該客戶并入到配送路徑中，并以車輛最大載重額度來分配貨物量，另一輛車來配送尚未配送完的貨物［3］.

圖5 改進節(jié)約算法的配送路徑圖

2.2 允許分割節(jié)約算法實例

下面采用改進的分割節(jié)約算法對上述實例進行再次計算，由于步驟和上述節(jié)約算法相似，在此不再重復(fù)計算.

對比表5 和表6 的結(jié)果，兩種算法都需要配送中心用5 輛車來完成11 個客戶的配送，傳統(tǒng)節(jié)約算法下總的運輸里程為704，而改進的節(jié)約算法下總的運輸里程為823.那么從運輸里程來看，改進后的節(jié)約算法對能耗的降低沒有任何提升，反而增加能耗.

表6 改進節(jié)約算法下的配送路徑

3 0－6－2－10－－0 16 3 201 4 0－6－5－7－0 16 3 191 5 0－6－0 5 1 92合計69 14 823

3 連接點選擇節(jié)約算法

3.1 算法分析

改進的節(jié)約算法(可分割的節(jié)約算法)與傳統(tǒng)的節(jié)約算法的區(qū)別主要有以下幾點:⑴允許分割貨運量，當(dāng)貨運量總和超過車輛的載重上限時，仍然選擇串聯(lián)目標(biāo)客戶;⑵將零售商并入到一條線路中，直到該線路車輛達(dá)到載重上限;⑶當(dāng)一條線路規(guī)劃完成后，將其余的目標(biāo)客戶、節(jié)約值矩陣和配送向量組成一個新的車輛路徑規(guī)劃問題［2，4］.

圖6 優(yōu)化后的連接點選擇節(jié)約算法流程圖

從很多學(xué)者的論證中都有可分割的節(jié)約法比傳統(tǒng)節(jié)約法更能有效地縮短總的運輸里程的實例證明，但是這個例子說明不是所有的可分割節(jié)約算法都比傳統(tǒng)節(jié)約算法有效［5～6］.主要原因在于，不管如何安排運輸，根據(jù)總需求為69 噸與每輛車載重限制為16 噸，可知必須要有5 輛及以上的車輛用于運輸，而改進節(jié)約法并沒有使得運輸?shù)目傑囕v減少，但同時把零售商進行分割增加了運輸行程.

因此，對于使用傳統(tǒng)C－W 節(jié)約法下得到的已經(jīng)是最小運輸車輛的車輛配送問題而言，不能使用改進后的節(jié)約算法.在此種情況下，可以對傳統(tǒng)的節(jié)約算法進行稍加改動，會使總的運輸行程最短.其他步驟都不變，在最后步驟時，若沒有超載，將該客戶并入配送路徑中，對并入配送路徑的具體連接點進行比較分析，選擇行程最短的路徑［7］.

3.2 連接點選擇節(jié)約算法實例

優(yōu)化后的連結(jié)點選擇節(jié)約算法流程圖如下圖6.

參見實例，輪到1－3 并入已有路徑0－1－4－0 時，計算0－1－4－3－0 和0－3－1－4－0 的行程，分別為207 和188，故選擇0－3－1－4－0 為該段路徑.其他路徑同樣優(yōu)化，最終能得到的配送路徑如下表7，配送路徑圖如下圖7.

表7 連接點選擇節(jié)約算法下的配送路徑

圖7 優(yōu)化后的傳統(tǒng)節(jié)約算法配送路徑圖

4 結(jié) 語

Clarke－Wright 節(jié)約算法常用于解決車輛路徑規(guī)劃問題.傳統(tǒng)的Clarke－Wright 節(jié)約算法依照CW 算法公式計算出連接兩個目標(biāo)客戶后所節(jié)約的里程數(shù)，然后按照節(jié)約里程數(shù)從大到小的順序來判斷客戶能否串聯(lián)入當(dāng)前路徑，由此形成的最終配送路徑會可能會出現(xiàn)路徑交叉的情況.在圖4 的配送路徑圖中可以看出，路徑0－1－4－3－0 出現(xiàn)了部分交叉.而本文利用有關(guān)學(xué)者研究的改進的允許分割節(jié)約算法進行路徑規(guī)劃，從圖5 的配送路徑圖可以看出，路徑交叉的問題更加嚴(yán)重，而且運輸里程顯著增加.說明針對使用傳統(tǒng)Clarke－Wright 節(jié)約算法下得到的已經(jīng)是最小運輸車輛的配送車輛數(shù)問題而言，不能使用改進后的節(jié)約算法.

誠然，路徑交叉在一定程度上會增加配送里程［8］，從而增加了配送成本.所以本文對并入配送路徑的具體地點的連接點進行了比較分析，選擇行程最短的路徑.從圖7 中可以清楚地看到，對傳統(tǒng)節(jié)約算法進行優(yōu)化的連接點選擇節(jié)約算法可以有效避免配送路徑交叉的情況，同時總運輸里程也從原來的740 公里相應(yīng)縮短到722 公里.由此可見，針對傳統(tǒng)CW 算法得出的已經(jīng)是最小運輸車輛數(shù)的問題，改進的節(jié)約算法不再適用.此時應(yīng)用連接點選擇節(jié)約算法有效地改善了路徑交叉問題，并且運輸里程優(yōu)于傳統(tǒng)節(jié)約算法.

［1］ 2013 全國物流運行情況通報［EB/OL］.http://news.163.com/14/0307/09/9MNLD8G600014JB5.html.

［2］ 張學(xué)志，陳功玉.車輛路線安排的一種改進節(jié)約算法［J］.物流技術(shù)，2008，27(10):139 －141.

［3］ Milan Stanojevi?a，Bogdana Stanojevi?b，Mirko Vujo?evi?a.Enhanced Savings Calculation and its Applications for Solving Capacitated Vehicle Routing Problem［J］.Applied Mathematics and Computation，2013，219(20):10302–10312.

［4］ 范潔，曹俊琴.改進節(jié)約算法在電表配送路線選擇中的應(yīng)用［J］.物流工程與管理，2012，(4):102－105.

［5］ Thibaut Vidal，Teodor Gabriel Crainic，Michel Gendreau.A Uni?ed Solution Framework for Multi－attribute Vehicle RoutingProblems［J］.European Journal of Operational Research，2014，(234):658–673.

［6］ Diego Cattaruzza，Nabil Absi.A Memetic Algorithm for the Multi Trip Vehicle Routing Problem［J］.European Journal of Operational Research，2014，(236):833–848.

［7］ Anders Segerstedt.A Simple Heuristic for Vehicle Routing－A Variant of Clarkeand Wright＇s Saving Method［J］.International Journal of Production Economics(2013)，DOI:http://dx.doi.org/10.1016/j.ijpe.2013.09.017i.

［8］ Shahin Moghadam，S.M.T.Fatemi Ghomi，B.Karimi.Vehicle Routing Scheduling Problem with Cross Docking and Split Deliveries［J］.Computers and Chemical Engineering，2014，69:98–107.doi:10.1016/j.compchemeng.2014.06.015.