劉志勇 蔡延光

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

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

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

引言

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

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

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

決策變量如下：

（1）

（2）

（3）

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

（4）

約束條件：

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

（13）

（14）

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

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

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

3.算例仿真

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

表1 客戶信息

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

4.結(jié)語(yǔ)

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

參考文獻(xiàn)

[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.

基金項(xiàng)目：國(guó)家自然科學(xué)基金（編號(hào)：61074147，61074185）

作者簡(jiǎn)介：

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

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