基于改進(jìn)節(jié)約算法的集送貨車輛路徑優(yōu)化

閔嘉寧，金 成 （無錫太湖學(xué)院，江蘇 無錫214064）

MIN Jia-ning, JIN Cheng (Taihu University of Wuxi, Wuxi 214064, China)

1 概 述

帶集送貨的物流可以減少單集貨和單送貨情況下車輛“空跑”所帶來的消耗，減少運(yùn)輸成本，降低流通成本，增加企業(yè)效益，近年來廣泛應(yīng)用于電子商務(wù)中，成為物流行業(yè)發(fā)展的新潮流。

物流配送車輛優(yōu)化問題（Vehicle Routing Problem, VRP） 是由Dantzig 和Ramser 于1959 年提出的，早年此類問題只是單純的集貨或者送貨，并沒有將二者結(jié)合起來[1]。為了更好地解決實(shí)際應(yīng)用中的問題，將VRP 問題擴(kuò)展為帶回程取貨的車輛路徑問題（Vehicle Routing Problem with Backhauls，VRPB）[1-2]，并對(duì)其進(jìn)行了分類，其中集送貨同時(shí)進(jìn)行的VRP 問題（Vehicle Routing Problem with Simultaneous Delivery and Pickup，VRPSDP）[2]是指對(duì)一系列集送貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，并最終返回配送中心；在滿足一定的約束條件下，使得費(fèi)用最少，也稱為帶集送貨的路徑優(yōu)化問題。

VRP 屬于NP-hard 問題，實(shí)際應(yīng)用中多采用啟發(fā)式算法和元啟發(fā)式算法，其中由Clarke 和Wright 于1964 年提出的C-W節(jié)約啟發(fā)式算法由于概念清晰、容易實(shí)現(xiàn)、很受企業(yè)歡迎。但是，在實(shí)際應(yīng)用中，往往存在多個(gè)約束條件、多個(gè)優(yōu)化目標(biāo)，尤其是帶集送貨和時(shí)間窗的引入要求對(duì)C-W 節(jié)約算法進(jìn)行改進(jìn)以適應(yīng)新的需求。目前國內(nèi)對(duì)于帶集貨送貨車輛路徑規(guī)劃的研究主要有：郭耀煌、李軍[3]采用網(wǎng)絡(luò)啟發(fā)式算法進(jìn)行了研究，并提出了考慮到每項(xiàng)任務(wù)，由其集貨點(diǎn)至送貨點(diǎn)為重車行駛，故將一項(xiàng)任務(wù)由兩個(gè)點(diǎn)看成是一個(gè)點(diǎn)，稱為重載點(diǎn)，從而簡(jiǎn)化了模型的規(guī)模?；艏颜穑瑥埨赱4]把上述問題分解為兩個(gè)階段進(jìn)行求解：第一階段對(duì)每一項(xiàng)任務(wù)內(nèi)部的集貨點(diǎn)與送貨點(diǎn)進(jìn)行內(nèi)部安排行車路線；第二階段再對(duì)各項(xiàng)任務(wù)之間進(jìn)行外部安排行車路線，以此簡(jiǎn)化問題。鐘石泉，賀國光[5]提出一種改進(jìn)的禁忌算法來解決這類問題。李華[6]建立多目標(biāo)優(yōu)化模型，提出了先對(duì)各個(gè)目標(biāo)進(jìn)行無量綱處理，之后通過加權(quán)的方式將多個(gè)目標(biāo)轉(zhuǎn)化為單個(gè)目標(biāo)作為適應(yīng)度函數(shù)，用混合遺傳算法進(jìn)行仿真求解。陳鑫，王明陽，張麗華[7]采用遺傳算法，在初始種群形成之前，將各個(gè)任務(wù)的送貨點(diǎn)按時(shí)間窗進(jìn)行排序的辦法，求解了多配送中心帶軟時(shí)間窗的路徑優(yōu)化問題。馮芳媛[2]采用節(jié)約算法和禁忌搜索算法來解決多配送中心帶逆向物流的多車型裝卸混合路徑優(yōu)化問題。

研究了近年來國內(nèi)學(xué)者解決VRPSDP 的方法，較少使用節(jié)約算法單獨(dú)求解。本文根據(jù)課題需要，探索節(jié)約算法在解決這類問題中的可行性和實(shí)用性。設(shè)定送貨與集貨均無優(yōu)先權(quán)，實(shí)現(xiàn)邊配送邊集收的運(yùn)輸模式，對(duì)有時(shí)間窗帶集送貨的VRP 進(jìn)行建模；汲取已有的研究成果的精華，對(duì)節(jié)約算法進(jìn)行改進(jìn)，使得在滿足時(shí)間窗的條件下，里程數(shù)最少并盡可能最大程度地利用車輛的載重能力、使用車輛數(shù)最少；通過實(shí)例驗(yàn)證，說明算法的合理性和有效性。

2 問題描述以及數(shù)學(xué)建模

VRPSDP 問題描述為：配送中心以及n個(gè)客戶以點(diǎn)i（i=0,1,…,n）表示，其中配送中心編號(hào)為0；各點(diǎn)位置或各點(diǎn)之間距離已知，dij表示客戶i到客戶j的之間的距離；配送中心擁有足夠的運(yùn)載能力且車型一樣，各貨車的載重量為Q，客戶i的送貨量wi＜Q、集貨量pi＜Q；tij表示車輛從客戶i行駛到客戶j的時(shí)間，sj表示運(yùn)貨車輛到達(dá)客戶j的時(shí)間（也即客戶j卸/裝貨任務(wù)的開始時(shí)間），Tj為完成裝/卸貨任務(wù)所需的時(shí)間；車輛從配送中心出發(fā)，完成配送和集貨任務(wù)后裝載收集的貨物返回配送中心。要求在滿足載重約束和時(shí)間約束的前提下貨運(yùn)的最短行車路線。載重約束為：一條線路上客戶的總貨運(yùn)量（集/送貨量） 不大于貨車的載重量Q；時(shí)間約束為：運(yùn)貨車輛到達(dá)客戶j的時(shí)間sj需要在一定的時(shí)間范圍[ETj,LTj]內(nèi)，其中ETj為到達(dá)的最早時(shí)間，LTj為允許到達(dá)的最遲開始的時(shí)間；如果提前或者遲后到達(dá)，則進(jìn)行懲罰。

考慮到實(shí)際應(yīng)用中的復(fù)雜情況，做如下假設(shè)：（1） 集貨沒有專門設(shè)定時(shí)間要求，在送貨的同時(shí)完成，即，邊送貨、邊集貨；送貨可以根據(jù)實(shí)際情況，設(shè)定時(shí)間約束或不設(shè)時(shí)間約束。（2） 在滿足車輛裝載量（或容積量） 的前提條件下盡可能多的滿足客戶的集送貨量。（3） 在滿足最短行車路徑的情況下，車輛行駛里程最少、費(fèi)用最??；車輛的使用數(shù)量最少、用車啟動(dòng)費(fèi)用最少。（4） 當(dāng)運(yùn)輸車輛為多種載重量時(shí)，選擇載重量較大的作為首先調(diào)度的重量約束，以保證用車數(shù)量最少。（5） 在以配送貨物為主、集收貨物為輔的調(diào)度目標(biāo)中，只有當(dāng)車輛的裝載量空余時(shí)才能集貨，如果集貨不能完全裝載，則需要考慮集貨積壓懲罰（懲罰系數(shù)*積壓貨物重量/體積）；如果配送和收集貨物作為共同的約束條件，則不再存在積壓的問題。

目標(biāo)函數(shù)：

其中：式（1） 為目標(biāo)函數(shù)，使車輛在完成全部配送任務(wù)時(shí)所需要的最短運(yùn)行距離。式（2） 為點(diǎn)j的客戶由車輛k完成的唯一性約束。式（3） 為到達(dá)某個(gè)客戶的車輛唯一性約束。式（4） 為客戶對(duì)配送車輛的時(shí)間窗約束。式（5） 為車輛的載重約束，即某輛車所訪問的全部客戶的總送貨量和總集貨量都不能超過車輛本身的載重量，出發(fā)時(shí)車輛上都是需要配送的貨物，而返回配送中心時(shí)車輛上都是收集的貨物。式（6） 為路徑中各點(diǎn)客戶的裝載量（送集貨量之和） 不能超過車輛本身的載重量：假設(shè)，第k輛車、路徑為（0,1,…,α-1,α,…,β,0），車輛到達(dá)當(dāng)前點(diǎn)ijk=α，那么，α 點(diǎn)前（1,…,α-1）個(gè)客戶的總集貨量與第（α… β）個(gè)客戶的總送貨量之和不大于車輛的裝載量；配送和收集的貨物可以混裝。

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

C-W 算法的基本思想是：首先構(gòu)建一個(gè)從配送中心到各客戶點(diǎn)的單點(diǎn)的回路集，然后從一個(gè)回路開始，每次根據(jù)某個(gè)判別函數(shù)來確定將一個(gè)不在回路上的點(diǎn)增加進(jìn)回路，以滿足約束的要求，得到一個(gè)較滿意的配送回路，直到所有的點(diǎn)都被安排進(jìn)回路為止[8]。根據(jù)VRPSDP 的要求，對(duì)基本的C-W 算法進(jìn)行了改進(jìn)。

首先，改進(jìn)算法增加了數(shù)據(jù)預(yù)處理?？紤]到集送貨的要求，在開始進(jìn)行計(jì)算之前，首先判斷各點(diǎn)需求量wi和集貨量pi是否超出車輛的最大裝載容量Q，如果超出，需要在Q的范圍之內(nèi)對(duì)該點(diǎn)單獨(dú)送集貨，而剩余部分再參加運(yùn)算。

其次，下列步驟中，步驟4（點(diǎn)歸并）、步驟5（載貨量判斷） 和步驟6（時(shí)間窗約束時(shí)點(diǎn)插入規(guī)則） 針對(duì)傳統(tǒng)的節(jié)約算法進(jìn)行了改進(jìn)。具體如下：

步驟1 形成一個(gè)初始解。采取單點(diǎn)配送構(gòu)成各車輛配送點(diǎn)集L1,L2,…,Ln，令Li=｛i｝，i=（1,2,…,n）。

步驟2 進(jìn)行節(jié)約度的計(jì)算。計(jì)算所有點(diǎn)對(duì)（i,j）的節(jié)約度然后對(duì)計(jì)算結(jié)果進(jìn)行降序排列。

步驟3 構(gòu)建新的初始回路集L'0=? 和重量集R'0=0。

步驟4 按照節(jié)約里程△dij隊(duì)列從大到小的順序，直至隊(duì)列為?，分析點(diǎn)對(duì)（i,j）合并進(jìn)入路徑的可能性：如果隊(duì)列不為?，而（i,j）合并的可能性不存在，則轉(zhuǎn)步驟3，開始構(gòu)建一個(gè)新的路徑。點(diǎn)對(duì)（i,j）合并進(jìn)入路徑的判斷條件如下：

（2） 若（i,j）中有一個(gè)點(diǎn)是回路中的首或尾而另一個(gè)點(diǎn)不在回路中則考慮合并計(jì)算回路的里程數(shù)，然后轉(zhuǎn)去步驟5：

①若i是回路末端，則j合并在i點(diǎn)之后；

②若i是回路首端，則j合并在i點(diǎn)之前；

③若j是回路首端，則i合并在j點(diǎn)之前；

④若j是回路末端，則i合并在j點(diǎn)之后。

（3） 在有時(shí)間窗約束的情況下，若（i,j）中有一個(gè)點(diǎn)是回路中的點(diǎn)而另一個(gè)點(diǎn)不在回路中則考慮合并轉(zhuǎn)去步驟5。

步驟5 考慮配送貨和集收貨共同作為載重約束，如果滿足下列條件則轉(zhuǎn)步驟6，否則返回步驟4，取下一個(gè)點(diǎn)對(duì)；

（3） 當(dāng)前ijk點(diǎn)載重量（4） 考慮到節(jié)約算法的求解過程中重量是按照歸并點(diǎn)逐點(diǎn)累加的，因此，在程序?qū)崿F(xiàn)時(shí)，進(jìn)行了假設(shè)，假設(shè)初始（滿載了所有的配送貨物），于是條件③歸納為：

當(dāng)ijk=1：

因此，w1≥p1

當(dāng)ijk=2：

因此，w1+w2≥p1+p2

如果以配送貨物量為主約束條件、集收貨量?jī)H僅是采用“量力而為”的策略，則采用兩階段算法：第一階段，只需考慮條件（1），運(yùn)用節(jié)約算法，計(jì)算出配送路線；第二階段，對(duì)第一階段進(jìn)行分析，找出可以順路“捎帶”集收貨物的數(shù)量，然后對(duì)不能“捎帶”的集收貨物進(jìn)行積壓懲罰。

步驟6 轉(zhuǎn)換時(shí)間約束為里程約束，里程約束為：

其中，ζ 為行駛速度；ζ*si為從源點(diǎn)到i點(diǎn)行駛的路程；ζ*tij=dij；ζ*Ti為i點(diǎn)的卸貨時(shí)間對(duì)應(yīng)的里程；ζ*ETj為提前到達(dá)的里程約束；ζ*LTj為遲后到達(dá)的里程約束。

里程約束的判斷條件如下：

（3） 如果ζ*ETj＞ζ*sj＞ζ*LTj，或者ζ*ETi＞ζ*si＞ζ*LTi，則返回步驟4，取下一個(gè)點(diǎn)對(duì)。

4 實(shí)例驗(yàn)證

案例1：

假設(shè)某企業(yè)在某一區(qū)域內(nèi)建有1 個(gè)配送站點(diǎn)，每輛車的車型都為650，某一時(shí)間段有16 個(gè)需要服務(wù)的顧客，客戶的配送量和集貨量以及點(diǎn)對(duì)之間的距離見表1、2，要求在配送站點(diǎn)中合理選擇車輛并安排行駛路線使總費(fèi)用最小。

表1 案例1 客戶集送量

表2 案例1 客戶點(diǎn)對(duì)間距離

采用上述改進(jìn)的節(jié)約算法，以配送和集收貨物量共同作為載重的約束條件，得到的結(jié)果如圖1 和表3 所示。

表3

以配送貨物量作為載重量的約束條件，先求得配送路徑，然后，再分析集收貨物量的可能性、進(jìn)行懲罰處理。第一階段得到的路徑結(jié)果仍然如圖1 所示。分析集收貨物的可能性：3、7、12、14 點(diǎn)分別在各路徑的接近末端，此時(shí)配送貨物已經(jīng)基本卸載，所以裝載不超重的集收貨物是可能的。該案例的集收貨物點(diǎn)少，采用兩階段算法是可行的，但是，當(dāng)集收貨物點(diǎn)遍布在各客戶點(diǎn)時(shí)，兩階段算法幾乎是不可能的。案例2 可以說明這一點(diǎn)。

案例2：

假設(shè)某企業(yè)在某一區(qū)域內(nèi)建有1 個(gè)配送站點(diǎn)，每輛車的車型都為10 噸，某一時(shí)間段有17 個(gè)需要服務(wù)的顧客，客戶的需求量或退貨量以及點(diǎn)對(duì)之間的距離見表4 和表5，要求在配送站點(diǎn)中合理選擇車輛并安排行駛路線使總費(fèi)用最小。

表4 案例2 中各客戶的集送量

采用本文改進(jìn)的節(jié)約算法、配送和集收貨物量共同作為載重量約束，無時(shí)間約束的運(yùn)行結(jié)果如表6 所示。結(jié)果表明改進(jìn)算法的運(yùn)行里程和用車數(shù)量比常規(guī)的節(jié)約算法都得到了減少：里程數(shù)減少了138，約10.7%；用車數(shù)已經(jīng)達(dá)到了最少，每條路徑都是滿載送貨，減少了用車費(fèi)用和人力成本。然而，如果僅以配送量作為載重量的約束，運(yùn)行結(jié)果的路徑為：0-7-8-11-3-15-14-17-9-0，0-5-16-4-0，0-7-10-0，0-12-13-0，0-2-0，0-6-0，不可能滿足集收貨物的要求。

有時(shí)間約束的運(yùn)行結(jié)果如表7 所示。結(jié)果表明改進(jìn)算法的運(yùn)行里程和用車數(shù)量比常規(guī)的節(jié)約算法都得到了明顯減少：里程數(shù)減少了106，約7.5%；用車數(shù)減少了一輛，減少了用車費(fèi)用和人力成本。

上述案例表明，采用改進(jìn)的節(jié)約算法可以實(shí)現(xiàn)VRPSDP 的要求：①按照需求的送貨量和集貨量同時(shí)進(jìn)行配送和集貨。②送集貨在時(shí)間窗約束之內(nèi)。③車輛行駛里程數(shù)盡量?。ü?jié)約算法本身內(nèi)在性保證了里程數(shù)盡量?。?。④車輛數(shù)盡量少（文中載重量的約束內(nèi)在性的保證了使用車輛盡可能少）。與文獻(xiàn)[2]相比有較好的結(jié)果。但是有時(shí)間約束的優(yōu)化還不很理想，點(diǎn)2 未能進(jìn)入運(yùn)算，這是下一步研究需要解決的問題之一。

表5 案例2 中各客戶的距離

表6 無時(shí)間約束運(yùn)行結(jié)果

表7 有時(shí)間約束運(yùn)行結(jié)果

5 結(jié) 論

本文從改進(jìn)C-W 節(jié)約算法入手，對(duì)有時(shí)間窗約束的VRPSDP 模式進(jìn)行了研究，提出了以集貨量和送貨量共同作為各客戶點(diǎn)歸并的判斷條件，把時(shí)間窗約束轉(zhuǎn)化為里程，針對(duì)有時(shí)間約束和無時(shí)間約束不同的條件提出了不同的歸并規(guī)則，實(shí)驗(yàn)表明，文中所提出的算法實(shí)現(xiàn)了多個(gè)目標(biāo)（里程、帶集送貨、載重、時(shí)間窗） 的路徑優(yōu)化，獲得了較好的優(yōu)化結(jié)果。

[1] 陳志忠，楊信豐，李引珍. 逆向物流綜合回收問題的建模研究[J]. 蘭州大學(xué)學(xué)報(bào)，2011,30(4):100-105.

[2] 馮芳媛. B2C 電子商務(wù)中帶逆向物流的車輛路徑優(yōu)化問題研究[D]. 沈陽：沈陽師范大學(xué)（碩士學(xué)位論文），2011.

[3] 李軍，郭耀煌. 物流配送車輛調(diào)度理論與方法[M]. 北京：中國物資出版社，2001.

[4] 霍佳震，張磊. 有時(shí)間窗的集貨送貨一體化車輛路徑規(guī)劃啟發(fā)式算法研究[J]. 物流技術(shù)，2004(5):64-66.

[5] 鐘石泉，賀國光. 有里程和時(shí)間窗約束的一體化車輛調(diào)度智能優(yōu)化[J]. 系統(tǒng)工程與電子技術(shù)，2006,28(2):240-243.

[6] 李華. 具有同時(shí)配送和回收需求的車輛路徑問題研究[D]. 成都：西南交通大學(xué)（碩士學(xué)位論文），2012.

[7] 陳鑫，王明陽，張麗華. 有里程和軟時(shí)間窗約束的開放式多車場(chǎng)帶集送貨化車輛路徑問題研究[J]. 物流科技，2012(12):28-31.

[8] 宋偉剛，張宏霞，佟玲. 有時(shí)間窗約束非滿載車輛調(diào)度問題的節(jié)約算法[J]. 東北大學(xué)學(xué)報(bào)，2006,27(1):65-68.