基于改進節約算法的集送貨車輛路徑優化

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

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

1 概 述

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

物流配送車輛優化問題（Vehicle Routing Problem, VRP） 是由Dantzig 和Ramser 于1959 年提出的，早年此類問題只是單純的集貨或者送貨，并沒有將二者結合起來[1]。為了更好地解決實際應用中的問題，將VRP 問題擴展為帶回程取貨的車輛路徑問題（Vehicle Routing Problem with Backhauls，VRPB）[1-2]，并對其進行了分類，其中集送貨同時進行的VRP 問題（Vehicle Routing Problem with Simultaneous Delivery and Pickup，VRPSDP）[2]是指對一系列集送貨點，組織適當的行車路線，使車輛有序地通過它們，并最終返回配送中心；在滿足一定的約束條件下，使得費用最少，也稱為帶集送貨的路徑優化問題。

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

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

2 問題描述以及數學建模

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

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

目標函數：

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

3 C-W 算法的改進

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

首先，改進算法增加了數據預處理。考慮到集送貨的要求，在開始進行計算之前，首先判斷各點需求量wi和集貨量pi是否超出車輛的最大裝載容量Q，如果超出，需要在Q的范圍之內對該點單獨送集貨，而剩余部分再參加運算。

其次，下列步驟中，步驟4（點歸并）、步驟5（載貨量判斷） 和步驟6（時間窗約束時點插入規則） 針對傳統的節約算法進行了改進。具體如下：

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

步驟2 進行節約度的計算。計算所有點對（i,j）的節約度然后對計算結果進行降序排列。

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

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

（2） 若（i,j）中有一個點是回路中的首或尾而另一個點不在回路中則考慮合并計算回路的里程數，然后轉去步驟5：

①若i是回路末端，則j合并在i點之后；

②若i是回路首端，則j合并在i點之前；

③若j是回路首端，則i合并在j點之前；

④若j是回路末端，則i合并在j點之后。

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

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

（3） 當前ijk點載重量（4） 考慮到節約算法的求解過程中重量是按照歸并點逐點累加的，因此，在程序實現時，進行了假設，假設初始（滿載了所有的配送貨物），于是條件③歸納為：

當ijk=1：

因此，w1≥p1

當ijk=2：

因此，w1+w2≥p1+p2

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

步驟6 轉換時間約束為里程約束，里程約束為：

其中，ζ 為行駛速度；ζ*si為從源點到i點行駛的路程；ζ*tij=dij；ζ*Ti為i點的卸貨時間對應的里程；ζ*ETj為提前到達的里程約束；ζ*LTj為遲后到達的里程約束。

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

（3） 如果ζ*ETj＞ζ*sj＞ζ*LTj，或者ζ*ETi＞ζ*si＞ζ*LTi，則返回步驟4，取下一個點對。

4 實例驗證

案例1：

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

表1 案例1 客戶集送量

表2 案例1 客戶點對間距離

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

表3

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

案例2：

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

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

采用本文改進的節約算法、配送和集收貨物量共同作為載重量約束，無時間約束的運行結果如表6 所示。結果表明改進算法的運行里程和用車數量比常規的節約算法都得到了減少：里程數減少了138，約10.7%；用車數已經達到了最少，每條路徑都是滿載送貨，減少了用車費用和人力成本。然而，如果僅以配送量作為載重量的約束，運行結果的路徑為：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，不可能滿足集收貨物的要求。

有時間約束的運行結果如表7 所示。結果表明改進算法的運行里程和用車數量比常規的節約算法都得到了明顯減少：里程數減少了106，約7.5%；用車數減少了一輛，減少了用車費用和人力成本。

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

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

表6 無時間約束運行結果

表7 有時間約束運行結果

5 結 論

本文從改進C-W 節約算法入手，對有時間窗約束的VRPSDP 模式進行了研究，提出了以集貨量和送貨量共同作為各客戶點歸并的判斷條件，把時間窗約束轉化為里程，針對有時間約束和無時間約束不同的條件提出了不同的歸并規則，實驗表明，文中所提出的算法實現了多個目標（里程、帶集送貨、載重、時間窗） 的路徑優化，獲得了較好的優化結果。

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

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

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

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

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

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

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

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