軟硬時間窗共存裝卸一體化車輛路徑問題的混合離散粒子群優化算法

周　蓉,　沈維蕾

(合肥工業大學 機械與汽車工程學院,安徽 合肥　230009)

?

軟硬時間窗共存裝卸一體化車輛路徑問題的混合離散粒子群優化算法

周蓉,沈維蕾

(合肥工業大學 機械與汽車工程學院,安徽 合肥230009)

文章針對軟硬時間窗共存裝卸一體化車輛路徑問題(vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows,VRPSDPCSHTW)建立了包含車輛固定出行成本、運輸成本和懲罰成本的數學模型,提出了一種混合離散粒子群優化算法。針對基本離散粒子群算法容易早熟收斂而陷入局部最優等問題,內嵌一種變鄰域下降局域搜索方法,并在一定概率下執行以加強種群搜索能力，最后通過3個算例的仿真分析進行了算法驗證。

車輛路徑問題;裝卸一體化;軟硬時間窗共存;粒子群算法;變鄰域下降搜索

帶時間窗裝卸一體化車輛路徑問題(vehicle routing problem with simultaneous delivery and pickup and time windows,VRPSDPTW)是車輛路徑問題的一類重要擴展。該問題涉及的客戶同時具有送貨和取貨2種需求,并且要求服務車輛在規定的時間窗內將需求的貨物送到,將待取的貨物取走。如果車輛在客戶要求的時間窗外到達,則存在2種情況:① 提前到達必須等待,遲到則拒絕服務,這種情況稱為硬時間窗問題;② 提前到達必須等待,遲到接受服務,但無論早到或遲到都將按照違反時間的長短進行懲罰,這種情況稱為軟時間窗問題。現實中，不同客戶對車輛服務的時間約束條件不同而使得軟硬時間窗共同存在的情形經常出現,如客戶的常規儲備貨物訂貨與緊急訂單需求供貨,前者通常是軟時間窗約束,后者則是硬時間窗約束。這類問題即為軟硬時間窗共存裝卸一體化車輛路徑問題(vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows,VRPSDPCSHTW)。

國內外有關VRPSDPTW的研究較多,而對VRPSDPCSHTW的研究較少。VRPSDPTW的求解算法大多集中在啟發式和元啟發式算法的研究[1]。文獻[2-9]對軟、硬時間窗問題分別進行了深入地研究。文獻[4]對帶軟時間窗的裝卸一體化車輛路徑問題進行了求解,結果證明改進模擬退火算法比文獻[2]的模擬退火算法效果更好;文獻[6]對帶硬時間窗的裝卸一體化車輛路徑問題進行了研究,并證明了混合遺傳啟發式算法比文獻[2]的2種算法具有更好的求解性能。此外,針對軟硬時間窗共存的車輛路徑問題的研究并不多。文獻[10]建立了軟硬時間窗共存的純配送車輛路徑問題的數學模型,并證明了其提出的改進遺傳算法性能的優越性;文獻[11]研究了部分客戶具有軟時間窗或硬時間窗約束的小規模貨物配送路線問題,并結合Dijkstra算法和最小權匹配算法進行求解。

粒子群優化(particle swarm optimization,PSO)算法是一種基于群體智能的自適應優化算法,在許多車輛路徑問題的求解應用中已被證明具有良好的優化性能[12-15]。本文提出一種混合離散粒子群算法,將基本PSO與變鄰域降序局域搜索相結合,實現在PSO完成全局空間搜索的同時進行隨機化深度搜索以提高解的質量。

1　問題描述及模型

VRPSDPCSHTW描述如下:多臺服務車輛裝載客戶需要的貨物從物流中心出發,在客戶規定的時間內送至各客戶處,并將客戶供應的貨物在規定時間內從各客戶處取走送至物流中心;每個客戶位置一定,貨物需求量和供應量一定;每輛車的載重量一定,1次配送最大行駛距離一定;部分客戶的服務時間窗約束為軟時間窗,其余客戶為硬時間窗;要求合理安排車輛配送路線,使目標函數得到優化,并滿足以下約束條件:① 容量限制,即配送過程中配送車輛載貨量不超過其最大載重量;② 行駛距離限制,即每條配送路徑長度不超過車輛一次配送最大行駛距離;③ 每個客戶需求的貨物必須送到,供應的貨物必須取走。本文以總配送成本最小為目標,研究單一物流中心問題。

根據上述描述,假設物流中心共有N個客戶點,i、j為各客戶的編號,0為物流中心編號;各客戶點配送需求量為di,貨物供應量為pi,單車最大裝載量為Q;各客戶點間距離為cij,各點服務時間為si,物流中心到客戶點i的距離為c0i;單車單位行駛距離成本為g,單車單次出行成本為f,單車最大行駛距離為L;所用車輛數為K,車輛k到達客戶點i的時間為Tik,在節點i的等待時間為tik,車輛k在i、j間的行駛時間為tijk,車輛k離開客戶點i時車上載重量為Uik;客戶點i的時間窗為[TEi,TLi]。若客戶i為軟時間窗約束,車輛k提前到達的懲罰因子為w1i,遲到懲罰因子為w2i。若客戶i為硬時間窗約束,車輛k遲到的懲罰因子為M(M為一個很大的正數)。

本文以總配送成本最小為目標，建立VRPSDPCSHTW混合整數規劃模型如下：

(1)

滿足如下約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(1)式為考慮了車輛固定成本、運輸成本及包含了軟硬時間窗懲罰項的總配送成本最小目標,其中ei、ei′分別為節點i的軟、硬時間窗性質,當ei=1且ei′=0時節點i為軟時間窗約束,當ei′=1且ei=0時節點i為硬時間窗約束;(2)式表示每個客戶都必須被服務1次,且每個客戶僅由1輛車來服務;(3)式表示所有路徑數不超過車輛總數K;(4)式為流量守恒式;(5)式表示車輛在行駛過程中,在任一客戶點的載重量都不能超過車容量Q;(6)式和(7)式用來限制每輛車的總配送裝載量與總供應裝載量都不得超過車容量Q;(8)式保證每輛車的配送距離不得超過車輛最大行駛距離;(9)式表示車輛k到達節點i的時間;(10)式表示車輛k提前到達節點i的等待時間;(11)式表示硬時間窗約束;(12)式表示決策變量為0或1的整數限制式。

2　算法設計

2.1離散粒子群算法基本原理

PSO算法是一種受到鳥群覓食行為啟發的進化算法,通過個體間信息互動使群體達到最優。基本PSO算法適用于連續問題優化求解,而實際工程組合優化問題一般為離散域問題,因而出現了重新定義PSO算法操作算子的DPSO離散策略[16]。DPSO用基于問題的一個排列作為粒子的一個位置,用問題的所有排列構成問題的搜索空間,并借鑒進化算法的操作方式,通過遺傳變異和交叉操作實現3部分信息的綜合影響,具體位置更新公式[14]為:

(13)

2.2混合離散粒子群算法

本文提出一種混合離散粒子群算法(HDPSO),該算法將PSO算法與局域搜索相結合求解VRPSDPCSHTW。混合算法的本質在于局域搜索作為個體粒子的一種概率變異操作,即在PSO算法中以一定概率執行局域搜索,算法步驟如下。

(1) 初始化種群參數Ps、變異概率w、交叉概率c1和c2、局域搜索概率pLS、最大迭代次數IteMax、全局極值連續未更新最大次數gSucNum。

(3) 判斷是否滿足終止條件。若gNotImpv> gSucNum且t> Itemax，則滿足終止條件,轉步驟(5);否則不滿足終止條件,轉步驟(4)。

(5) 輸出全局極值粒子gX、全局極值gCOST以及最優配送方案。

2.2.1解的表示、解碼與評價

(1) 解的表示。本文采用文獻[17]提出的基于客戶直排大路徑解表示方法。對于具有N個客戶的VRPSDPCSHTW,直接產生N個1 ～N之間互不重復自然數的排列而形成一條大路徑,表示客戶順序,然后在大路徑最前面加上0(表示物流中心)形成帶物流中心的大路徑。

(2) 解碼。深度優先搜索方法是一種大路徑分割方法[18],本文根據研究問題的約束條件,包括車輛的最大載重量約束、車輛一次服務的最大行駛距離約束以及客戶要求服務的時間窗約束,對深度優先搜索大路分割方法稍作修改,使其適用于VRPSDPCSHTW。

(3) 解的評價。本文以目標函數值Z作為解的評價值。

2.2.2種群初始化

本文采用改進節約法和隨機產生2種方法構造初始種群。改進節約法是在C-W節約法基礎上,綜合考慮車輛總行駛距離、時間窗、同時取送貨以及車輛容量限制等約束因素,重新定義節約值[19]。采用該改進節約法時,通過設定不同的參數取值產生一定數量的初始大路徑解,剩余的初始種群采用隨機方法生成。

2.2.3位置更新準則

采用(13)式實現粒子的位置更新,具體更新規則為:當變異概率小于或等于w時執行自身變異操作,否則不執行;當個人交叉概率小于或等于c1時與個人極值執行F2交叉操作,否則不執行;當全局交叉概率小于或等于c2時與全局極值執行F3交叉操作,否則不執行。

變異操作采用兩點插入式變異,即任意選擇變異粒子中的2個位置,變異時首先將變異粒子中2個位置之間的所有元素按原順序放置到最前面,然后依次按原順序插入第1個位置前的所有元素、所選擇2個位置上的元素、第2個位置后的所有元素,便得到變異后粒子。

本文采用PTL兩點交叉操作[14],可以使相同序列交叉后得到不同的新序列。

2.2.4局域搜索

本文以兩點換位[2]、2-OPT 2種鄰域機制為基礎,設計了一種簡單的變鄰域下降局域搜索方法,其搜索流程為:首先對局域搜索粒子采用兩點換位機制,如果交換后的新粒子目標函數值比交換前降低,則以新粒子位置代替交換前的粒子位置,否則執行2-OPT鄰域機制。

3　實驗計算和結果分析

3.1算例選取及實驗參數設置

選取文獻[4]的單純軟時間窗算例作為算例1,文獻[2]與文獻[6]的單純硬時間窗算例作為算例2,根據文獻[4]的算例修改后的軟硬時間窗共存算例作為算例3。其中,算例1要求以配送總里程最短為目標安排車輛配送路線;算例2要求以配送總距離最短為目標安排車輛配送路線;算例3是在算例1的基礎上,隨機選取客戶點3、8、14將其設為硬時間窗約束,其余客戶點仍為軟時間窗約束,時間窗數據不改變,以配送總里程最短為優化目標。

經測試設置參數為:Ps=20,pLS=0.3,w=0.2,c1=c2=0.6，最大迭代次數IteMax=1 000,全局極值連續未更新最大次數gSucNum=20。

3.2計算結果分析

3.2.1算例1分析

算例1的10次計算平均結果見表1所列,其中“偏差百分比”的計算公式為:

偏差百分比=

表1　算例1分析結果

由表1可知,與文獻[4]提出的SA相比,本文算法求得的近似最優解更好、平均值更優,但本文算法比SA的平均等待及遲到時間要長一些。該問題的改善可以通過改變相應權重來減少相應時間,如增大等待/遲到懲罰因子來減少等待/遲到時間。

3.2.2算例2分析

算例2的平均計算結果見表2所列。由表2可以看出,本文算法得到的最優配送距離最短、使用車輛數最少。因此在求解單純硬時間窗車輛路徑問題時,本文算法的性能優于文獻[6]提出的HGHA、文獻[2]提出的Tabu和SA等算法。本文算法得到的近似最優解共有5條配送路徑:0-6-26-40-20-21-1-27-7-0;0-33-2-3-11-31-28-0;0-9-29-38-18-30-10-23-36-16-22-0;0-13-25-24-37-17-39-19-4-5-35-15-0;0-14-34-8-32-12-0。累積等待時間為29.38 h,累積遲到時間為0。

表2　算例2分析結果

3.2.3算例3分析

本文算法和文獻[10]算法對算例3平均計算結果的對比分析見表3所列,其中偏差百分比計算方式同表1,成本標準差、里程標準差分別為10次計算結果的總配送成本標準偏差、總配送里程標準偏差。由表3可知,無論是以總配送里程最短還是以總配送成本最小為目標,本文算法在尋優質量、計算速度以及計算穩定性方面都比文獻[10]的GA算法更好。采用本文算法得到該問題的最優配送里程為109.3 km,總配送成本為192.2元,對應最優配送路線為:0-14-8-0;0-6-20-1-7-12-0;0-9-18-11-10-3-2-0;0-13-19-17-16-4-5-15-0。累積等待時間為1.27 h,累積遲到時間為0。

表3　算例3平均計算結果的對比分析

4　結　　論

本文構建了軟硬時間窗共存的裝卸一體化車輛路徑問題模型,提出了求解該模型的混合離散粒子群算法,將變鄰域下降局域搜索方法與基本離散粒子群算法相結合,有效避免了粒子群算法早熟收斂、陷入局部最優。通過單純的軟、硬時間窗問題及軟硬時間窗共存問題3個算例的仿真測算,驗證了本文設計算法的求解性能。本文算法對于具有不同時間約束服務的物流配送和取貨優化問題具有一定的指導意義。

[1]郎茂祥.物流配送車輛調度問題的模型和算法研究[D].北京:北方交通大學,2002.

[2]PARRAGH S N,DOERNER K F,HARTL R F.A survey on pickup and delivery problems:part Ⅰ:transportation between customers and depot [J].Journal Für Betriebswirtschaft,2008,58(1):21-51.

[3]祁文祥,陸志強,孫小明.帶軟時間窗的集貨與送貨多車輛路徑問題節約算法[J].交通運輸工程學報,2010,10(2):99-103,109.

[4]鄧愛民,毛超,周彥霆.帶軟時間窗的集配貨一體化VRP改進模擬退火算法優化研究[J].系統工程理論與實踐,2009,29(5):186-192.

[5]張麗艷,龐小紅,夏蔚軍,等.帶時間窗車輛路徑問題的混合粒子群算法[J].上海交通大學學報,2006,40(11):1890-1894,1900.

[6]胡大偉,陳誠,王來軍.帶硬時間窗車輛路線問題的混合遺傳啟發式算法[J].交通運輸工程學報,2007,7(5):112-117.

[7]趙達,李軍,馬丹祥,等.求解硬時間窗約束下隨機需求庫存-路徑問題的優化算法[J].運籌與管理,2014,23(1):26-32,38.

[8]龍汀,潘若愚.蟻群算法求解帶時間窗的配送路徑問題[J].合肥工業大學學報(自然科學版),2008,31(7):1042-1046.

[9]LAI M Y,CAO E B.An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows[J].Engineering Applications of Artificial Intelligence,2010,23(2):188-195.

[10]史昊,何俊生,馬暢.求解軟硬時間窗共存配送路徑問題的改進遺傳算法[J].山東交通學院學報,2013,21(2):14-18.

[11]楊容浩,范俊波,楊佳,等.一種帶有時間窗的貨物配送路線設計算法[J].交通運輸工程與信息學報,2005,3(1):30-35.

[12]張其亮,陳永生.基于混合粒子群-NEH算法求解無等待柔性流水車間調度問題[J].系統工程理論與實踐,2014,34(3):802-809.

[13]邱晗光,張旭梅.基于改進粒子群算法的開放式定位-運輸路線問題研究[J].中國機械工程,2006,17(22):2359-2361.

[14]PAN Q K,TASGETIREN M F,LIANG Y C.A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J].Computers and Operations Research,2008,35(9):2807-2839.

[15]AI T J,KACHITVICHYANUKUL V.A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J].Computers and Operations Research,2009,36(5):1693-1702.

[16]郭文忠,陳國龍,陳振.離散粒子群優化算法研究綜述[J].福州大學學報(自然科學版),2011,39(5):631-638.

[17]PRINS C.A simple and effective evolutionary algorithm for the vehicle routing problem [J].Computers and Operations Research,2004,31(12):1985-2002.

[18]DUHAMEL C,LACOMME P,PRODHON C.Efficient frameworks for greedy split and new depth first search split procedures for routing problems[J].Computers and Operations Research,2011,38(4):723-739.

[19]莊英群.應用禁忌搜索法于混合送收貨之車輛途程問題[D].臺中:逢甲大學,2003.

(責任編輯胡亞敏)

Hybrid discrete particle swarm optimization algorithm for vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows

ZHOU Rong, SHEN Weilei

(School of Machinery and Automobile Engineering, Hefei University of Technology, Hefei 230009, China)

In this paper, a general mathematical model of the vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows(VRPSDPCSHTW), which contains fixed cost, travel cost and punished cost of vehicles, was established. And a hybrid discrete particle swarm optimization algorithm was proposed. In order to solve the problems of premature convergence and easily falling into local minimum in the basic discrete particle swarm optimization algorithm, a simple variable neighborhood descent search algorithm as a local search procedure was embedded in the basic algorithm and was carried out under a certain probability. Finally, the performance of the proposed method was examined by three numerical cases.

vehicle routing problem; simultaneous delivery and pickup; coexistence of soft and hard time windows; particle swarm optimization; variable neighborhood descent search

2015-03-31；

2015-05-04

國家自然科學基金資助項目(71071046)

周蓉(1977-),女,四川德陽人,博士,合肥工業大學講師.

10.3969/j.issn.1003-5060.2016.08.004

TP18

A

1003-5060(2016)08-1022-05