李 珺，郝丽艳，何奕涛，段钰蓉

（兰州交通大学电子与信息工程学院，兰州 730070）

0 概述

车辆路径问题（Vehicle Routing Problem，VRP）一直是物流配送活动中的基本问题，受到国内外学者的广泛关注。随着电子商务的发展以及客户需求的提高，企业在设计物流系统时需要在规定时间窗内完成服务，从而提高服务水平。带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）是经典VRP 问题的一个重要扩展，每个顾客有预先设定的时间窗，车辆不能早于顾客允许的最早服务时间提供服务，也不能晚于顾客允许的最晚服务时间提供服务。

求解VRPTW 问题的算法大致可以分为精确算法和启发式算法两类。精确算法在理论上可以找到问题的最优解，但由于在实际应用中消耗的空间和时间成本较大，因此计算机内存要求较高，仅适用于求解较小规模的路径优化问题。启发式算法不管是求解小规模的问题还是大规模的问题，都能够在一定范围和较短的时间内给出满意解或最优解。因此，目前相关领域的学者专注于设计不同的启发式算法寻找该问题的近似最优解，特别是对现代启发式算法的研究。文献［1］利用分布式多agent系统实现分布式求解VRPTW问题。文献［2］介绍基于量子蚁群算法的VRPTW 问题。文献［3］介绍一种求解VRPTW 问题的离散粒子群算法。文献［4］介绍改进的蚁群算法求解带时间窗的车辆路径问题。文献［5］介绍一种新的求解带时间窗车辆路径问题的遗传算法。文献［6］介绍考虑载荷约束的求解时间窗车辆路径问题的遗传算法。……