邵俊崗，鄭芳瑜

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

0 引 言

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

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

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

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

1.1 節(jié)約算法原理

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

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

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

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

圖1 單獨(dú)配送

圖2 混載配送

圖3 多客戶混載配送

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

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

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

表2 距離矩陣

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

表3 節(jié)約值矩陣

第三步，對節(jié)約行程按從大到小的順序進(jìn)行排序，如表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é)約算法的改進(jìn)思路

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

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

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

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

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

表6 改進(jìn)節(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合計(jì)69 14 823

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

3.1 算法分析

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

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

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

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

3.2 連接點(diǎn)選擇節(jié)約算法實(shí)例

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

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

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

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

4 結(jié) 語

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

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

［1］ 2013 全國物流運(yùn)行情況通報(bào)［EB/OL］.http://news.163.com/14/0307/09/9MNLD8G600014JB5.html.

［2］ 張學(xué)志，陳功玉.車輛路線安排的一種改進(jìn)節(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］ 范潔，曹俊琴.改進(jìn)節(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.