帶多時間窗的實時車輛路徑優(yōu)化問題的研究

劉志勇 蔡延光

【摘要】考慮客戶的多時間窗需求，建立RTVRPMTW問題模型。充分利用ACO和GA的優(yōu)勢，并采用了3-opt搜索、車場交換及協(xié)同機制等策略進行改進，構造了HACO。對實例進行仿真表明該算法在收斂速度和尋優(yōu)結果兩方面都優(yōu)于另外三種算法，而且穩(wěn)定性較好。

【關鍵詞】多時間窗;實時車輛路徑優(yōu)化;蟻群優(yōu)化算法;協(xié)同機制

Research on real time vehicle routing problem with multiple time windows

LIU Zhi-yong，CAI Yan-guang

（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

Abstract：Considering the multiple time windows，establishing real time vehicle routing problem with multiple time windows model.Making full use of the advantages of ant colony optimization and genetic algorithm，3-opt local search，depot exchange and collaborative mechanism were introduced to improved the algorithms performance，then the hybrid ant colony optimization was constructed.Experiments show that the algorithm is better.

Key words：multiple time windows;real time vehicle routing problem;ACO;collaborative mechanism

引言

帶時間窗的車輛路徑優(yōu)化問題（vehicle routing problem with time windows，VRPTW）屬于車輛路徑問題（vehicle routing problem，VRP）的范疇，也屬于NP-h問題，近年來，有不少學者[1-3]對VRPTW進行了深入研究，該問題一直是運籌學與組合優(yōu)化領域的前沿和熱點問題，且在現(xiàn)實生產(chǎn)生活中有著相當廣泛的應用，因而研究該問題具有現(xiàn)實意義。目前，國內外對于多時間窗VRP的研究文獻不少，但是考慮多時間窗的實時VRP（real time vehicle routing problem with multiple time windows，RTVRPMTW）的研究文獻還相當有限，本文通過提出的混合蟻群優(yōu)化算法求解該問題模型。

1.問題描述及數(shù)學模型

客戶i（i=1，2，…，l）的需求量為gi，客戶時間窗的個數(shù)，，客戶要求送貨的時間窗為[，]，等待費用為s1，延遲費用為s2，車場個數(shù)為n（n=1，2，…，N），車輛類型為h（h=1，2，…，H），車輛載重為qhgi

決策變量如下：

（1）

（2）

（3）

目標函數(shù)：

（4）

約束條件：

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

（13）

（14）

2.混合蟻群算法求解流程

混合蟻群算法的求解流程框圖如圖1所示。

圖1 混合蟻群算法的求解流程框圖

3.算例仿真

某企業(yè)有兩車場，車場A（40，30），兩種類型車輛各3輛，載重分別為35和25，固定成本分別為8和5，運輸成本為1和0.8;車場B（80，45），三種類型車輛各3輛，載重分別為35、20和25，固定成本分別為8、4和5，運輸成本分別為1、0.6和0.8?？蛻粜畔⑷绫?。最早和最晚發(fā)車時間分別為480和600個時間單位。司機工資為10個單位，里程約束為150個單位，車輛最大行駛時間為210個時間單位。服務時間為10個時間單位，早到和遲到懲罰系數(shù)分別為1和4。v=50千米/時。

表1 客戶信息

在Intel（R）Core?i5 CPU3.0GHz、內存為8.0G、win7的PC機上采用Matlab R2010b編程實現(xiàn)。針對RTVRPMTW模型，分別采用GA、TS、ACO和HACO進行仿真，各運行20次。GA參數(shù)設計：初始化種群N=20，最大迭代次數(shù)為800，交叉概率pc=0.9，變異概率pm=0.04，采用精英選擇策略，算術交叉，均勻變異。TS參數(shù)設計：最大迭代次數(shù)800，禁忌長度為10，候選解個數(shù)為80個，保留20個最小候選解。ACO參數(shù)設計：蟻群規(guī)模m=20，最大迭代次數(shù)Nc=800，q0=0.8，Q=100。通過多次實驗知當，，時蟻群優(yōu)化算法的性能最優(yōu)。4種算法求解RTVRPMTW的結果是：GA在第50代搜索到最好解為566.38，TS在第12代搜索到最好解572.55，ACO在第60代搜索到最好解566.38，而HACO在第13代搜索到最好解為566.38，可以看出本文算法的收斂速度和求解質量優(yōu)于另外三種算法。

4.結語

本文提出了基于GA和ACO兩種算法的優(yōu)點及多種改進策略的HACO，本文提出模型屬于小規(guī)模模型，研究更大規(guī)模模型及包含多種擴展特性（多周期性、服務優(yōu)先級等）的VRP及其求解方法將是下一步研究的方向。

參考文獻

[1]Simchi-Levi D，Chen X，Bramel J.The VRP with Time-Window Constraints[M]//The Logic of Logistics.Springer New York，2014： 341-357.

[2]Cattaruzza D，Absi N，F(xiàn)eillet D，et al.An Iterated Local Search for the Multi Commodity Multi Trip Vehicle Routing Problem with Time Windows[C]//ROADEF-15ème congrès annuel de la Société fran?aise de recherche opérationnelle et daide à la décision.2014.

[3]Ko? ?，Bekta? T，Jabali O，et al.A Hybrid Evolutionary Algorithm for Heterogeneous Fleet Vehicle Routing Problems with Time Windows[J].2014.

基金項目：國家自然科學基金（編號：61074147，61074185）

作者簡介：

劉志勇（1990—），男，江西新余人，碩士研究生，研究方向：物流運輸信息技術研究。

蔡延光（1963—），男，湖北咸寧人，博士，廣東工業(yè)大學自動化學院教授，主要從事組合優(yōu)化、人工智能、決策支持系統(tǒng)等的研究。