时间窗约束下的车辆路径问题多目标优化算法.pdfVIP

第39卷第7I／1 数学的实践与认识 V01．39No．7 April，2009 2009年4月 INPRACTICEANDTHEORY MATHEMATICS 时间窗约束下的车辆路径问题多目标优化算法 张 毅， 申彦杰 (河南科技大学车辆与动力工程学院，河南洛阳471003) 摘要： 讨论了带时间窗约束的车辆路径问题(VRPTW)及其数学模型。分析了以遗传算法求解该类问题时 的染色体表示和有关遗传操作，将VRPTW视为一个多目标优化问题．用Pareto评等技术来求解最优解．并以 Solomen基准问题为例验证了该方法的有效性．结果表明t该方法与以往文献中的最好结果具有竞争性． 关键词： 物流配送，时问窗约束的VRP，遗传算法，多目标优化 ．1 引 言 NP难题。且对于超过100个客户点的问题很难找到最优解．近年来，遗传算法、禁忌有哪些信誉好的足球投注网站算 法、模拟退火算法等启发式方法在解决此类问题中发挥了积极的作用．文献[1]中，H． and GehringJ．Homberger研究了基于混合两阶段有哪些信誉好的足球投注网站算法，第一阶段用演化策略使车辆数 and J．M．Rousseau研 最小，第二阶段用禁忌有哪些信誉好的足球投注网站法使总距离最小．文献[2]中，J．Y．Potvin 究了两阶段禁忌有哪些信誉好的足球投注网站算法，第一阶段通过改变路径上的客户来减小车辆数，第二阶段客户交 and 换使总费用最小．文献[3]中，w．C．ChiangR．Russell研究了基于模拟退火和禁忌搜 G．Agazzi 等通过分层目标函数最小化研究了一类VRPTW的多目标问题，第一个函数使车辆数最小。 O．Maeda先用模拟 第二个函数使总时问最小．文献[6]中。B．Ombuki，M．Nakamura，and 退火算法设置车辆数。再用局部禁忌有哪些信誉好的足球投注网站算法使总运输费用最小．但上述文献中普遍采用两 阶段法解决VRPTW问题，即首先最小化车辆数。继而再最小化行驶距离(费用)，其实质是 将一个多目标问题转化为一个单目标的优化问题．但笔者以为，车辆数增加固然会使与之相 关的车辆使用费和人工费增加，但优先优化最小车辆数(使用较少的车辆长距离行驶)。在理 论和实际应用中不仅没有太多的积极意义，相反会增加燃料费用和为客户服务的时间。特别 是在车辆和人工费用较低(如使用摩托车快递)的条件下，由于车辆和人员数的重要性相对 降低，这种差别就更加显著．因此，无论从能源消耗还是从生态环境保护角度而言，均应将优 化车辆数和距离视为同等重要．本文将两者独立考虑，避免优先考虑其中任何一方和试图将 其组合．并运用Pareto评等技术的遗传算法获得与以往研究更具竞争性的最优解． 2 VRPTW问题及其数学模型 收藕日期：2007—04．19 基金项目t河南省教育厅自然科学基金(200510464028) 万方数据 7期 张毅，等：时间窗约柬下的车辆路径问题多目标优化算法 125 各个顶点间的可能连接(包括表示配送中心的点)．所有弧既不能终止于点0，也不能起始于 点卵+1，并且所有的路线都是从点0开始。至点咒+1结束．费用f，』和在弧(i，．f)∈A上的 行驶时间为t伊车辆是的容量为qt，客户i的需求量为di，i∈C．每个客户有时间窗[口，，b，] 限制．车辆可以在时间窗开始之前到达，而不允许在时间窗之后到达．假定所有路线在时间0 开始，则口。=b。=0． i点到-『点时。变