-
电子商务改变了人们的消费方式，网上交易量与日俱增。例如，根据国家邮政发布的数据，2019年11月11日前后，全国邮政、快递企业共处理邮(快)件23.1亿件[1]。面对如此庞大的交易量，如何有效地在较短时间、较低成本下完成物流配送，是物流业亟待解决的问题，智能决策、智能调度在供应链中发挥着越来越重要的作用[2]。
随着消费结构的变化，配送需求在不断地发生着变化，更多的需求呈现出随机性和时效性强等特点。在物流配送过程中出现突发事件时，例如任务增加和车辆故障等情况，如何快速响应，有效解决突发事件，并且能够减少人力、物力和财力的消耗，是物流配送面临的巨大挑战。
车辆路径问题[3]是工业系统中运输和物流管理的著名运筹学问题。解决车辆路径问题有很多方法，文献[4]提出了波束搜索与最大最小蚂蚁系统相结合的启发式算法；文献[5]采用元启发式模拟退火、禁忌搜索和混合算法对元启发式算法进行了改进；文献[6]提出了一种集成模拟退火机制和Voronoi长边引导优化的启发式算法解决大规模车辆路径问题。这些方法针对的是静态的车辆配送需求，而在运输过程中出现动态请求，需要在短时间内作出决策，传统启发式算法无法快速生成有效的车辆调度方案。在现实情况中，为了维持市场份额，往往存在着配送成本与配送时效之间的矛盾。因此，本文基于破坏重建算法提出了一种局部搜索的物流车辆动态调度方法，解决车辆故障或新增配送任务等突发状况下的重新调度问题，降低路线调整的配送成本。
-
车辆路径问题是指一定数量的客户，各自有不同数量的货物需求，配送中心分配车辆、安排路线完成运输任务，并在一些约束条件下，达到运输距离、时间等成本最小的目的，车辆路径问题被证明为非确定性多项式(nondeterministic polynomially，NP)难题。
车辆路径问题根据路径规划信息是否变化分为静态车辆路径问题和动态车辆路径问题。如图 1所示，静态车辆调度问题是指在车辆调度之前，所有有关调度的基本信息以及优化条件都是不变的，包括任务点数量、任务点服务窗口、车辆状态、行车时间和任务点之间的距离等。而现实中，大部分有关调度的优化信息都是变化的。
图 1 静态车辆路径问题
Figure 1. Static Vehicle Routing Problem
动态车辆路径问题是指在初始车辆路径构建之后，部分规划信息发生变化，车辆路径必须根据信息变化不断进行重新优化。如图 2所示，动态车辆路径问题是静态车辆调度的扩展，在静态车辆调度的前提下，在运输过程中，出现紧急状况，产生新的调度需求，例如任务点增加、车辆故障等情况，需要在较短时间内生成新的车辆路线。这就对车辆调度提出了更高的要求。
图 2 动态车辆路径问题
Figure 2. Dynamic Vehicle Routing Problem
根据文献[7]的研究，本文将动态车辆调度问题的动态度量化为：
$$ D = \frac{{{n_d}}}{n} \times 100{\rm{\% }} $$ (1) 式中，D表示动态性程度；nd表示动态任务点的数量；n表示所有任务点的总和。
-
动态车辆路径问题比静态车辆路径问题更加复杂，因为它需要在一个基于不确定需求的短时间内进行决策。求解动态车辆调度问题需要解决两个基本问题：求解策略与求解算法。目前有两种解决策略：(1)通过发生事件的概率来预测某区域的未来事件；(2)求解过程是基于已知数据并不考虑未知信息，当一些任务点出现时会立刻被整合到现有的解决方案中。通过第1种策略对动态车辆路径问题求解，文献[8-15]研究了车辆运载量、请求位置点、请求发生时间、需求量和服务时间的预测，并将预测的请求作为虚拟客户纳入到车辆路线中，提高了配送效率。但是基于这种策略求解动态车辆问题需要大量有显著特征的历史数据，而通常情况下这些数据需要通过长期观测获取，并且由于预测未来事件是概率事件，当未来事件预测不准确时会造成无法完成任务。因此，针对动态车辆路径问题的求解，依然以第2种策略为主。
通过第2种策略求解动态车辆路径问题是将动态车辆路径问题分解为一系列的静态车辆路径问题。对于静态车辆路径问题求解分为精确算法和启发式算法，精确算法只能针对数据量较小的车辆路径问题[16]，对于较多数据量的车辆路径问题的求解主要以启发式算法为主。其中，元启发式算法是传统启发式算法的改进，计算量比传统启发式算法更少，能求得更优化的解，例如遗传算法[17-20]、蚁群算法[21-24]和粒子群算法[25]等。针对将动态车辆路径问题分解为静态车辆路径问题的方法，文献[26]对动态情况下未完成的任务点利用遗传算法中的竞标赛选拔和精英策略进行选择，通过交叉与突变来形成新的路线，该方法提高了全局搜索能力，但是未考虑当数据量增大时带来的运算时间增大的问题；文献[27-28]将可变邻域搜索算法与另一种遗传算法结合应用于动态车辆问题，但是实验结果中距离成本增加约6.7%和7.4%；文献[29]开发了一个元启发式算法，用于处理具有多个约束(多时间窗口、客户优先级和车辆客户约束)的有时间窗动态车辆路径问题的(dynamic vehicle routing problems with time windows，DVRPTW)的两个变体，文献[30]对此进行了进一步研究，提出了一个通用可变邻域搜索(general variable neighborhood search，GVNS)算法来解决DVRPTW的实际应用；文献[31]提出了一种邻域搜索的启发式算法，并将其应用于取货和分发问题；文献[32-33]对邻域搜索方法进行改进，降低了配送的成本，但是平均行驶距离增加4.63%；文献[34]使用一种等待策略，即车辆完成任务后，延长车辆在当前任务点等待时间，增加可使用车辆数量来完成新请求的配送任务，但是这种方法延长了车辆等待时间，会造成其他任务点无法完成的问题。
本文针对没有大量历史数据的动态车辆路径问题，选择第2种策略，在车辆配送中及时将新的请求插入系统并进行处理。已有的众多求解DVRPTW的算法中没有车辆数量的限制，并且没有考虑资源有限这个实际问题，这使得在实际应用中动态车辆路径问题受到约束，导致无法完成任务。对于构造好的初始解以及在出现动态需求后能够合理生成新的解，很少有人研究。本文设计了一种基于破坏重建算法的局部搜索方法，通过破坏重建算法获得较好的初始解，在出现紧急状况之后使用局部搜索方法进行求解。局部搜索方法分为移除与插入两步，本文提出了一种新的移除策略，将动态任务点作为移除的一部分，结合破坏重建算法对动态车辆路径问题进行求解。
-
物流配送车辆调度可以简单描述为从一个配送中心派出多辆车辆，合理规划路线，在规定时间内到达指定任务点完成发货任务，返回配送中心，使得整体成本(运输时间和运输距离)尽可能少。动态车辆路径问题是在配送过程中出现新的请求，进行合理的重新规划以完成新的需求。
根据上述动态车辆调度问题，将问题定义为F={S，A，M}，符号说明见表 1。表 1中，S={si} 表示任务点集合，向量si=[eifiwixiyiqi]表示任务点的属性数，其中ei、fi表示服务窗口中的开始时间与结束时间，wi表示服务时间，(xi，yi)表示位置坐标，qi表示任务点的需求量；A={ai}表示新添加任务点的集合；车辆集合为K={ki，i= 1，2，3…v}，将车辆视为一个移动的节点M= {mki，i=1，2…v}，其中v表示车辆总数，每辆车可以通过mk=(gk，hk，xk，yk，zk)表示，其中gk、hk表示车辆运行窗口，(xk，yk)表示车辆位置，zk表示车辆的载荷；Ck表示车辆k的固定成本；Tj表示到达任务点sj的时间。
表 1 符号说明
Table 1. Description of Symbols
符号 符号说明 S={si} 模型中任务点集合, s0表示调度中心 A={ai} 模型中新增任务点集合 M={mki, i=1, 2…k} 模型车辆作为移动节点集合 K={ki, i=1, 2, 3…v} ki表示第i辆车，共有v辆车 lij 任务点i到j路段的长度 tij 任务点i到j路段的车辆运输时间 S' 原有任务点与新增任务点的集合
S'=S∪ACk 车辆k的固定成本 Tj 到达任务点sj的时间 结合上述各类建模，可构造出单配送中心车辆调度的数学模型如下：模型有μi，jk、ρk两类决策变量，定义为：μi，jk=1表示车辆k会在i到j路段运行，否则为0；ρk=1表示车辆被使用，否则为0。
目标函数为：
$$ {\rm{min}}\mathop \sum \limits_{i \in S'} \mathop \sum \limits_{j \in S', i \ne j} \mathop \sum \limits_{k \in K} {\rho _k}\mu _{i, j}^k{l_{i, j}} + \lambda \mathop \sum \limits_{k \in K} {\rho _k}{C_k} $$ (2) 约束条件为：
$$ \sum\limits_{i \in S'} {\mu _{i, j}^k} = \sum\limits_{i \in S'} {\mu _{j, i}^k} , j \in S', k \in K $$ (3) $$ \mathop \sum \limits_{i \in S'} \mu _{i, j}^k = \mathop \sum \limits_{i \in S'} \mu _{j, i}^k = 1, j \in S', i \ne j, j \ne 0 $$ (4) $$ \mathop \sum \limits_{k \in K} \mathop \sum \limits_{i \in S', i \ne 0} \mu _{i, 0}^k = \mathop \sum \limits_{k \in K} \mathop \sum \limits_{i \in S', i \ne 0} \mu _{0, i}^k = \mathop \sum \limits_{k \in K} {\rho _k} $$ (5) $$ \mathop \sum \limits_{j \in S'} \mu _{i, j}^k = {\rho _k}, i \in M $$ (6) $$ \mathop \sum \limits_{i \in S'} \mathop \sum \limits_{j \in S', i \ne j} {q_i}\mu _{i, j}^k \le {z_k} $$ (7) $$ \begin{array}{l} {f_j} \ge {T_j} = {\rm{max}}\left( {\mathop \sum \limits_{i \in N} \mu _{i, j}^k\left( {{T_i} + {t_{ij}}} \right), \mathop \sum \limits_{i \in N} \mu _{i, j}^k{e_j}} \right) + \\ \;\;\;\;\;\;\;\;\;\mathop \sum \limits_{i \in N} \mu _{i, j}^k{w_j} \ge {e_j}, N = M\mathop \cup \nolimits^ S\mathop \cup \nolimits^ A \end{array} $$ (8) $$ \mu _{i, j}^k, {\rho _k} \in \left\{ {0, 1} \right\}, i, j \in S' $$ (9) 式(2)表示车辆调度优化目标函数，使得路径规划的总成本尽可能小；式(3)、式(4)表示每个任务点只被一辆车拜访一次；式(5)表示所有车辆从中心出发，并返回中心；式(6)保证两个决策变量的关系正确；式(7)保证车辆的运载量满足需求；式(8)保证车辆在任务点服务窗口关闭前到达并完成发货任务。
-
动态车辆调度问题是静态车辆调度问题的扩展，需要生成车辆初始调度路线。根据建立的车辆调度模型，初始化解决方案采用破坏重建算法进行求解。破坏重建算法[35]适用于较复杂的优化问题(不连续问题、目标复杂或约束较多的问题)，提高了针对复杂优化问题求解的精度。破坏重建算法示意图如图 3所示。图 3(a)是当前车辆路径问题的解决方案；图 3(b)是删除3个节点后生成的破坏后解决方案，存在未完成的节点；图 3(c)是将删除的节点插入到方案中，重建后生成的新的车辆路线方案。
图 3 破坏重建算法过程示意图
Figure 3. Diagram of Ruin and Recreate Algorithm
破坏重建算法是先破坏某一部分的当前解，之后再试图恢复被破坏的解的过程，希望寻找到比之前更好的解决方案。破坏是对当前解的扰动，当破坏的范围较大时，就会有更高的可能性来创建一个新的解决方案，从而获得更好的解决方案，但收敛速度较慢。当破坏范围较小时，容易陷入局部最优。破坏有3种策略：径向破坏、随机破坏和顺序破坏。径向破坏是在随机任务点周围根据欧氏距离获得任务点集合进行破坏；随机破坏是随机生成任务点集合进行破坏；顺序破坏是从随机选择的路线中破坏一部分任务点。重建是将已经破坏的节点重新插入到系统中，使用贪婪算法等其他算法将破坏的节点在满足约束条件的前提下依次插入，从而获得新的解决方案。
-
当车辆在配送过程中出现紧急状况时产生动态需求，这就要求信息处理的时间尽可能短，已达到可执行与快速响应的需求，这类问题对求解时间要求较高。针对这些问题，本文提出了一种基于局部搜索的动态调度方法。算法流程如图 4所示：初始调度路线生成后，当出现动态需求时，通过移除任务点与重新插入两个步骤进行动态调度。
图 4 动态调度基本流程图
Figure 4. Diagram of Dynamic Scheduling
1) 移除任务点。本文提出了时间窗口路径任务点移除策略：首先搜索新增请求点一定范围内的节点，进而根据当前解，找到与范围内搜索到的节点在同一路线的未完成任务点，将这两类节点与新增请求点结合生成移除任务点集合。将新增的任务点a保存到集合φ，从未完成任务点集合U中计算相关值Rj(j∈U)。根据相关值将符合规则约束的任务点保存到集合φ，作为移除任务点集合。Rj的定义为：
$$ {R_j} = \left\{ {\begin{array}{*{20}{l}} {1, {d_{ja}} \le D}\\ {\mathop \sum \limits_{k \in K} \mathop \sum \limits_{i \in U} {\rho _k}\frac{{\mu _{i, j}^k}}{{{g_{ij}}}} + {R_i}, {d_{ja}} > D} \end{array}} \right. $$ (10) 式中，D表示固定值；dja表示任务点j到a的距离(本文使用欧氏距离)；gij定义为：
$$ {g_{ij}} = \frac{{{d_{ij}}}}{{{\rm{ma}}{{\rm{x}}_{p, q \in U}}{d_{pq}}}} $$ (11) 当dja≤D时，将Rj=1的任务点保存到集合φ中；当dja>D时，将Rj>1的任务点保存到φ中。通过Rj值就生成移除任务点集合。
2) 重新插入任务点。使用最佳插入原则在第一步获得的任务点集合中随机抽取任务点，判断可执行车辆以及成本，选择成本最小的方案插入。
-
为验证破坏重建算法的性能，首先使用公开数据集在静态调度情况下与蚁群算法进行对比分析，然后分别采用公开数据集和真实数据集进行动态调度实验。
-
本文首先选用了Solomon数据[36]对破坏重建算法与多目标混合蚁群优化算法[37]进行对比测试。Solomon数据是针对具有时间窗的车辆路线问题提出的数据集。选择其中C、R两种类型，C类数据任务点集中分布，R类数据任务点分散分布，两类数据任务点都为100个。测试环境为处理器为1.80 GHz/8 GB Intel(R) Core(TM) i5-8250，操作系统为Windows 10。分别使用破坏重建算法和多目标混合蚁群优化算法对C类数据集和R类数据集进行路线规划，每个数据集分别执行3次，结果取平均值。
蚁群算法中计算结果的好坏与蚂蚁个数和迭代次数没有较大联系，蚁群算法是一种与概率有关的算法，蚂蚁个数多、迭代次数大也不一定会比蚂蚁个数少、迭代次数少的情况好，有时会陷入局部最优，且在同一参数情况下，每次运行结果也都不一样。对于蚁群算法的这些缺点，大量研究对蚁群算法进行改进优化[38-44]。文献[45]提出了一种混合蚁群算法，该算法调整信息素方法和引入灾难算子，防止搜索过程陷入局部最优解；文献[37]提出了多目标混合蚁群优化算法，使用了3个变异算子，增强了局部搜索能力，并允许随机全局搜索。这些变异算子防止蚁群算法陷入局部最优解。
针对C数据，破坏重建算法迭代2 000次；针对R数据，因为R数据较复杂，采用破坏重建算法迭代10 000次。测试结果见表 2。由于测试数据较多，本文只展示了C101数据调度结果(见图 5)。
表 2 破坏重建算法与多目标混合蚁群优化算法对比结果
Table 2. Comparison Results of Ruin and Recreate and Multi-objective Hybrid Ant Colony Optimization Algorithm
数据集 最优解 多目标混合蚁群优化算法 破坏重建算法 车辆数/辆 成本/m 车辆数/辆 成本/m 耗时/s 车辆数/辆 成本/m 耗时/s C101 10 828.94 10 828.94 0.428 10 828.94 3.610 C102 10 828.94 10 831.42 0.497 10 828.94 3.653 C103 10 828.06 10 835.46 0.508 10 828.06 3.909 C104 10 824.78 10 839.53 0.485 10 852.35 6.833 C105 10 828.94 10 828.94 1.029 10 828.94 3.712 C106 10 828.94 10 828.94 1.352 10 828.94 3.911 C107 10 828.94 10 833.78 1.469 10 828.94 3.987 C108 10 828.94 10 838.15 1.584 10 828.94 3.735 C109 10 828.94 10 828.94 1.720 10 828.94 9.758 R101 20 1 650.80 20 1 675.45 1.598 19 1 654.41 80.382 R102 17 1 486.12 18 1 447.20 1.484 18 1 487.41 76.447 R103 14 1 213.62 15 1 239.40 1.297 13 1 224.55 60.114 R104 10 982.01 12 974.24 1.384 10 998.92 61.737 R105 14 1 377.11 15 1 385.67 1.492 14 1 379.73 64.366 R106 12 1 252.03 14 1 258.61 1.373 14 1 257.90 81.023 R107 10 1 113.69 12 1 110.54 1.436 11 1 097.80 56.898 R108 9 964.38 11 961.23 1.275 11 959.52 19.128 
图 5 C101数据调度结果
Figure 5. Scheduling Result of C101 Data
如表 2所示，对于C类数据集，多目标混合蚁群优化算法计算的距离成本有5个数据(C102、C103、C104、C107和C108)未达到最优解，而破坏重建算法除了C104数据都达到了最优解。对于R类数据集，破坏重建算法在成本计算与车辆使用量方面相对于多目标混合蚁群优化算法有较好的结果：在距离成本上，破坏重建算法有6个数据(R101、R103、R105、R106、R107和R108)测试结果优于多目标混合蚁群优化算法；在车辆使用量上，破坏重建算法有5个数据(R101、R103、R104、R105和R107)的测试结果少于多目标混合蚁群优化算法，并且有的测量结果优于最好结果，例如R101和R103。多目标混合蚁群优化算法虽然有2个数据(R102和R104)的距离成本上优于破坏重建算法，但是数据R104的计算结果中在车辆使用量上高于破坏重建算法。多目标混合蚁群优化算法有时依然会陷入局部最优，同一参数情况下，每次运行结果也都不一样，这些情况不利于模型建立。虽然破坏重建算法运行时间会受迭代次数的影响，但结果会随着迭代次数的增加而逐渐趋于最优，这种稳定性也是该算法的优点。
-
本文使用的关于动态车辆路径问题的标准数据集为Lackner数据集，下载链接为https://github.com/orivalde/dvrptw/blob/master/lackner.zip。Lackner数据集是Solomon数据的扩展，根据式(1)将动态性分为10%、30%、50%、70%和90%共5类，通过对C1、C2、R1和R2这4类数据集共240个实例进行求解。每个数据集通过两种方法运行3次，结果取平均。将结果与破坏重建算法进行比较，结果见表 3。
表 3 两种方法的计算结果比较
Table 3. Computational Results of Two Methods
实例 动态性/% 破坏重建方法 局部搜索方法 平均车辆数/辆 平均总行驶距离/m 平均车辆数/辆 平均总行驶距离/m C1 90 10.111 11 939.172 7 12.888 89 1 275.401 70 10.111 11 978.741 6 12 1 196.998 50 10.111 11 978.355 3 12.777 78 1 274.871 30 10.111 11 990.383 5 10.555 56 1 045.715 10 10.111 11 943.311 4 10.111 11 903.830 6 C2 90 4.25 678.148 1 4.5 693.822 3 70 4.125 651.534 6 3.25 636.552 9 50 3.25 617.743 3 604.122 8 30 3.5 626.162 3.125 602.238 8 10 3.5 611.311 7 3 594.865 2 R1 90 29.833 33 1 805.866 19.333 33 1 545.443 70 30 1 818.134 18.416 67 1 512.891 50 29.25 1 785.106 17.25 1 454.067 30 28.25 1 789.482 16.333 33 1 429.76 10 22.416 67 1 570.345 14.416 67 1 341.895 R2 90 10.363 64 1 174.672 6.181 818 1 206.2 70 10 1 132.638 5.181 818 1 167.593 50 9.545 455 1 125.548 5.454 545 1 159.591 30 8.909 091 1 096.661 4.090 909 1 022.334 10 8.090 91 1 050.84 4.727 273 977.819 3 从表 3中可以看出，针对C1类数据，本文提出的局部搜索方法平均车辆数高于破坏重建算法，只有在对动态性为10%的数据求解的结果中平均行驶距离少于破坏重建算法；对于C2类数据，本文方法在处理动态性小于90%的4种数据的结果中平均车辆数与平均总行驶距离都少于破坏重建算法；对于R1类数据，在5种动态性数据的处理结果中，本文方法在平均车辆数与平均总行驶距离都少于破坏重建算法；对于R2类数据，在5种动态性数据的处理结果中，本文方法在车辆使用上少于破坏重建算法，在行驶距离上，只有动态性10%和30%的数据处理结果少于破坏重建算法。实验结果表明，对于C1类数据，本文方法在平均车辆数和平均总行驶距离方面比破坏重建算法结果差。对于R2类数据，本文方法减少了车辆的使用，但是增加了行驶距离。而对于C2和R1类数据，本文方法在车辆数和行驶距离方面都有优势。
-
实验数据采用广州运钞车与自动取款机数据，包括35辆车和307个配送点，位置点间的距离为车辆真实运行距离。使用破坏重建算法生成初始调度路线，使用23辆车完成了307个任务点，总距离成本为1 943 882 m(见表 4)。
表 4 初始调度各路线距离成本
Table 4. Cost of Initial Delivery Plan
车辆编号 距离/m 车辆编号 距离/m v002 164 440 v020 123 420 v003 71 046 v021 61 571 v004 49 283 v022 41 822 v005 61 421 v023 54 796 v007 63 603 v024 145 254 v009 64 766 v027 40 167 v012 108 287 v028 80 232 v013 49 944 v029 63 581 v014 59 799 v030 113 027 v015 83 200 v032 53 421 v017 97 488 v034 146 962 v019 146 352 总成本/m 1 943 882 以初始调度结果为前提，本文针对新增任务点与车辆故障两种紧急情况，使用本文提出的局部搜索方法与基于全局的破坏重建算法进行动态调度对比实验，验证本文方法的有效性。
新增任务点情况下的动态调度：车辆配送过程中，假设新增了任务点，任务点数学模型表示为：
$$ \mathit{\boldsymbol{s}} = \left[ {08:14:00\;5:13:00\;900\;113.25\;23.12\;3} \right] $$ 如表 5所示，当任务点新增时，使用本文方法形成的新调度路线使用两辆在运行车辆v005、v014完成任务。直接将新增任务点、所有车辆和未完成任务点通过破坏重建算法进行运算，生成了新的调度路线。新的调度路线使用22辆车进行配送，使用新车v000，有两辆在运行车辆v009和v019不再执行配送任务，需要返回调度中心。破坏重建方法和局部搜索方法的调度结果变更路线如图 6所示，本文方法变更的路线明显较少。从表 5中的车辆调度成本对比可以看出，基于全局方式的破坏重建方法进行动态调度，21辆车的路线发生改变，而使用本文提出的局部搜索的调度方法，只有2辆车的路线发生改变，减少了车辆路线改变带来的额外成本。
表 5 新增任务点后各方法剩余距离成本对比
Table 5. Comparing the Distance Cost of Each Vehicle After Adding the New Task
车辆编号 局部搜索方法 破坏重建方法 车辆编号 局部搜索方法 破坏重建方法 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m v000 0 0 92 750 92 750 v019 101 495 0 33 901 -67 594 v002 129 755 0 139 047 9 292 v020 85 757 0 63 698 -22 059 v003 44 255 0 53 625 9 370 v021 40 588 0 40 588 0 v004 24 031 0 22 972 -1 059 v022 24 859 0 37 836 12 977 v005 58 327 20 498 17 345 -20 484 v023 31 894 0 36 032 4 138 v007 46 657 0 46 698 41 v024 105 498 0 108 331 2 833 v009 41 006 0 21 558 -19 448 v027 26 293 0 26 293 0 v012 70 624 0 66 844 -3 780 v028 47 874 0 47 874 0 v013 30 430 0 29 099 -1 331 v029 37 539 0 39 886 2 347 v014 71 060 34 758 53 575 17 273 v030 70 475 0 84 298 13 823 v015 63 763 0 77 244 13 481 v032 26 371 0 31 627 5 256 v017 59 825 0 69 331 9 506 v034 115 320 0 105 805 -9 515 
图 6 新增任务点的配送方案变更路径对比
Figure 6. Comparison of Scheduling Results Change in Case of Newly Added Task
通过计算可知，全局方式破坏重建方法的运行时间为1 978.456 s，总距离为1 346 257 m；本文方法的运行时间为15 s，总距离为1 353 696 m。可以看出，本文提出的局部搜索方法的运行时间明显少于全局方式破坏重建方法，而距离成本可以满足紧急情况下动态调度的实时性与动态性要求。
车辆故障情况下的动态调度：车辆配送过程中，假设车辆v015发生故障。该车辆数学模型为：
$$ {m_v} = \left\{ {10:00:00, 18:00:00, 113.37, 23.21, 91} \right\} $$ 如表 6所示，采用本文提出的局部搜索方法进行动态调度，使用在运行的8辆车进行配送；直接将所有车辆和未完成任务点通过破坏重建算法进行运算，生成了新的调度方案，该方案共使用了21辆车进行配送，其中使用1辆新车v008，原来在运行的车辆v009、v019和故障车辆v015都不再执行配送任务，所有车辆的路线都发生了改变。两种方法生成的配送方案中改变的路线对比如图 7所示。
表 6 车辆故障后距离成本对比
Table 6. Comparing the Distance Cost of Each Vehicle After Vehicle Breakdown
车辆编号 局部搜索方法 破坏重建方法 车辆编号 局部搜索方法 破坏重建方法 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m v002 129 755 0 139 047 9 292 v019 101 495 0 33 901 -67 594 v003 44 255 0 62 411 18 156 v020 85 757 0 101 837 -16 080 v004 24 031 0 24 034 3 v021 40 588 0 27 994 -12 594 v005 56 971 19 142 103 692 65 863 v022 24 859 0 24 918 59 v007 81 725 35 068 46 699 42 v023 51 769 19 875 39 388 7 494 v008 0 0 71 710 71 710 v024 104 045 -1 453 108 331 2 833 v009 41 006 0 21 558 -19 448 v027 26 293 0 20 642 -5 651 v012 106 770 36 146 84 425 13 801 v028 47 874 0 54 544 6 670 v013 30 430 0 33 381 2 951 v029 37 539 0 39 886 2 347 v014 52 423 16 121 53 575 17 273 v030 70 475 0 67 299 -3 176 v015 0 -63 763 0 -63 763 v032 26 371 0 27 347 976 v017 67 580 7 755 68 197 8 372 v034 79 404 -35 916 105 805 -9 515 
图 7 车辆故障的配送方案变更路径对比
Figure 7. Comparison of Scheduling Results Change in Case of Damaged Vehicle
从表 6中破坏重建方法和局部搜索方法的各个车辆距离成本对比来看，直接使用破坏重建算法，所有车辆路线都发生变化。而本文提出的局部搜索调度方法使用了部分在运行车辆进行调度，其他车辆配送路线保持不变，减少了重新调度带来的成本。
通过计算，全局方式破坏重建方法运行时间为1 651.303 s，总距离为1 360 621 m；本文提出的局部搜索方法运行时间为105.192 s，总距离为1 331 415 m。可以看出，本文方法在距离成本上比直接使用破坏重建算法少约29 km，而且运行时间明显少于后者。在实际情况中，多出的距离成本在紧急情况中是可以承受的，较短的运算时间更符合紧急情况调度，满足紧急情况动态调度的实时性与动态性要求。
-
动态车辆调度一直是车辆调度研究的热点，本文根据物流配送的实际特点，提出了一种基于破坏重建算法的动态车辆调度方法。调度需求分为静态需求和动态需求。对于静态需求，采用破坏重建算法构造生成初始路径，对于出现新增任务点或车辆故障等紧急情况的动态需求，采用局部搜索的动态调度方法设计一种移动策略，形成新的车辆调度方案。使用公开数据集和真实数据进行实验，实验结果表明，本文提出的动态调度方法在需求量较大和小动态性方面有效地提升了实时性和系统运行效率。
A Dynamic Scheduling Method of Logistics Vehicles Based on Ruin and Recreate Algorithm
-
摘要: 随着中国经济的快速发展，物流配送对车辆调度的实时性与应急情况处理能力提出了更高的要求，使用传统车辆调度算法难以满足突发事件实时处理需求。针对紧急情况如车辆故障或新增任务点等，在传统启发式算法——破坏重建算法的基础上提出了一种动态调度方法：局部搜索方法，实现了物流车辆的动态调度，有效提升了车辆调度中应对紧急情况的实时性与动态性。与多目标混合蚁群优化算法进行实验对比，结果验证了破坏重建算法的优势；利用公开数据和真实数据，与全局方式破坏重建车辆调度方法进行对比实验，结果验证了局部搜索动态调度方法的有效性。Abstract:
Objectives With the rapid development of the Chinese economy, logistics distribution has put forward higher requirements on the real-time performance of vehicle scheduling and the ability to deal with emergencies. As traditional vehicle scheduling algorithms usually consider static scheduling tasks, it is difficult to deal with emergencies such as vehicle failure or adding new tasks in real-time. A local search of the dynamic scheduling method is proposed based on the ruin and recreate algorithm. Methods When some vehicle breaks down or a new task is added, the location of the added task node or broken vehicle is obtained and all the nodes are found within a certain range around the location. Based on the initial solution, all the unfinished nodes are searched that are outside the range and on the same path with the nodes mentioned above. The two sets of nodes compose a collection of removal task nodes, which act as the input of the ruin and recreate algorithm to generate new vehicle routes. Results To demonstrate the performance of the proposed method, three experiments are designed and conducted: (1)The data in the Solomon benchmark examples are used in the static scheduling experiment, which is divided into 9 C-type (clustered customers) and 8 R-type (uniformly distributed customers) datasets. The multi-objective hybrid ant colony optimization algorithm is employed as the reference method. Results on the Solomon benchmark datasets show that ruin and recreate algorithm outperforms the reference method with respect to distance cost and the number of vehicles in 14 of 17 datasets. (2) The second experiment is a dynamic scheduling test, and it uses Lackner's benchmark datasets that can be used to demonstrate five different dynamic degrees of 10%, 30%, 50%, 70%, and 90%. The test data contains 240 sub-datasets and is divided into four groups: C1, C2, R1, and R2. In this experiment, the ruin and recreate algorithm is employed as the reference method. Results show that the local search algorithm proposed in this paper outperforms the ruin and recreate algorithm in terms of vehicle usage and driving distance on C2 and R1 datasets, but the ruin and recreate algorithm performs better than the proposed method on C1 dataset. For the R2 dataset, the proposed method reduces the number of vehicles but increases the driving distance. (3) The third experiment is conducted on a real scheduling scenario dataset that contains 35 vehicles and 307 task nodes. Ruin and recreate algorithm is also employed as the reference method in this experiment.In the case of vehicle breakdowns, the proposed method changes 37.5% of vehicle routes while the reference method changes all the routes, and the performance of the proposed method is much better than that of the ruin and recreate algorithm with respect to program running time and driving distance cost. In the case of adding new tasks, the proposed method adjusts only 8.3% vehicle routes while the reference method changes 87.5% of routes. Conclusions The proposed method performs much better than the reference method in terms of running time, but the proposed method costs an additional 0.5% driving distance than the reference method. From the above three experiments, it can be concluded that the ruin and recreate algorithm has advantages in terms of vehicle usages and driving distance for the static scheduling tasks, and for the dynamic scheduling scenario that has a lot of distribution task nodes, the proposed method can solve small‐scale dynamic vehicle routing problem within a very short time and with minor route adjustments. -
Key words:
- ruin and recreate algorithm /
- vehicle routing problem /
- local search /
- dynamic scheduling
-
图 6 新增任务点的配送方案变更路径对比
Figure 6. Comparison of Scheduling Results Change in Case of Newly Added Task
图 7 车辆故障的配送方案变更路径对比
Figure 7. Comparison of Scheduling Results Change in Case of Damaged Vehicle
表 1 符号说明
Table 1. Description of Symbols
符号 符号说明 S={si} 模型中任务点集合, s0表示调度中心 A={ai} 模型中新增任务点集合 M={mki, i=1, 2…k} 模型车辆作为移动节点集合 K={ki, i=1, 2, 3…v} ki表示第i辆车，共有v辆车 lij 任务点i到j路段的长度 tij 任务点i到j路段的车辆运输时间 S' 原有任务点与新增任务点的集合
S'=S∪ACk 车辆k的固定成本 Tj 到达任务点sj的时间 
下载: 导出CSV
表 2 破坏重建算法与多目标混合蚁群优化算法对比结果
Table 2. Comparison Results of Ruin and Recreate and Multi-objective Hybrid Ant Colony Optimization Algorithm
数据集 最优解 多目标混合蚁群优化算法 破坏重建算法 车辆数/辆 成本/m 车辆数/辆 成本/m 耗时/s 车辆数/辆 成本/m 耗时/s C101 10 828.94 10 828.94 0.428 10 828.94 3.610 C102 10 828.94 10 831.42 0.497 10 828.94 3.653 C103 10 828.06 10 835.46 0.508 10 828.06 3.909 C104 10 824.78 10 839.53 0.485 10 852.35 6.833 C105 10 828.94 10 828.94 1.029 10 828.94 3.712 C106 10 828.94 10 828.94 1.352 10 828.94 3.911 C107 10 828.94 10 833.78 1.469 10 828.94 3.987 C108 10 828.94 10 838.15 1.584 10 828.94 3.735 C109 10 828.94 10 828.94 1.720 10 828.94 9.758 R101 20 1 650.80 20 1 675.45 1.598 19 1 654.41 80.382 R102 17 1 486.12 18 1 447.20 1.484 18 1 487.41 76.447 R103 14 1 213.62 15 1 239.40 1.297 13 1 224.55 60.114 R104 10 982.01 12 974.24 1.384 10 998.92 61.737 R105 14 1 377.11 15 1 385.67 1.492 14 1 379.73 64.366 R106 12 1 252.03 14 1 258.61 1.373 14 1 257.90 81.023 R107 10 1 113.69 12 1 110.54 1.436 11 1 097.80 56.898 R108 9 964.38 11 961.23 1.275 11 959.52 19.128
下载: 导出CSV
表 3 两种方法的计算结果比较
Table 3. Computational Results of Two Methods
实例 动态性/% 破坏重建方法 局部搜索方法 平均车辆数/辆 平均总行驶距离/m 平均车辆数/辆 平均总行驶距离/m C1 90 10.111 11 939.172 7 12.888 89 1 275.401 70 10.111 11 978.741 6 12 1 196.998 50 10.111 11 978.355 3 12.777 78 1 274.871 30 10.111 11 990.383 5 10.555 56 1 045.715 10 10.111 11 943.311 4 10.111 11 903.830 6 C2 90 4.25 678.148 1 4.5 693.822 3 70 4.125 651.534 6 3.25 636.552 9 50 3.25 617.743 3 604.122 8 30 3.5 626.162 3.125 602.238 8 10 3.5 611.311 7 3 594.865 2 R1 90 29.833 33 1 805.866 19.333 33 1 545.443 70 30 1 818.134 18.416 67 1 512.891 50 29.25 1 785.106 17.25 1 454.067 30 28.25 1 789.482 16.333 33 1 429.76 10 22.416 67 1 570.345 14.416 67 1 341.895 R2 90 10.363 64 1 174.672 6.181 818 1 206.2 70 10 1 132.638 5.181 818 1 167.593 50 9.545 455 1 125.548 5.454 545 1 159.591 30 8.909 091 1 096.661 4.090 909 1 022.334 10 8.090 91 1 050.84 4.727 273 977.819 3
下载: 导出CSV
表 4 初始调度各路线距离成本
Table 4. Cost of Initial Delivery Plan
车辆编号 距离/m 车辆编号 距离/m v002 164 440 v020 123 420 v003 71 046 v021 61 571 v004 49 283 v022 41 822 v005 61 421 v023 54 796 v007 63 603 v024 145 254 v009 64 766 v027 40 167 v012 108 287 v028 80 232 v013 49 944 v029 63 581 v014 59 799 v030 113 027 v015 83 200 v032 53 421 v017 97 488 v034 146 962 v019 146 352 总成本/m 1 943 882
下载: 导出CSV
表 5 新增任务点后各方法剩余距离成本对比
Table 5. Comparing the Distance Cost of Each Vehicle After Adding the New Task
车辆编号 局部搜索方法 破坏重建方法 车辆编号 局部搜索方法 破坏重建方法 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m v000 0 0 92 750 92 750 v019 101 495 0 33 901 -67 594 v002 129 755 0 139 047 9 292 v020 85 757 0 63 698 -22 059 v003 44 255 0 53 625 9 370 v021 40 588 0 40 588 0 v004 24 031 0 22 972 -1 059 v022 24 859 0 37 836 12 977 v005 58 327 20 498 17 345 -20 484 v023 31 894 0 36 032 4 138 v007 46 657 0 46 698 41 v024 105 498 0 108 331 2 833 v009 41 006 0 21 558 -19 448 v027 26 293 0 26 293 0 v012 70 624 0 66 844 -3 780 v028 47 874 0 47 874 0 v013 30 430 0 29 099 -1 331 v029 37 539 0 39 886 2 347 v014 71 060 34 758 53 575 17 273 v030 70 475 0 84 298 13 823 v015 63 763 0 77 244 13 481 v032 26 371 0 31 627 5 256 v017 59 825 0 69 331 9 506 v034 115 320 0 105 805 -9 515
下载: 导出CSV
表 6 车辆故障后距离成本对比
Table 6. Comparing the Distance Cost of Each Vehicle After Vehicle Breakdown
车辆编号 局部搜索方法 破坏重建方法 车辆编号 局部搜索方法 破坏重建方法 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m 距离/m 改变/m v002 129 755 0 139 047 9 292 v019 101 495 0 33 901 -67 594 v003 44 255 0 62 411 18 156 v020 85 757 0 101 837 -16 080 v004 24 031 0 24 034 3 v021 40 588 0 27 994 -12 594 v005 56 971 19 142 103 692 65 863 v022 24 859 0 24 918 59 v007 81 725 35 068 46 699 42 v023 51 769 19 875 39 388 7 494 v008 0 0 71 710 71 710 v024 104 045 -1 453 108 331 2 833 v009 41 006 0 21 558 -19 448 v027 26 293 0 20 642 -5 651 v012 106 770 36 146 84 425 13 801 v028 47 874 0 54 544 6 670 v013 30 430 0 33 381 2 951 v029 37 539 0 39 886 2 347 v014 52 423 16 121 53 575 17 273 v030 70 475 0 67 299 -3 176 v015 0 -63 763 0 -63 763 v032 26 371 0 27 347 976 v017 67 580 7 755 68 197 8 372 v034 79 404 -35 916 105 805 -9 515
下载: 导出CSV
-
[1] 国家邮政局. 2019年11月中国快递发展指数报告[R/OL]. (2019-12-04)[2020-01-01]. http://www.spb.gov.cn/xw/dtxx_15079/201912/t20191204_1983526.html National Bureau of China. China Express Development Index Report in Nvember, 2019[R/OL]. (2019-12-04)[2020-01-01]. http://www.spb.gov.cn/xw/dtxx_15079/201912/t20191204_1983526.html [2] 姚莉. 移动配送模式下快速响应需求的车辆动态调度研究[D]. 北京: 北京交通大学, 2017 Yao Li. Research on Vehicle Dynamic Scheduling with Quickly Response Demand of Mobile Distribution Model[D]. Beijing: Beijing Jiaotong University, 2017 [3] Ting C J, Huang C H. An Improved Genetic Algorithm for Vehicle Routing Problem with Time Windows[J]. International Journal of Industrial Engineering, 2018, 12(3): 218-228 doi: 10.1109/ICICCI.2010.42 [4] Tang J, Guan J, Yu Y, et al. Beam Search Combined with MAX-MIN Ant Systems and Benchmarking Data Tests for Weighted Vehicle Routing Problem[J]. IEEE Transactions on Automation Science and Engineering, 2014, 11(4): 1 097-1 109 doi: 10.1109/TASE.2014.2357911 [5] Ferreira J C, Steiner M T A, Guersola M S. A Vehicle Routing Problem Solved Through Some Metaheuristics Procedures: A Case Study[J]. IEEE Latin America Transactions, 2017, 15(5): 943-949 doi: 10.1109/TLA.2017.7910210 [6] 涂伟, 李清泉, 方志祥. 一种大规模车辆路径问题的启发式算法[J]. 武汉大学学报·信息科学版, 2013, 38(3): 59-62 http://ch.whu.edu.cn/article/id/24 Tu Wei, Li Qingquan, Fang Zhixiang. A Heuristic Algorithm for Large Scale Vehicle Routing Problem[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 59-62 http://ch.whu.edu.cn/article/id/24 [7] Lund K, Madsen O B G, Rygaard J. Vehicle Routing Problems with Varying Degrees of Dynamism[R]. Lyngby, Denmark: Technical University of Denmark, 1996 [8] Powell W B. A Stochastic Formulation of the Dynamic Assigment Problem, with an Application to Truckload Motor Carriers[J]. Transportation Science, 1996, 30(3): 195-219 doi: 10.1287/trsc.30.3.195 [9] Slater A. Specification for a Dynamic Vehicle Routing and Scheduling System[J]. International Journal of Transport Management, 2002, 1(1): 29-40 doi: 10.1016/S1471-4051(01)00004-0 [10] Ferrucci F, Bock S, Gendreau M. A Pro-active Real-Time Control Approach for Dynamic Vehicle Routing Problems Dealing with the Delivery of Urgent Goods[J]. European Journal of Operational Research, 2013, 225(1): 130-141 doi: 10.1016/j.ejor.2012.09.016 [11] Godfrey G A, Powell W B. An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, Ⅰ: Single Period Travel Times[J]. Transportation Science, 2002, 36(1): 21-39 doi: 10.1287/trsc.36.1.21.570 [12] Godfrey G A, Powell W B. An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, Ⅱ: Multiperiod Travel Times[J]. Transportation Science, 2002, 36(1): 40-54 doi: 10.1287/trsc.36.1.40.572 [13] Larsen A, Solomon M M M. A Priori Dynamic Traveling Salesman Problem with Time Windows[J]. Transportation Science, 2004, 38(4): 459-472 doi: 10.1287/trsc.1030.0070 [14] Ichoua S, Gendreau M, Potvin J Y. Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching[J]. Transportation Science, 2006, 40(2): 211-225 doi: 10.1287/trsc.1050.0114 [15] Mitrovic-Minic S, Laporte G. Waiting Strategies for the Dynamic Pickup and Delivery Problem with Time Windows[J]. Transportation Research Part B: Methodological, 2004, 38B(7): 635-655 http://www.sciencedirect.com/science/article/pii/S0191261503001073 [16] Ozbaygin G, Savelsbergh M. An Iterative Re-optimization Framework for the Dynamic Vehicle Routing Problem with Roaming Delivery Locations[J]. Transportation Research Part B: Methodological, 2019, 128: 207-235 doi: 10.1016/j.trb.2019.08.004 [17] Holland J H. Adaptation in Natural and Artificial Systems[M]. Ann Arbour: MIT Press, 1975 [18] Ghannadpour S F, Noori S, Tavakkoli-Moghaddam R, et al. A Multi-objective Dynamic Vehicle Routing Problem with Fuzzy Time Windows: Model, Solution and Application[J]. Applied Soft Computing, 2014, 14: 504-527 doi: 10.1016/j.asoc.2013.08.015 [19] Okulewicz M, Mańdziuk J. A Metaheuristic Approach to Solve Dynamic Vehicle Routing Problem in Continuous Search Space[J]. Swarm and Evolutionary Computation, 2019, DOI: 10.1016/j.swevo.2019.03.008 [20] Zheng J, Zhang Y. A Fuzzy Receding Horizon Control Strategy for Dynamic Vehicle Routing Problem[J]. IEEE Access, 2019, 7: 151 239-151 251 doi: 10.1109/ACCESS.2019.2948154 [21] Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transactions on Systems Man and Cybernetics, 1996, 26(1): 29-41 doi: 10.1109/3477.484436 [22] Necula R, Breaban M, Raschip M. Tackling Dynamic Vehicle Routing Problem with Time Windows by Means of Ant Colony System[C]//IEEE Congress on Evolutionary Computation, San Sebastian, Spain, 2017 http://www.sciencedirect.com/science/article/pii/S0307904X16303365 [23] Rizzoli A E, Montemanni R, Lucibello E, et al. Ant Colony Optimization for Real-World Vehicle Routing Problems[J]. Swarm Intelligence, 2007, 1(2): 135-151 doi: 10.1007/s11721-007-0005-x [24] Kennedy J, Eberhart R. Particle Swarm Optimization[C]//International Conference on Neural Networks, Perth, WA, Australia, 1995 [25] Xu Haitao. Solving Dynamic Vehicle Routing Problem Using Enhanced Genetic Algorithm with Penalty Factors[J]. International Journal of Performability Engineering, 2018, 14(4): 611-620 [26] Abdallah A M F M, Essam D L, Sarker R A. On Solving Periodic Re-optimization Dynamic Vehicle Routing Problems[J]. Applied Soft Computing, 2017, 55: 1-12 doi: 10.1016/j.asoc.2017.01.047 [27] Sarasola B, Doerner K F, Schmid V, et al. Variable Neighborhood Search for the Stochastic and Dynamic Vehicle Routing Problem[J]. Annals of Operations Research, 2016, 236: 425-461 doi: 10.1007/s10479-015-1949-7 [28] de Armas J, Melián-Batista B. Constrained Dynamic Vehicle Routing Problems with Time Windows[J]. Soft Computing, 2015, 19(9): 2 481-2 498 doi: 10.1007/s00500-014-1574-4 [29] de Armas J, Melián-Batista B. Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with Time Windows[J]. Computers and Industrial Engineering, 2015, 85: 120-131 doi: 10.1016/j.cie.2015.03.006 [30] Gendreau M, Guertin F, Potvin J Y, et al. Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pick-Ups and Deliveries[J]. Transportation Research Part C: Emerging Technologies, 2006, 14(3): 157-174 doi: 10.1016/j.trc.2006.03.002 [31] Hong L. An Improved LNS Algorithm for Real-Time Vehicle Routing Problem with Time Windows[J]. Computers and Operations Research, 2012, 39(2): 151-163 doi: 10.1016/j.cor.2011.03.006 [32] Chen S, Chen R, Wang G G, et al. An Adaptive Large Neighborhood Search Heuristic for Dynamic Vehicle Routing Problems[J]. Computers and Electrical Engineering, 2018, 67: 596-607 doi: 10.1016/j.compeleceng.2018.02.049 [33] Pureza V, Laporte G. Waiting and Buffering Strategies for the Dynamic Pickup and Delivery Problem with Time Windows[J]. Information Systems and Operational Research, 2008, 46(3): 165-176 doi: 10.3138/infor.46.3.165 [34] Schrimpf G, Schneider J, Stamm-Wilbrandt H, et al. Record Breaking Optimization Results Using the Ruin and Recreate Principle[J]. Journal of Computational Physics, 2000, 159(2): 139-171 doi: 10.1006/jcph.1999.6413 [35] Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research, 1987, 35(2): 254-265 doi: 10.1287/opre.35.2.254 [36] Zhang H, Zhang Q, Ma L, et al. A Hybrid Ant Colony Optimization Algorithm for a Multi-objective Vehicle Routing Problem with Flexible Time Windows[J]. Information Sciences, 2019, 490: 166-190 doi: 10.1016/j.ins.2019.03.070 [37] Kalayci C B, Kaya C. An Ant Colony System Empowered Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery[J]. Expert Systems with Application, 2016, 66: 163-175 doi: 10.1016/j.eswa.2016.09.017 [38] Gao S, Wang Y, Cheng J, et al. Ant Colony Optimization with Clustering for Solving the Dynamic Location Routing Problem[J]. Applied Mathematics and Computation, 2016, 285: 149-173 doi: 10.1016/j.amc.2016.03.035 [39] Deepa T K, Amuthan A. Cellular Automata-Based Improved Ant Colony-Based Optimization Algorithm for Mitigating DDoS Attacks in VANETs[J]. Future Generation Computer Systems, 2018, 82: 304-314 doi: 10.1016/j.jocs.2017.12.012 [40] Kaabachi I, Jriji D, Krichen S. An Improved Ant Colony Optimization for Green Multi-depot Vehicle Routing Problem with Time Windows[C]//The 18th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing Kanazawa, Japan, 2017 doi: 10.1016/j.future.2017.11.043 [41] Wang Y, Wang L, Peng Z, et al. A Multi Ant System Based Hybrid Heuristic Algorithm for Vehicle Routing Problem with Service Time Customization[J]. Swarm and Evolutionary Computation, 2019, 50: 100563 doi: 10.1016/j.swevo.2019.100563 [42] Jabir E, Panicker V V, Sridharan R. Design and Development of a Hybrid Ant Colony-Variable Neighbourhood Search Algorithm for a Multi-depot Green Vehicle Routing Problem[J]. Transportation Research Part D: Transport and Environment, 2017, 57: 422-457 doi: 10.1016/j.trd.2017.09.003 [43] Ding Q, Hu X, Sun L, et al. An Improved Ant Colony Optimization and Its Application to Vehicle Routing Problem with Time Windows[J]. Neurocomputing, 2012, 98: 101-107 doi: 10.1016/j.neucom.2011.09.040 -
点击查看大图
图(7) / 表(6)
计量
- 文章访问数: 626
- HTML全文浏览量: 264
- PDF下载量: 51
- 被引次数: 0
