求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法*

张 瑾,洪 莉,戴二壮

(河南大学计算机与信息工程学院，河南 开封 475004)

1 引言

车辆路径问题VRP(Vehicle Routing Problem)是物流理论体系中一类经典的组合优化问题，随着物流业的不断发展，越来越多的VRP问题模型得以产生和发展，如带容量约束的VRP CVRP(Capacitated VRP)、带时间窗约束的VRP VRPTW(VRP with Time Windows)以及带容量和时间窗约束的VRP CVRPTW(Capacitated VRP with Time Windows)[1]等。

由于上述问题都属于NP难题，对于较大规模问题，精确算法难以在有限时间内给出最优解，因此普遍采用智能算法进行求解。现有关于CVRPTW问题的算法大致有遗传算法GA(Genetic Algorithm)、蚁群算法、禁忌搜索算法、粒子群优化PSO(Particle Swarm Optimization)算法、蝙蝠算法和狼群算法等，问题的优化目标大多为运输距离最短或时间最短，部分文献考虑了违反时间窗约束的惩罚成本。采用遗传算法GA求解的文献中，Jiang等[2]通过合理构造染色体，利用遗传算法使最优解的搜索在可行空间内进行;赵振华等[3]提出一种先考虑客户服务的先后次序，然后在此基础上构建初始种群的方法，二者都以运距最短为优化目标；李加玲等[4]在遗传算法中引入轮盘赌策略寻找可行的配送路径；黄务兰等[5]引入精英保留策略，采用客户点交叉和路段交叉算子相结合的方式以保证算法中种群的多样性，二者都以配送时间最短作为优化目标。采用蚁群算法求解的文献中，李琳等[6]在算法的不同阶段采用不同的信息素挥发策略防止算法陷入局部最优；辜勇等[7]以改进蚁群算法为主体，插入遗传操作算子作为局部优化方法，二者都以运距最短为优化目标；……