帶多時間窗的實時車輛路徑優化問題的研究

劉志勇 蔡延光

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

【關鍵詞】多時間窗;實時車輛路徑優化;蟻群優化算法;協同機制

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

引言

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

1.問題描述及數學模型

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

決策變量如下：

（1）

（2）

（3）

目標函數：

（4）

約束條件：

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

（13）

（14）

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

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

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

3.算例仿真

某企業有兩車場，車場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。客戶信息如表1。最早和最晚發車時間分別為480和600個時間單位。司機工資為10個單位，里程約束為150個單位，車輛最大行駛時間為210個時間單位。服務時間為10個時間單位，早到和遲到懲罰系數分別為1和4。v=50千米/時。

表1 客戶信息

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

4.結語

本文提出了基于GA和ACO兩種算法的優點及多種改進策略的HACO，本文提出模型屬于小規模模型，研究更大規模模型及包含多種擴展特性（多周期性、服務優先級等）的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，Feillet 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—），男，湖北咸寧人，博士，廣東工業大學自動化學院教授，主要從事組合優化、人工智能、決策支持系統等的研究。