摘要：针对时间窗约束下的车辆路径问题（VRPTW）建立了数学模型，将VRPTW的车辆数和距离优化视为多目标优化问题，利用遗传算法和Pareto评等方法进行了算法设计和求解，并以Solomen基准数据进行了实例对比和验证，结果表明：本文方法与目前已知文献中的最优结果相比具有竞争优势。

关键词：公路运输；车辆路径；时间窗约束；Pareto评等方案；Solomen基准

0引言

带时间窗约束的车辆路径问题（VRPTW）是车辆路径问题的扩展，它是典型的多目标组合优化问题，已被证明是一个NP难题。近年来，模拟退火算法、禁忌搜索算法、遗传算法等启发式方法在解决此类问题中发挥了积极的作用。文献[1] 中，W.C. Chiang and R.Russell研究了基于模拟退火和禁忌搜索的混合算法。文献[2] 中，J.Y. Potvin and J.M.Rousseau研究了两阶段禁忌搜索算法，第一阶段通过改变路径上的客户来减小车辆数，第二阶段客户交换使总费用最小。文献[3] 中，H.Gehring and J.Homberger研究了基于混合两阶段搜索算法，第一阶段用演化策略使车辆数最小，第二阶段用禁忌搜索法使总距离最小。文献[4] 中，B. Ombuki, M.Nakamura, and O. Maeda先用模拟退火算法设置车辆数，再用局部禁忌搜索算法使总运输费用最小。文献[5] 中，L.M. Gambar -della, E.Taillard,and G.Agazzi等通过分层目标函数最小化研究了一类VRPTW的多目标问题，第一个函数使车辆数最小，第二个函数使总时间最小。文献[6] 中，S.R.Thangiah,研究了先聚类后考虑路线的模型，并用遗传算法和局部搜索来进行模型求解。但上述文献中普遍采用的两阶段法解决VRPTW问题，其实质均是将一个多目标问题转化为一个单目标的优化问题。但笔者以为，车辆数增加固然会使与之相关的车辆使用费和人工费增加，但优先优化最小车辆数，在理论和实际应用中不仅没有太多的积极意义，相反会增加燃料费用和为客户服务的时间，特别是在车辆和人工费用较低的条件下，由于车辆和人员数的重要性相对降低，这种差别就更加显著。因此，无论从能源消耗还是从生态环境保护角度而言，均应将优化车辆数和距离视为同等重要。本文将两者独立考虑，避免优先考虑其中任何一方，并运用Pareto评等技术的遗传算法获得与以往研究更具竞争性的最优解。