带多时间窗的实时车辆路径优化问题的研究

刘志勇 蔡延光

【摘要】考虑客户的多时间窗需求，建立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—），男，湖北咸宁人，博士，广东工业大学自动化学院教授，主要从事组合优化、人工智能、决策支持系统等的研究。