车辆路径优化算法

1、：数据魔术师扫码即可关注大量运筹及人工智能算法源代码车辆路径优化算法：现状和罗志兴 南京大学工程管理学院秦虎华技大学管理学院2019年5月29日：数据魔术师扫码即可关注大量运筹及人工智能算法源代码问题介绍Problem Introduction01精确算法Exact Algorithm02摘要启发式算法Heuristic03高效启发式算法设计Efficient Heuristic Design04通用启发式算法设计General Heuristic Framework05问题介绍Problem Introduction：数据魔术师扫码即可关注大量运筹及人工智能算法源代码问题的定义基础约束每一辆

2、车必须从仓库出发并最终回到仓库。给定一个仓库、一组位于不同的位置的顾客以及每一个顾客都必须有且仅有一次。一个车队，为车队的每一辆车驶路径，优化总的物流成本。服务顾客的行常见约束容量约束：每个顾客都有一个需求，一条路径上总的顾客需求不能超过车辆容量。工作时长约束：车辆从仓库出发到返回仓库的时长不能超过限制。时间窗约束：每一个顾客都有一个服务时间窗，车辆在顾客的服务开始时间必须落在该时间窗内。目标函数车辆数目、车辆行驶总里程、车辆总的工作时长、车辆使用固定成本、顾客。问题拓展取货送货、多车型、多仓库 、多行程、Team Orienteering Problem、Time-Dependent Tra

3、vel Time等。和其他组合优化问题结合：三维装箱、选址、库存管理等。参数随机：随机优化、鲁棒优化等。4车辆路径算法分类：数据魔术师扫码即可关注大量运筹及人工智能算法源代码构造算法Insertion Based Construction Heuristic Saving Based Construction Heuristic动态通常用于求解只有一辆车的路径问题设置属于动态abel-Setting Algorithm）本质上基于邻域搜索的算法Tabu Search Iterative Local Search基于分支定界的算法拉格朗日松弛（Lagrangian Relaxation） 分支切

4、割（Branch-and-Cut）分支定价（Branch-and-Price）Benders Decomposition精确算法启发式基于大规模邻域搜索的算法Adaptive Large Neighborhood Search Ejection Pool Based Search基于群体的算法Genetic Algorithm Particle Swarm Optimization基于路径枚举的算法Roberto Baldacci提出的算法框架。利用一个很强的下界和一个很好的上界，枚举出所有可能最优解的路径，然后利用MIP求解器求解一个集合划分模型获取最优解。5：数据魔术师扫码即可关注大量运筹

5、及人工智能算法源代码精确算法Exact AlgorithmVRPTW边-流（Arc-Flow）模型𝑥,：0-1决策变量，当边(𝑖, 𝑗)被某辆车使用时为1，否则为0。𝐺 = (𝑉, 𝐴)表示一个完全有向图，其中𝑉 =0,1, , 𝑛, 𝑛 + 1表示节点集合，𝐴表示边集合。一个仓库、一组顾客、一组相同类型的车辆。𝑎：非负连续变量，表示节点𝑖的服务开始时间。车辆必须从仓库出发并回到仓库。节点0和Ү

6、99; + 1表示仓库。𝑑：非负连续变量，表示车辆离开节点𝑖时载货量。每个节点都必须一次。𝑁 = 1, , 𝑛表示顾客的节点集合。容量约束。𝑞𝑖表示节点𝑖的需求（𝑞0 = 0）。𝑒𝑖, 𝑙𝑖表示节点𝑖的服务时间窗，其中𝑒0和𝑙0分别表示车辆最早离开仓库和最晚回到仓库的时间。时间窗约束。最小化车辆行驶里程。𝑄表示车辆容量。𝐾表示

7、可用的车辆集合。𝑐𝑖, 𝑗和𝑡𝑖, 𝑗分别表示边(𝑖, 𝑗)的长度和时间。7决策变量符号问题描述VRPTW边-流（Arc-Flow）模型最小化车辆行驶里程。每个节点都必须一次。从仓库出发的车辆数量必须等于回到仓库的车辆数量， 并且小于等于可用车辆数量。顾客节点的流平衡约束。节点服务开始时间传递约束，可以使用Big-M 法进行线性化处理。车辆载货量传递约束，可以使用Big-M法进行线性化处理。时间窗约束。容量约束。8合法不等式（Valid Inequalities）Ca

8、pacity Inequalities 𝑞,𝑥, 𝑆 𝑁,𝑄Incompatible Pair InequalitiesLet 𝑖 𝑗 be a pair of incompatible nodes and𝑃 = 𝑖, 𝑘, , 𝑘 , 𝑗 be a path in 𝐺. Then the following inequalities in valid:𝑥,+ ү

9、09; , + + 𝑥, + 𝑥,𝑃 2𝑥 , 𝑆 𝑁 ,𝑥, + 𝑥, + + 𝑥 , + 𝑥, 𝑃 2, P 9 𝑞𝑄分支切割法𝑥𝑥 𝑍, 𝑐< 𝑈𝐵分支𝑥𝑥 𝑍, 𝑐< 𝑈𝐵

10、9909;𝑥 𝑍, 𝑐< 𝑈𝐵更新UB分支𝑥𝑥𝑥 𝑍, 𝑐< 𝑈𝐵𝑐> 𝑈𝐵否是否找到𝑥不满足的不等式是分支剪枝10将找到的不等式加入模型返回最优解x*求解Separation Problem寻找𝑥不满足的合法不等式根据最优解𝑥构造每一类不等式对应的Separation Problem求解边-

11、流模型的线性松弛获得最优解𝑥VRPTW集合划分（Set-Partitioning）模型符号 𝑅表示可行路径的集合。 𝑐表示路径𝑟的行驶里程。 𝛼,是一个0-1常量，假如路径𝑟包含了顾客𝑖，则取1，否则取0.决策变量 𝜃是0-1决策变量，假如路径𝑟出现在最优解中，则取1，否则取0.11分支定价法𝑥𝑥 𝑍, 𝑐< 𝑈𝐵分支𝑥𝑥

12、; 𝑍, 𝑐< 𝑈𝐵𝑥𝑥 𝑍, 𝑐< 𝑈𝐵是否找到reduced cost 为负的column?是否更新UB> 𝑈𝐵分支𝑥𝑥𝑥 𝑍, 𝑐< 𝑈𝐵𝑐分支剪枝12将找到的column加入RMP返回最优解x*设计专门算法求解Pricing Problem使用Si

13、mplex求解Restricted Master Problem（RMP）定价问题符号 𝜋表示约束条件（12）的对偶变量。 𝜋表示约束条件（13）的对偶变量。决策变量 x, 是0-1决策变量，假如车辆使用边(i,j)， 则取1，否则取0.算法设置Algorithm）abel-Setting13设置法定义里的一个状态，表示 一个对应动态一条从仓库出发到达某个节点的路径.拓展方程 用于拓展，达到枚举路径的目的。占优准则 识别那些可以被安全删除的进而算法. 一个被另外一个占优，被占优的可以被安全删除.14设置法给定一条边(𝑖, 𝑗)和一

14、个𝐿，通过拓展可以生成一个新𝑐表示的reduced cost。𝐿𝑐 = 𝑐 + 𝑐, 𝜋𝑎表示车辆在节点𝑖的服务开始时间。𝑎 = max𝑎 + 𝑠 + 𝑡, , 𝑒 𝑢表示车辆在节点𝑖的载货量。𝑢 = 𝑢 + 𝑞= 1, 𝑣, = 1 𝑜𝑟

15、19896; = 𝑗𝑣,是0-1常量，当对应的路径经过节点𝑗时，取1，否则，取0；𝑣,0, 𝑜𝑡𝑒𝑟𝑤𝑖𝑠𝑒给两个关于节点i的𝐿和𝐿，假如满足条件，则𝐿占优𝐿𝑐 𝑐𝑎 𝑎𝑢 𝑢𝑣 𝑣 , 𝑗 = 1,

16、 , 𝑛,15占优准则拓展方程𝐿 = (𝑐, 𝑎, 𝑢, 𝑣, , 𝑣,)是 一个关于节点𝑖的设置法Algorithm 1: LabelSetting()1.2.3.4.5.6.7.8.9.10.11.Set = = 𝑖 = 0, , 𝑛Create an initial label 𝐿 and add it to while(, )Choose a label 𝐿 ( , 𝑖 w

17、899; + 1).for ( 𝑖, 𝑗 𝐴)If (extension through arc (𝑖, 𝑗) is feasible )Extend 𝐿 through (𝑖, 𝑗) to create a new label 𝐿If (𝐿 is not dominated by any labels in ) Add 𝐿 to Remove the labels in dominated by 𝐿ac

18、cording to the extension functionsRemove 𝐿 from and add it to 12. Return the route with the minimum reduced cost in 16设置法设置法技巧Decremental Space Search首先放松节点只能一次约束，然Label Pruning通过下界删除不可能拓展成最优解的。后通过机制逐渐恢复该约束。State Space RelaxationNg-route Relaxation放松节点只能被一次，路径中存在子环。由Roberto Baldacci提出，类似Decr

19、emental Space Search，效果更好。Bounded Bidirectional Search双向搜过，减少生成数量。17：数据魔术师扫码即可关注大量运筹及人工智能算法源代码启发式算法Heuristic构造法Algorithm 2: InsertionBasedConstruction()1.2.3.𝑠 , 𝐶 𝑁While(𝐶 )find a customer 𝑖 and a place 𝑝 with the smallest cost increment.If (customer

20、𝑖 and place 𝑝 exist) Insert customer 𝑖 into 𝑝 in 𝑠 Remove 𝑖 from 𝐶elseConstruct an empty route and add it to 𝑠Return 𝑠4.5.6.7.8.9.Insertion Based Construction AlgorithmAlgorithm 3: SavingBasedConstruction()1.2.𝑠 Construc

21、t |𝑁| routes of which each serves a customer in 𝐶Add the routes to 𝑠While(True)find the best saving 𝑜 in 𝑠If saving 𝑜 does not existBreakModify 𝑠 according saving 𝑜Return s2123.4.5.6.7.8.9. 0 0 Saving Based Construction Algorithm基于邻域搜索的

22、算法Algorithm 4: LocalSearch(𝑠, 𝑚𝑎𝑥𝐼𝑡𝑒𝑟, 𝑠𝑎𝑘𝑇𝑒𝑛𝑢𝑟𝑒)𝑖 1, 𝑗 0, 𝑠 𝑠While(𝑖 < 𝑚𝑎𝑥𝐼𝑡

23、9890;𝑟)1.2.3.4.5.6.7.8.9.10.11.12.𝑠成本𝑁(𝑠)𝑁(𝑠)𝑠𝑠 𝑎𝑟𝑔𝑚𝑖𝑛 𝑐(𝑠)𝑠: 第𝑖迭代的解。𝑠If (c(𝑠) < 𝑐(𝑠 )𝑠 𝑠, 𝑗 0els

24、e𝑗 + +If (𝑗 = 𝑠𝑎𝑘𝑇𝑒𝑛𝑢𝑟𝑒)𝑠 𝑆𝑎𝑘𝑒(𝑠)𝑗 0𝑖 + +Return 𝑠𝑠𝑁(𝑠) : 解𝑠的邻域。𝑁(𝑠)𝑠𝑠⻕

25、8;𝑎𝑥𝐼𝑡𝑒𝑟 : 最大迭代次数。Shake𝑠𝑠𝑎𝑘𝑇𝑒𝑛𝑢𝑟𝑒 ：执行扰动的周期𝑠𝑆𝑎𝑘𝑒(𝑠) : 对解𝑠进行随机扰动。迭代次数20符号常见邻域搜索算子Exchange算子Relocate算子(c)Cross算子21常见邻域搜

26、索算子Or-Opt算子3-Opt算子222-Exchange算子Cross-Exchange算子：数据魔术师扫码即可关注大量运筹及人工智能算法源代码基于邻域搜索的算法收敛速度快 每一次迭代速度较快，可以在比较短时间内收敛到一个局部最优解。 是其他很多复杂的启发式算法的基础。 适用于计算时间要求比较高的环境。算法最终收敛的结果依赖初始解基于邻域搜索的算法搜索的空间是在初始解邻域空间附近，搜索的空间有限。对于一些约束条件非常紧的问题，初始解的邻域空间可能很小甚至是空集，这种情况不适用基于邻域搜索的算法算法结构简单 在邻域搜索的基础上，衍生出很多各种各样的启发式算法，例如tabu search, i

27、terative local search, simulated annealing等。算子设计难度大邻域搜索的算子必须在算子搜索范围以及算子复杂度之间做一个平衡.高效邻域搜索算子的实现是基于邻域搜索算法设计的。23基于大规模邻域搜索的算法Algorithm 4: ALNS(𝑠, 𝑚𝑎𝑥𝐼𝑡𝑒𝑟, 𝐼𝐻𝑆, 𝑅𝐻𝑆)𝑠普通邻域𝑁(ү

28、04;)𝑠𝑖 1, 𝑠 𝑠While(𝑖 < 𝑚𝑎𝑥𝐼𝑡𝑒𝑟)Select an insertion heuristic 𝑖 from 𝐼𝐻𝑆 and a removal heuristic 𝑟 from 𝑅𝐻𝑆.Modify s by heuristics ⻕

29、4; and 𝑟 to get a new solution 𝑠If (c(𝑠) < 𝑐(𝑠)𝑠 𝑠If (accept(𝑠) = True)s 𝑠𝑖 + +Return 𝑠1.2.3.4.5.6.7.8.9.10.大规模邻域𝑁(𝑠)2,3,6,8,100-1-2-3-4-00-1-4-00-10-1-4-0An insertion heuristicA removal heuris

30、tic0-5-6-7-8-00-9-10-00-5-7-00-9-00-2-5-7-3-00-9-6-8-0大规模邻域搜索算子操作0-1-2-3-4-00-1-6-3-4-0Exchange算子0-5-6-7-8-00-5-2-7-8-00-9-10-00-9-10-0普通邻域搜索算子操作24基于大规模邻域搜索的算法Random Removal Heuristic从解中随机删除一定数量的顾客Basic Greedy Insertion Heuristic将顾客到解中成本增量最少的位置。Worst Removal Heuristic删除解中一定数量成本最高的顾客Neighborhood Grap

31、h Removal HeuristicRegret Insertion Heuristic每一迭代首先计算每一个顾客的regret value，然利用一个图搜索过程中的一些历史信息，基于这个图删除给定数量的顾客后将regret value最大的顾客最少的位置。到解中成本增量25：数据魔术师扫码即可关注大量运筹及人工智能算法源代码基于大规模邻域搜索的算法遍历的解空间更大 遍历的解空间越大，越是有利于获得更好的解。 相比普通的邻域搜索，大规模邻域搜索陷入局部最的概率较小。算法收敛速度较慢 大规模邻域搜索的目的性不及普通的邻域搜索，普通的邻域搜索在每一迭代移动的方向是邻域中最好的解。 大规模邻域搜索

32、不适用于实时性要求较高的场景。适用问题范围更广搜索粒度过大 在每一次迭代，大规模邻域搜索并没有搜索邻域空间内所有的解，只是根据特定的策略选取了邻域空间内的某个解，因此很大概率会错过了邻域空间内其他高质量的解。 大规模邻域搜索基于删除和节点的启发式算法，这些启发式算法往往不需要依赖特定的问题结构，通用性更强。26基于群体的算法Return the best solutionEncodingYes𝑠𝑠𝑠NoReplacementTerminatio n criterion基于搜索的算法Evaluation𝑠,𝑠,

33、19904;,𝑠,𝑠,𝑠,𝑠,𝑠,𝑠,基于群体的算法DecodingSelectionCrossoverMutation27New solutionsRanking of population membersNew populationChromosomes with different fitnessPopulation of possible solutionInitialization of population：数据魔术师扫码即可关注大量运筹及人工智能算法源代码基于群体的算法适用多目标优化

34、多目标优化问题需要返回Pareto最优解，而基于群体的算法在搜索过程中维护一个群体的解有助于寻找Pareto 最优解。算法收敛速度较慢 每一次迭代需要的时间较长。 不太适用于实时性要求较高的场景。适合并行计算Encoder和Decoder设计难度大 对于约束复杂的问题，通用的Encoder和Decoder可能 种群中每一个合并发进行。的evaluation、mutation等操作很适不能满足需求，需要设计有性的Encoder和Decoder。28：数据魔术师扫码即可关注大量运筹及人工智能算法源代码高效启发式算法设计Efficient Heuristic Design问题介绍给定一个仓库、一组顾

35、客和一组充电站。容量约束（两个维度）。固定成本。顾客同时需要取货和送货。时间窗约束。行驶成本。一辆车回到仓库多次。车辆电量约束。充电成本。车辆在行驶过程中到充电站充电，电量等待成本。必须充满但充电时间固定。车型有两种，货物容量、电池容量、行驶成本、固定成本有所不同。顾客的货物有重量和体积两个属性。每个顾客有一个服务时间窗。30目标函数约束条件问题设置：数据魔术师扫码即可关注大量运筹及人工智能算法源代码数据特点与计算条件算例规模较大最大规模算例包含1500个顾客和100个充电站， 最小规模算例包含1000个顾客和100个充电站车辆的行驶距离成本占比很高将最小化行驶距离作为首要目标。处理器：I5-

36、7200U 内存：8G计算时间：5分钟距离和时间矩阵不满足三角定律从A点到B点的行驶距离和时间有可能大于从A点经过C点到达B点的行驶距离和时间距离行驶成本，1号车低于2号车约17%尽可能多用1号车，简化车型选择决策。顾客的服务时间窗和容量约束都较紧顾客在地图上分布比较平均不适合将问题划分成几个小规模问题进行求解路径上节点个数太多，车辆数目有可能比较多，路径间的算子影响可能比路径内的算子更大31算法设计思想初始解构造Insertion Based Construction Algorithm初始构造算法框架Tabu Search算法框架算子Relocate、Exchange、Cross和一个La

37、bel-Setting算法优化充电桩分布。算子缩小邻域空间采用一些方法忽略邻域中不是那么有希望的空间。缩小邻域空间32高效的邻域遍历33消除冗余计算O(1)时间复杂度计算邻域解的目标值O(1)时间复杂度检验邻域解的检测以及目标值计算分析定义推导实现分析约束定义属性推导递推表达式算法实现分析约束对于路径的影响根据影响，对路径的节点定义若干属性创建递推表达式计算属性的值实现O(1)时间复杂度34检测以及目标值计算假设给定一个顾客𝑖和路径𝑟 = (𝑖, 𝑖, , 𝑖)，我们以将顾客𝑖法性以及计算新的路径成

38、本。到𝑖和𝑖之间作为例子，介绍如何在𝑂(1)时间复杂度内检测新的路径( , 𝑖 , 𝑖, 𝑖, )的 合时间窗约束𝑒= 𝑒, 𝑙 = 𝑙: 车辆在节点𝑖 最早的服务开始时间𝑒𝑒𝑒= max+ 𝑠+ 𝑡, , 𝑒, 𝑗 = 2, , 𝑘𝑙 : 车辆在节点𝑖最晚的服务

39、开始时间 𝑙𝑙= m𝑖𝑛 𝑠 𝑡 , 𝑙, 𝑗 = 1, . , 𝑘 1 依据上述递推表达式可以计算出𝑒 和𝑙 ，如果𝑒 𝑙 ，则新的路径满足时间窗约束35递推表达式属性消除冗余计算以Exchange算子为例 解s的每个邻域解对应一个值 求s的邻域解可以借助s的邻域解 涉及𝑟和𝑟上的点才需要重新计算 我们有100-300条路径，因此每次迭代绝大多数不需要重新

40、计算 消除了冗余计算，邻域搜索额效率提高的倍数约等于车辆的数目。36通用启发式算法设计General Heuristic Framework：数据魔术师扫码即可关注大量运筹及人工智能算法源代码目的学生培养需求降低VRP算法编写难度. 吸引学生从事运筹优化算法设计研究工作.项目开发需求可以快速响应企业提出的业务需求. 降低开发成本.基金结题需求算法研究需求减少重复开发，提高新算法开发速度.提供一个算法比较的基准.完成当年基金申请书里的预期成果.38效率在大部分经典的VRP上，接近文献中最好的算法。通用性拓展性通用性能够求解文献中常见的车辆路径问题。问题的约束和目标函数可以根据需求自由添加或删除。

41、提供常见的算子和算法供用户使用。效率拓展性提供接口让用户可以处理新引入的约束或目标函数，不需要对算法架构进行改动。39开发进度其他特色目标函数约束条件支持多线程并发，既适用于计算时间要求苛刻的业务场景，也适用计算时间要求相对宽松但追求高质量解的业务场景。支持二次开发，只需要实现给定的接口就可以轻松处理新的约束和目标函数。1.拓展属性配送模式车辆数目1.2.3.4.容量约束工作时长约束时间窗约束 三维装箱约束1.2.3.4.固定成本行驶距离多车型Multi-Trip 多仓库 多时间窗Time-Dependent Travel Time顾客分区1.2.3.4.5.2.6.401. 常规配送模式2.

42、 取货送货模式3. 需求可拆分模式系统介绍41基于Eclipse Che编程平台系统介绍42可以在平台上调用API，多人协同开发系统介绍43少量代码就可以完成一个路径优化算法开发系统性能GVRPBest KnownMAPSO 1HGSADC 2YO3AGEA4LZ5GH026HG057BHD8LC9PDR10PR11LCK1234173417342234203417342834293446345934653451343234383442算例：56 Gehring & Homberger benchmark instances with 1000customers1 Y. Marinak

43、is, M. Marinaki, A Migdalas. A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows. Inf. Sci. 481(2019): 311-3292 T. Vidal , T.G. Crainic , M. Gendreau , C. Prins ,A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle rout

44、ing problems with time-windows, Comput. Oper. Res. 40 (2013) 475489 .3 Y. Nagata, O. Braysy. A powerful route minimization heuristic for the vehicle routing problem with time windows.Oper. Res. Lett. 37(2009): 333-3384 P.P. Repoussis , C.D. Tarantilis , G. Ioannou , Arc-guided evolutionary algorithm

45、 for the vehicle routing problem with time windows, IEEE Trans. Evol. Comput. 13 (3) (2009) 624647 .5 A. Lim , X. Zhang , A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows, INFORMS J. Comput. 19 (2007) 443457 .6 H. Gehring , J

46、. Homberger , Parallelization of a two-phase metaheuristic for routing problems with time windows, J. Heuristics 8 (2002) 251276 .7 J. Homberger , H. Gehring , A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, Eur. J. Oper. Res. 162 (2005) 220238 .8 O. Braysy , G. H

47、asle , W. Dullaert ,A multi-start local search algorithm for the vehicle routing problem with time windows, Eur. J. Oper. Res. 159 (2004) 586605 .9 A.L. Bouthillier , T.G. Crainic , Co-operative parallel metaheuristic for vehicle routing with time windows, Comput. Oper. Res. 32 (2005) 16851708 .10 E

48、. Prescott-Gagnon , G. Desaulniers , L.M. Rousseau , A branch and price based large neighborhood search algorithm for the vehicle routing problem with time windows, Networks 54 (2009) 190204 .11 A.L. Bouthillier , T.G. Crainic , P. Kropf , A guided cooperative search for the vehicle routing problem

49、with time windows, IEEE Trans. Intell. Syst. 20 (2005) 3642 .12 A.L. Bouthillier , T.G. Crainic , P. Kropf , A guided cooperative search for the vehicle routing problem with time windows, IEEE Trans. Intell. Syst. 20 (2005) 3642 .计算环境：Intel Xeon CPU E5-1607 v3 3.10GHz, 128 GB RAM计算时间：1小时44VRPTW系统拓展性

50、英文题目：The fuel-consumption-minimizing capacitated vehicle routing problem (FCM-CVRP)𝑖𝑛𝑡 𝑖𝑛𝑠𝑒𝑟𝑡_𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒(𝑖𝑛𝑡 𝑝, 𝑖𝑛

51、9905; 𝑖𝑑) :向路径位置𝑝节点𝑖𝑑的删除路径位置𝑝上的节点的𝑖𝑛𝑡 𝑟𝑒𝑚𝑜𝑣𝑒_𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒(𝑖𝑛𝑡 𝑝):基本问题设置：CVRP𝑖

52、19899;𝑡 𝑒𝑥𝑐𝑎𝑛𝑔𝑒_𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒(𝑖𝑛𝑡 𝑝1, 𝐵𝑎𝑠𝑒 𝑟, 𝑖𝑛𝑡 𝑝2):当前路径位置𝑝1上的节

53、点和路径𝑟位置𝑝2的节点交换的𝑖𝑛𝑡 𝑐𝑟𝑜𝑠𝑠_𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒(𝑖𝑛𝑡 𝑝1, 𝐵𝑎𝑠𝑒 𝑟, 𝑖𝑛𝑡 ү

54、01;2):当前路径位置𝑝1上的边和路径𝑟位置𝑝2的边进行交叉的𝑖𝑛𝑡 𝑟𝑒𝑝𝑙𝑎𝑐𝑒_𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒(𝑖𝑛𝑡 𝑝, 𝑖𝑛𝑡 𝑖

55、19889;) :用节点𝑖𝑑替换路径位置𝑝上的节点的目标函数：每公里行驶成本是一个关于车重和速度的非线性函数；当速度恒定时，简化成一个和车重相关的线性函数。因此，我们假定每公里行驶成本𝑤 = 𝑎𝑤 + 𝑏，其中𝑤是载货量。𝑐𝑑𝑜𝑢𝑏𝑙𝑒 𝑖𝑛𝑠𝑒𝑟𝑡_Ү

56、88;𝑜𝑠𝑡(𝑖𝑛𝑡 𝑝, 𝑖𝑛𝑡 𝑖𝑑) : 计算向路径位置𝑝 本增量节点𝑖𝑑引起的成𝑑𝑜𝑢𝑏𝑙𝑒 𝑟𝑒𝑚𝑜𝑣𝑒_𝑐𝑜𝑠𝑡(𝑖𝑛𝑡 𝑝): 计算