论文部分内容阅读
摘 要：为了解决带软时间窗车辆路径这一类典型的NP-hard问题，减少总配送成本，本文提出一种混合蚁群算法，通过蚁群优化技术与遗传算法中的变异算子结合增加解的多样性，根据适应度函数评估解的质量获得精英解来对构建的模型求解，采用众所周知的基准所罗门数据集，设置25和100不同的客户规模仿真结果对比评估性能，得到全局平均解的优化率都达到10%以上的结果。仿真结果显示，高效地求解了VRPSTW问题，在收敛速度和寻优结果两方面均有明显优化。
关键词：VRPSTW;蚁群优化;变异算子;精英解
中图分类号：TP181 文献标识码：A 文章编号：1673-260X（2021）07-0009-04
1 引言
带软时间窗的车辆路径问题（VRPSTW），是基本VRP的延伸，时间窗约束被放宽为“软”，如果车辆未按客户提前预定的时间窗要求到达客户点，允许时间有所偏离，但必须付出一定惩罚成本。带软时间窗车辆路径问题在考虑带硬时间窗车辆路径问题会对车辆资源浪费和配送服务窗口要求过于强硬两方面存在优势。近年对VRPSTW的研究，Xu等人[1]采用了将贪婪策略和自适应策略结合的非支配排序遗传算法;Beheshti等人[2]提出了一种高效的混合列生成-元启发式方法;范厚明等人[3]将变领域下降搜索应用于粒子群算法的扰动，提高了算法的搜索性能;李国明等人[4]提出一种修正算法和禁忌搜索算法结合的两阶段改进算法;凌海峰等人[5]将蚁群算法与2-opt结合求解MDOVRPSTW。蚁群优化算法在求解VRP及其扩展问题上，因为其自身较强的自组织性和正反馈特点，拥有较好收敛效果同时容易陷入“早熟”，学者们于是通过引入精英保留方法、领域搜索或混合其他经典启发式算法优势[6]来改进蚁群算法。在此对VRPSTW首先进行了介绍和建模，目的在于降低总配送成本;其次，为了产生高质量的解决方案，将蚁群元启发式算法与利用邻域搜索空间的变异算子进行了混合求解。
2 VRPSTW问题描述
带软时间窗的车辆路径问题实质上相当于一个运输网络G（N，A），N={0，1，…，n，n+1}是对应于N位客户的节点集，V={1，…，k}是可用车辆的集合，每辆车容量有限为Qv，其使用时产生的固定成本为fv，每位客户i具有在配送服务时间内的需求dj，并且由一辆车在要求的时间窗[ei，li]内一次服务完成，目标是找到合适的路线同时减少总配送成本。
2.1 符号定义
运输车v在边（i，j）上的路线成本用cij表示，运输车v在路径（i，j）的行驶时间用tijv表示，Ri为提前配送给客户的惩罚成本，Hi是延误配送给客户惩罚成本，C是控制参数，W为客户需求点的任意子集，xijv作为决策变量取为1，否则为0，Eiv表示当车辆v提前到达客户点时情况的决策变量，Liv表示车辆v延误到达客户点时情况的决策变量。
式（1）中的目标函数是最小化总路线成本，式（2）和式（3）表示每个客户只得到车辆服务一次，式（4）为车辆从运输点出发最终返回运输点，式（5）确保每条路线在仓库开始和结束，式（6）为保证不超过车辆容量，式（7）为车辆离开的时间和开始节点计算每个节点的到达时间要求，式（8）为了将多余子路排除，式（9）为决策变量取值要求，式（10）参数约束为非负。
3 求解带软时间窗车辆路径问题的混合蚁群算法
3.1 蚁群算法
蚁群算法（ACO）受蚂蚁搜索食物机制的启发，使得每个智能体都是一只人工蚂蚁。蚁群算法能够以非常有效的方式解决像TSP和VRP这样的NP难问题。具体如下：
（1）构建解：通过计算状态转移概率逐步构建完整解。状态转移概率公式如下：
其中，Pijw（t）表示选择选择下一节点的转移概率，？子ij为边（i，j）上释放的信息素浓度，？浊ij为边（i，j）的信息启发式因子，？琢和？茁分别表示信息素和启发式因子的影响程度，Ni为蚂蚁向下一节点访问的节点集。
（2）当蚂蟻在每次迭代中找到最佳解时，通过以下方式执行全局更新：
在这个等式中，？驻？子ijw（t）表示在t时刻边（i，j）上的信息素的值，由蚂蚁w来释放。？籽为信息素挥发系数，Q为全局信息素常量。
在这个公式中，Q代表信息素的蒸发率，而cost（i，j）代表蚂蚁w在前一次重复中进行分配的成本。由于依照目标函数是降低配送总成本，则将表示路径（i，j）上的成本cost（i，j）加入改进信息素更新公式。信息素更新的目的是降低次优解的价值，增加最佳解的数量。当使用ACO算法求解VRPSTW时，每只蚂蚁从仓库出发，在一定的约束条件下，通过逐步选择下一访问节点来构建路径。当前路线中的下一个选择不满足条件时，蚂蚁返回仓库，通过分配未被路由的节点来构建另一条路线。重复这个过程，直到所有节点都被访问，并且可以获得一个可行的解决方案。
3.2 变异操作
蚁群算法和遗传算法进行混合的方法在目前的研究很多，但基本都是局限在基本车辆路径问题上，在此采用了新的方式并应用在带软时间窗车辆路径上，变异算子定义为：在0到1之间选择一个随机数c，判断c是否小于等于变异概率q1;如果满足，便随机产生几对基因变异位;然后交换这几对变异位置的基因。为了形象描述变异操作，我们在图1中给出了一个示例解决方案，它是由实际车辆路径解决方案转换而来的序列代码。变异操作在图2所示变异前的序列代码上实现，其通过从图1所示的序列解去除去0（仓库）而获得。本变异操作首先随机选择多对客户，例如3和8，1和10。通过交换客户对，我们获得了一个新解决方案序列。结果如图2变异后所示。最后将0（仓库）插回获得的新序列解中，便得到新的解决方案。交换次数n=n/3，n为客户数量。 3.3 解的评估
利用公式⒁作为评价解质量的适应度函数。假设应用变异操作得到K个后代解，那么解的个数为M+K个（其中M为蚂蚁数，M≤K）。根据公式（14）得出其每一个的适应度函数值进行排序，适应度值大的，解的质量就比较好，排序就靠前。
3.4 混合蚁群算法
该混合算法利用蚁群优化算法和变异算子来获得一个具有良好平衡的探索-开发行为的搜索过程。此算法由两个阶段组成。第一阶段，每个蚂蚁基于蚁群优化框架生成可行解，第二阶段，利用变异算子产生随机选择的解决方案，获得一定个数新的解决方案。然后，将这些新解结合第一步改进蚁群算法获得的可行解，随后，信息素轨迹将被更新以探索蚂蚁的搜索空间并产生更好的后续解决方案。通过这个过程重复，直到达到预定的迭代次数。提出的HACO的算法具体步骤如下：
输入：蚂蚁数量m，0≤q0≤1等。
输出：一组针对VRPSTW的精英解决方案。
Step1初始化：对于l=1，2，…，m，将m只蚂蚁随机放在调度中心，初始化访问节点集合Ni=？覬及候选集Taub表，初始化各参数，设置l=1。
Step2根据公式（11）选择下一个要访问的节点j（j？埸Ni）并更新蚂蚁l的Ni和Taub表。
Step3如果Taub=？覬，进入步骤3;否则，请转到步骤2。
Step4停止标准：如果l>M，则停止，记录进全局可行解集M;否则，转到步骤2。
Step5将计数器设置为nc=1。
Step6生成解：如果nc≤maxiter，使用全局可行解集M里的M个解;否则，算法终止并输出M。
Step7突变：设置l=l+1，在[0，1]中均匀生成一个随机数c，如果c≤q1，则对蚂蚁l生成的解进行变异操作;否则，请转到步骤7。设置l=l+1并重复步骤7，直到l>M。
Step8解的评估：使用公式（14）计算的适应度降序排列M+K解（由m蚂蚁获得的M解和使用变异操作获得的K个新解），并接受第一个M解。
Step9根据式（12）和（13），更新信息素。
Step10设置nc=nc+1，进入步骤6。
4 实验及其结果分析
4.1 实验环境及参数设置
本实验采用国际上通用的Solomon标准算例。该算法在Matlab R2010a中实现，并在一台搭载Intel i5-8265U双核处理器，CPU 3.60GHz、8GB RAM的计算机上执行。算例参数在多次调试后最终设置为：种群蚂蚁规模m=40，？琢=1，？茁=3，？酌=2，？籽=0.85，全局信息素常量Q=20，变异概率q1=0.5。
4.2 模型试验结果与分析
选取Solomon标准数据集的3类数据中有客户规模25的C101-25、R101-25、RC101-25和客户规模100的C101-100、R101-100、RC101-100共6组算例，设置相同的参数和实验条件，对传统蚁群算法与提出的混合蚁群算法都进行200次迭代，由于混合蚁群算法[7]同样分为25和100两种客户规模，和该混合蚁群算法具有可比性，因此将其与本文迭代200次实验结果的平均值一起分析，统计结果见表1。我们选取C101-25算例传统蚁群算法和该混合蚁群算法的算法迭代曲线图对比效果如图3。
根据表1的实验数据结果对比可知，所提出的混合蚁群算法相比同等条件下的传统蚁群算法，不仅在使用车辆数，还有花费路程和总成本平均值上都有显著的优化，其在C101-25、R101-25、RC101-25和客户规模100的C101-100、R101-100、RC101-100这6组算例，全局平均解优化率分别为12%、14%、12%、14%、13%、13%，全局优化解的质量最高达到了14%，所有算例的全局平均解优化率误差不超过2%。通过对比黄震[7]的混合蚁群算法实验结果，该算法在车辆数和总路程上都有明显效果，不仅在25的客户规模还是100的客户规模上，使用的配送车辆数都有减少1-3辆，使用车辆带来的成本也得到减少，表现了很好的适应性，有效减少配送车辆，优化了路线的同时在有限条件下使目标函数配送总成本减少。通过图3在同样进行200次迭代下，该混合蚁群算法在迭代开始总成本为4282元对比传统蚁群算法的最开始成本4800元少，表明该混合蚁群算法提高解的质量，同时由图3可知，该混合蚁群算法达到迭代最优的速度比传统蚁群算法迭代达到最优速度快，保持的收敛性较好，也体现了算法的稳健性和求解性能良好，所提出的HACO方法获得的结果在解的质量和计算收敛迭代方面都得到优化。
下面选择客户规模小的25名客户的C101-25和相对大的100名客户的RC101-100算例最优解的路径规划情况，以及其最优配送方案路线图，如表2、表3和图4、图5。
5 结语
为了更适用于现实生活中的实际问题，将经典蚁群算法作为基本框架，引用遗传算法中的变异算子，增强了局部探索解的能力，并结合随机全局探索，避免了蚁群算法陷入局部最优解。所提出的HACO在仿真实验中不同的客户规模下对比。与传统蚁群算法和其他混合蚁群算法结果相比，算法的求解能力是相当有效的。并且在接下来的工作，也为相关方向提供了参考依据。现实需求中，为了满足更多功能设定，对车辆路径问题的更多变种，比如带容量限制的多目标，软时间窗車辆路径问题，以及加入随机、模糊区间等约束，都具有进一步研究的价值。
参考文献：
〔1〕Xu Z， Elomri A， Pokharel S， et al. A Model for Capacitated Green Vehicle Routing Problem with the Time-varying Vehicle Speed and Soft Time Windows[J].Computers & Industrial Engineering， 2019， 137（Nov.）： 106011.1-106011.14.
〔2〕Beheshti A K ， Hejazi S R . A Novel Hybrid Column Generation-metaheuristic Approach for the Vehicle Routing Problem with General Soft Time Window[J].Information Sciences，2015， 316（C）：598-615.
〔3〕范厚明，刘文琪，徐振林，等.混合粒子群算法求解带软时间窗的VRPSPD问题[J].计算机工程与应用，2018，54（19）：221-229.
〔4〕李国明，李军华.带软时间窗的随机需求车辆路径问题的算法研究[J].计算机集成制造系统，2021，03（09）：1-20.
〔5〕凌海峰，谷俊辉.带软时间窗的多车场开放式车辆调度[J].计算机工程与应用，2017，53（14）：232-239.
〔6〕JIANG，GENGL.Hybridizing Variablen Eighbor-hoodserch with Ant Colony Optimization for Solving the Sing Lerow Facility Lay Out Problem[J].Europoean Journal of Operational Reserch，2016，248（03）：899-909.
〔7〕黄震，罗中良，黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报（自然科学版），2015，54（01）：41-46.
关键词：VRPSTW;蚁群优化;变异算子;精英解
中图分类号：TP181 文献标识码：A 文章编号：1673-260X（2021）07-0009-04
1 引言
带软时间窗的车辆路径问题（VRPSTW），是基本VRP的延伸，时间窗约束被放宽为“软”，如果车辆未按客户提前预定的时间窗要求到达客户点，允许时间有所偏离，但必须付出一定惩罚成本。带软时间窗车辆路径问题在考虑带硬时间窗车辆路径问题会对车辆资源浪费和配送服务窗口要求过于强硬两方面存在优势。近年对VRPSTW的研究，Xu等人[1]采用了将贪婪策略和自适应策略结合的非支配排序遗传算法;Beheshti等人[2]提出了一种高效的混合列生成-元启发式方法;范厚明等人[3]将变领域下降搜索应用于粒子群算法的扰动，提高了算法的搜索性能;李国明等人[4]提出一种修正算法和禁忌搜索算法结合的两阶段改进算法;凌海峰等人[5]将蚁群算法与2-opt结合求解MDOVRPSTW。蚁群优化算法在求解VRP及其扩展问题上，因为其自身较强的自组织性和正反馈特点，拥有较好收敛效果同时容易陷入“早熟”，学者们于是通过引入精英保留方法、领域搜索或混合其他经典启发式算法优势[6]来改进蚁群算法。在此对VRPSTW首先进行了介绍和建模，目的在于降低总配送成本;其次，为了产生高质量的解决方案，将蚁群元启发式算法与利用邻域搜索空间的变异算子进行了混合求解。
2 VRPSTW问题描述
带软时间窗的车辆路径问题实质上相当于一个运输网络G（N，A），N={0，1，…，n，n+1}是对应于N位客户的节点集，V={1，…，k}是可用车辆的集合，每辆车容量有限为Qv，其使用时产生的固定成本为fv，每位客户i具有在配送服务时间内的需求dj，并且由一辆车在要求的时间窗[ei，li]内一次服务完成，目标是找到合适的路线同时减少总配送成本。
2.1 符号定义
运输车v在边（i，j）上的路线成本用cij表示，运输车v在路径（i，j）的行驶时间用tijv表示，Ri为提前配送给客户的惩罚成本，Hi是延误配送给客户惩罚成本，C是控制参数，W为客户需求点的任意子集，xijv作为决策变量取为1，否则为0，Eiv表示当车辆v提前到达客户点时情况的决策变量，Liv表示车辆v延误到达客户点时情况的决策变量。
式（1）中的目标函数是最小化总路线成本，式（2）和式（3）表示每个客户只得到车辆服务一次，式（4）为车辆从运输点出发最终返回运输点，式（5）确保每条路线在仓库开始和结束，式（6）为保证不超过车辆容量，式（7）为车辆离开的时间和开始节点计算每个节点的到达时间要求，式（8）为了将多余子路排除，式（9）为决策变量取值要求，式（10）参数约束为非负。
3 求解带软时间窗车辆路径问题的混合蚁群算法
3.1 蚁群算法
蚁群算法（ACO）受蚂蚁搜索食物机制的启发，使得每个智能体都是一只人工蚂蚁。蚁群算法能够以非常有效的方式解决像TSP和VRP这样的NP难问题。具体如下：
（1）构建解：通过计算状态转移概率逐步构建完整解。状态转移概率公式如下：
其中，Pijw（t）表示选择选择下一节点的转移概率，？子ij为边（i，j）上释放的信息素浓度，？浊ij为边（i，j）的信息启发式因子，？琢和？茁分别表示信息素和启发式因子的影响程度，Ni为蚂蚁向下一节点访问的节点集。
（2）当蚂蟻在每次迭代中找到最佳解时，通过以下方式执行全局更新：
在这个等式中，？驻？子ijw（t）表示在t时刻边（i，j）上的信息素的值，由蚂蚁w来释放。？籽为信息素挥发系数，Q为全局信息素常量。
在这个公式中，Q代表信息素的蒸发率，而cost（i，j）代表蚂蚁w在前一次重复中进行分配的成本。由于依照目标函数是降低配送总成本，则将表示路径（i，j）上的成本cost（i，j）加入改进信息素更新公式。信息素更新的目的是降低次优解的价值，增加最佳解的数量。当使用ACO算法求解VRPSTW时，每只蚂蚁从仓库出发，在一定的约束条件下，通过逐步选择下一访问节点来构建路径。当前路线中的下一个选择不满足条件时，蚂蚁返回仓库，通过分配未被路由的节点来构建另一条路线。重复这个过程，直到所有节点都被访问，并且可以获得一个可行的解决方案。
3.2 变异操作
蚁群算法和遗传算法进行混合的方法在目前的研究很多，但基本都是局限在基本车辆路径问题上，在此采用了新的方式并应用在带软时间窗车辆路径上，变异算子定义为：在0到1之间选择一个随机数c，判断c是否小于等于变异概率q1;如果满足，便随机产生几对基因变异位;然后交换这几对变异位置的基因。为了形象描述变异操作，我们在图1中给出了一个示例解决方案，它是由实际车辆路径解决方案转换而来的序列代码。变异操作在图2所示变异前的序列代码上实现，其通过从图1所示的序列解去除去0（仓库）而获得。本变异操作首先随机选择多对客户，例如3和8，1和10。通过交换客户对，我们获得了一个新解决方案序列。结果如图2变异后所示。最后将0（仓库）插回获得的新序列解中，便得到新的解决方案。交换次数n=n/3，n为客户数量。 3.3 解的评估
利用公式⒁作为评价解质量的适应度函数。假设应用变异操作得到K个后代解，那么解的个数为M+K个（其中M为蚂蚁数，M≤K）。根据公式（14）得出其每一个的适应度函数值进行排序，适应度值大的，解的质量就比较好，排序就靠前。
3.4 混合蚁群算法
该混合算法利用蚁群优化算法和变异算子来获得一个具有良好平衡的探索-开发行为的搜索过程。此算法由两个阶段组成。第一阶段，每个蚂蚁基于蚁群优化框架生成可行解，第二阶段，利用变异算子产生随机选择的解决方案，获得一定个数新的解决方案。然后，将这些新解结合第一步改进蚁群算法获得的可行解，随后，信息素轨迹将被更新以探索蚂蚁的搜索空间并产生更好的后续解决方案。通过这个过程重复，直到达到预定的迭代次数。提出的HACO的算法具体步骤如下：
输入：蚂蚁数量m，0≤q0≤1等。
输出：一组针对VRPSTW的精英解决方案。
Step1初始化：对于l=1，2，…，m，将m只蚂蚁随机放在调度中心，初始化访问节点集合Ni=？覬及候选集Taub表，初始化各参数，设置l=1。
Step2根据公式（11）选择下一个要访问的节点j（j？埸Ni）并更新蚂蚁l的Ni和Taub表。
Step3如果Taub=？覬，进入步骤3;否则，请转到步骤2。
Step4停止标准：如果l>M，则停止，记录进全局可行解集M;否则，转到步骤2。
Step5将计数器设置为nc=1。
Step6生成解：如果nc≤maxiter，使用全局可行解集M里的M个解;否则，算法终止并输出M。
Step7突变：设置l=l+1，在[0，1]中均匀生成一个随机数c，如果c≤q1，则对蚂蚁l生成的解进行变异操作;否则，请转到步骤7。设置l=l+1并重复步骤7，直到l>M。
Step8解的评估：使用公式（14）计算的适应度降序排列M+K解（由m蚂蚁获得的M解和使用变异操作获得的K个新解），并接受第一个M解。
Step9根据式（12）和（13），更新信息素。
Step10设置nc=nc+1，进入步骤6。
4 实验及其结果分析
4.1 实验环境及参数设置
本实验采用国际上通用的Solomon标准算例。该算法在Matlab R2010a中实现，并在一台搭载Intel i5-8265U双核处理器，CPU 3.60GHz、8GB RAM的计算机上执行。算例参数在多次调试后最终设置为：种群蚂蚁规模m=40，？琢=1，？茁=3，？酌=2，？籽=0.85，全局信息素常量Q=20，变异概率q1=0.5。
4.2 模型试验结果与分析
选取Solomon标准数据集的3类数据中有客户规模25的C101-25、R101-25、RC101-25和客户规模100的C101-100、R101-100、RC101-100共6组算例，设置相同的参数和实验条件，对传统蚁群算法与提出的混合蚁群算法都进行200次迭代，由于混合蚁群算法[7]同样分为25和100两种客户规模，和该混合蚁群算法具有可比性，因此将其与本文迭代200次实验结果的平均值一起分析，统计结果见表1。我们选取C101-25算例传统蚁群算法和该混合蚁群算法的算法迭代曲线图对比效果如图3。
根据表1的实验数据结果对比可知，所提出的混合蚁群算法相比同等条件下的传统蚁群算法，不仅在使用车辆数，还有花费路程和总成本平均值上都有显著的优化，其在C101-25、R101-25、RC101-25和客户规模100的C101-100、R101-100、RC101-100这6组算例，全局平均解优化率分别为12%、14%、12%、14%、13%、13%，全局优化解的质量最高达到了14%，所有算例的全局平均解优化率误差不超过2%。通过对比黄震[7]的混合蚁群算法实验结果，该算法在车辆数和总路程上都有明显效果，不仅在25的客户规模还是100的客户规模上，使用的配送车辆数都有减少1-3辆，使用车辆带来的成本也得到减少，表现了很好的适应性，有效减少配送车辆，优化了路线的同时在有限条件下使目标函数配送总成本减少。通过图3在同样进行200次迭代下，该混合蚁群算法在迭代开始总成本为4282元对比传统蚁群算法的最开始成本4800元少，表明该混合蚁群算法提高解的质量，同时由图3可知，该混合蚁群算法达到迭代最优的速度比传统蚁群算法迭代达到最优速度快，保持的收敛性较好，也体现了算法的稳健性和求解性能良好，所提出的HACO方法获得的结果在解的质量和计算收敛迭代方面都得到优化。
下面选择客户规模小的25名客户的C101-25和相对大的100名客户的RC101-100算例最优解的路径规划情况，以及其最优配送方案路线图，如表2、表3和图4、图5。
5 结语
为了更适用于现实生活中的实际问题，将经典蚁群算法作为基本框架，引用遗传算法中的变异算子，增强了局部探索解的能力，并结合随机全局探索，避免了蚁群算法陷入局部最优解。所提出的HACO在仿真实验中不同的客户规模下对比。与传统蚁群算法和其他混合蚁群算法结果相比，算法的求解能力是相当有效的。并且在接下来的工作，也为相关方向提供了参考依据。现实需求中，为了满足更多功能设定，对车辆路径问题的更多变种，比如带容量限制的多目标，软时间窗車辆路径问题，以及加入随机、模糊区间等约束，都具有进一步研究的价值。
参考文献：
〔1〕Xu Z， Elomri A， Pokharel S， et al. A Model for Capacitated Green Vehicle Routing Problem with the Time-varying Vehicle Speed and Soft Time Windows[J].Computers & Industrial Engineering， 2019， 137（Nov.）： 106011.1-106011.14.
〔2〕Beheshti A K ， Hejazi S R . A Novel Hybrid Column Generation-metaheuristic Approach for the Vehicle Routing Problem with General Soft Time Window[J].Information Sciences，2015， 316（C）：598-615.
〔3〕范厚明，刘文琪，徐振林，等.混合粒子群算法求解带软时间窗的VRPSPD问题[J].计算机工程与应用，2018，54（19）：221-229.
〔4〕李国明，李军华.带软时间窗的随机需求车辆路径问题的算法研究[J].计算机集成制造系统，2021，03（09）：1-20.
〔5〕凌海峰，谷俊辉.带软时间窗的多车场开放式车辆调度[J].计算机工程与应用，2017，53（14）：232-239.
〔6〕JIANG，GENGL.Hybridizing Variablen Eighbor-hoodserch with Ant Colony Optimization for Solving the Sing Lerow Facility Lay Out Problem[J].Europoean Journal of Operational Reserch，2016，248（03）：899-909.
〔7〕黄震，罗中良，黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报（自然科学版），2015，54（01）：41-46.