求解双目标带时间窗车辆路径问题的蚁群算法
柴 获a,b，何瑞春*b，苏江省b，宋宇博a，代存杰a，马昌喜b
【摘 要】针对运输网络为多重图的双目标带时间窗车辆路径问题设计了蚁群算法.首先，建立了多重图的双目标带时间窗车辆路径问题的数学模型，提出了针对该问题解的搜索空间构建方法，定义了一种综合考虑各优化目标、时间窗和信息素等启发信息的状态转移概率公式.为了对比说明该算法的有效性，同时设计基于NSGA-II的多目标遗传算法.针对本文算例，对蚁群算法中的各参数进行了敏感性分析，根据分析结果设定算法参数，获得了算例的Pareto最优路径集，同时与NSGA-II算法及相关文献算法针对运行时间、收敛性和群体多样性进行比较.结果显示，本文设计的蚁群算法在这3个指标上均明显优于NSGA-II算法；在相同蚂蚁数量情况下，本文的算法在收敛性和群体多样性方面优于相关文献算法.
【期刊名称】交通运输系统工程与信息 【年(卷),期】2018(018)004 【总页数】7
【关键词】交通工程；带时间窗的车辆路径问题；多目标优化；蚁群算法；NSGA-II；状态转移概率；多重图
修回日期：2018-02-05录用日期：2018-03-07
基金项目：国家自然科学基金/National Natural Science Foundation of China(61364026)；兰州交通大学校青年基金/Youth Foundation of Lanzhou Jiaotong University(2015026)；兰州交通大学优秀科研平台(团队)资助计划/Excellent Platform of Lanzhou Jiaotong University(201604).
0 引言
车辆路径问题(VRP)中存在这样一类问题，其配送网络是1个多重图，网络中边具有1个以上属性，使得任意两个节点间存在1条以上非支配路径，而一般车辆路径问题[1-3]是基于简单图.这类问题被称为多重图中的车辆路径问题(VRP on Mutilgraph,VRP-MG)[4]，通常其优化目标与边的属性一一对应，为多目标优化问题.例如，危险品配送VRP问题中，任意路段具有运输成本与运输风险两个属性，往往成本和风险是此消彼长的关系，问题的解为1组Pareto最优路径.
VRP-MG中任意两个客户节点间存在1条以上非支配路径，在安排车辆配送时，除节点间的配送次序会影响问题结果外，相同次序节点间不同路径的选择也对结果产生影响，因此，常见的MOVRP问题求解方法并不适用于此类问题.针对VRP-MG问题，部分学者设计了精确算法进行问题求解，Baldacci等[4]先进行拉格朗日松弛后，再采用列生成算法；Garaix等[5]设计了动态规划方法；Ticha等[6]设计了分枝定价算法求解带时间窗的VRP-MG问题(VRPTW-MG)，但精确算法对于具有一定规模的问题则不再有效.因此，启发式算法和进化算法是一个不错的选择，David等[7]设计了禁忌搜索算法；Pradhananga等[8]先采用标号算法确定两节点间的Pareto路径集，然后设计了蚁群算法对该问题求解，该方法中采用局部搜索与全局搜索相结合的方式，具有较好的收敛性，然而算法中并没有针对不同目标建立相应的搜索空间，在解的群体分布性和多样性方面存在不足.
本文以多重图中路段具有2个属性的带时间窗的车辆问题(Bi-objective VRPTW-MG,BOVRPTW-MG)为对象，建立了双目标优化数学模型，并提出用
于求解双目标车辆路径问题的改进蚁群算法.
1 BOVRPTW-MG问题数学模型
在运输网络G=(N,E)中，N为n个节点的集合，包含配送中心0和客户节点集合C，E为节点间路段的集合.任意路段具有2个属性，因此，任意节点i,j间存在1条以上非支配路径.路径采用三元组(i,j,p)来表示，其中，p为节点i,j间的1条非支配路径；c(i1jp),c(i2jp)分别为路径p的2个属性；节点i,j间所有非支配路径集合为Pij.对于任意客户节点i(i∈C)，qi为节点i的需求量；[bi,ei]为节点i的需求时间窗；si为节点i的服务时长；[b0,e0]为车辆从配送中心出发和最晚返回配送中心的时间窗.K表示运输车辆集合，对于任意车辆k(k∈K)，CAPk表示其装载容量.xijpk表示车辆k是否经由路径p从节点i移动到节点j，如果是，xijpk=1，否则，xijpk=0.
式中：tijp为车辆从节点i经由路径p到达节点j的运输时间；Tik为车辆k开始为节点i服务的时刻，如果车辆从节点i经由路径p到达节点j，则Tjk=max(Tik+si+tijk,bj)，即车辆k如果早于节点j的最早开始时间，则需要等待到时刻bj后才能开始服务.
式(2)和式(3)为目标函数；式(4)和式(5)表示任意1个节点由1辆车经由1条路径来服务；式(6)为子回路消去约束；式(7)～式(9)表示1辆车从配送中心出发，满足式(10)容量约束的条件下，服务完所有节点后再返回配送中心；式(11)表示车辆k在从开始为节点i服务至移动到下一节点j并开始服务过程中需要满足的时间条件；式(12)～式(14)为时间窗约束，式(12)表示车辆k到达节点i开始服务的时刻需要满足节点i的时间窗要求，式(13)和式(14)分别表示车辆k从配送中心出发和返回配送中心的时刻需满足配送中心的时间窗.
姹傝В鍙岀洰鏍囧甫鏃堕棿绐楄溅杈嗚矾寰勯棶棰樼殑铓佺兢绠楁硶 - 鐧惧害鏂囧簱
