考虑废物包装时间的车辆回收路径规划方法

2021-11-13邢立宁

包装学报 2021年5期

关键词：模因搜索算法爬山

邢立宁吴健

国防科技大学

系统工程学院

湖南长沙 410000

0 引言

随着人们环保意识的增强和一系列新的环境保护法律法规的出台，绿色物流成为现代物流可持续发展的必然之路。合理规划车辆路径是实现绿色物流的关键环节[1-3]。

车辆路径规划问题（vehicle routing problem，VRP）是指：合理调度一定数量的车辆通过一系列的收货点和发货点，在满足相应约束条件（车辆容量、时间窗口等）下，达到运输总费用最低、路程最短等目标[4-5]。在此基础上，多个学者延伸出多个问题的变种，主要包括：带时间窗的车辆路径规划问题（vehicle routing problem with time window，VRPTW），加入服务客户的时窗约束，即服务客户的时间在一定范围内；与车型相关的车辆路径规划问题（mixed fleet vehicle routing problem，MFVRP ），考虑负责运输的车辆属性（容量、速度）不同；带多车场的车辆路径规划问题（multi-depot vehicle routing problem，MDVRP），是指有多个车场同时为多个客户提供服务，在满足客户需求的前提下，使总运输成本最小；随机车辆路径规划问题（stochastic vehicle routing problem，SVRP），涉及运输中遇到的不确定信息，比如订单到达随机、服务时间不确定等。这些问题多数从收发货点数量、车辆数量、收发货方式、用户需求等角度研究车辆路径规划问题，较少从物品本身性质来规划车辆路径。根据《中华人民共和国固体废物污染环境防治法》第八十三条之规定“运输危险废物，应当采取防止污染环境的措施，并遵守国家有关危险货物运输管理的规定”，液体、半固体等危险废物需进行适当的包装并贴有危险废物标签后，才能进行收集、贮存、运输。因此研究废物运输路径规划问题时，可将包装时间考虑进来。

基本的车辆路径规划问题已经被证明是NP-Hard问题，即不存在多项式时间内求得最优解的算法。因此更复杂的车辆路径规划问题同样不存在多项式时间内可求得精确解的算法[6]。国内外学者求解车辆路径规划问题的方法大致分为精确算法、启发式算法以及元启发式算法3类。精确算法是以分支定界、动态规划为典型的算法[7-8]。此类算法能从理论上求得最优解，但局限性在于只适用于小规模场景，扩展性不足，并且简化了问题约束，无法满足实际工程需要。启发式算法有距离越近越优先、冲突消解和任务分配等算法，此类算法能够在短时间内生成可行的路径方案，但求解策略较为简单，解质量较低，无法提升资源的使用效率[9]。元启发式算法是以遗传算法、蚁群算法、粒子群算法为典型的算法[10-11]，此类算法是通过模拟自然界生物种群演化机理和群体行为，对问题进行迭代寻优，能在一定时间内生成较优解，因而在车辆路径规划问题中应用较为广泛。基于此，本文研究废物回收的车辆路径规划问题时，考虑废物包装时间，并构建问题数学模型，设计两种算法即禁忌搜索算法和模因算法进行求解。

1 问题描述与数学模型

考虑废物包装时间的车辆路径规划问题描述如下：1个回收中心点和N个回收站点，回收中心点拟派K辆车回收废物，所有车辆均从回收中心点出发，最后到达回收中心点。该问题可用G=(V,E)的有向连通图表示（见图1），V表示回收中心点和回收站点的集合，E表示图中所有边的集合。图1中有3条车辆行驶路径，分别为0→2→7→0，0→6→1→0，0→5→4→3→0。

图1 车辆路径规划示意图Fig. 1 Vehicle route diagram

本车辆路径规划问题的数学模型如下：

1）目标函数即车辆行驶总路程最短为

式中：cij为站点i与j之间的距离；xijk为模型的决策变量，取值为0或1，xijk=1表示第k辆车服务完站点i之后立马服务站点j，否则为0。为了简化计算，假设车辆行驶速度为1，则车辆从站点i到站点j的时间tij与距离cij相等。

2）每个回收站点只被服务一次，

3）车辆均从回收中心点出发，最后到达回收中心点，即

4）时间约束为

式中：si为废物包装的时间；wik、wjk分别为第k车辆在第i个和第j个站点的开始包装时间；aj、bj分别为站点j接受废物回收的最早、最晚时间。当车辆到达站点j的时间小于aj，则必须等待；当车辆到达站点j的时间超过bj，则需放弃该站点。

5）车辆容量约束为

式中：di为站点i的废物容量；Ck为第k辆车容量。

2 算法设计

2.1 禁忌搜索算法

禁忌搜索（tabu search，TS）算法是由Glover于1986年提出的一种带有记忆策略的局部搜索算法。禁忌算法以传统爬山算法为基础开展搜索优化，并通过禁忌表记录优化过程中的局部最优解或产生局部最优解的操作，以避免对局部最优空间的重复搜索，达到跳出局部最优、开辟优质解空间的效果。

1）禁忌长度

在禁忌搜索算法中，禁忌长度即禁忌解集的大小是影响算法性能的主要因素。为增强算法在不同问题规模的适应能力，设禁忌长度为任务集T规模的某一比例。禁忌对象直接为解，即回收路径总长度。

式中αT为比例系数，取值为0.1～0.3。

2）编码方式

编码采取实数编码方式。每辆车的行驶路径单独编码，该编码方式更加简洁直观。两辆车的行驶路径编码如图2所示，车辆1的行驶路径为0→1→2→3→5→0，车辆2的行驶路径为0→4→6→0。

图2 解的编码Fig. 2 The coding of the solution

3）插入算子

采用插入算子产生新解，如图3所示。图中，选择路径1中回收站点3插入到路径2中回收站点6的后面，以产生新解。插入算子完全遍历当前解得到的解集即为邻域。选取邻域最好解或者非禁忌最好解作为下一迭代的当前解。

图3 插入算子Fig. 3 Insertion operator

禁忌搜索算法流程如图4所示。

图4 禁忌搜索算法流程图Fig. 4 The flow chart of tabu search algorithm

2.2 模因算法

采用遗传算法与局部搜索算法相结合的模因算法解决废物回收车辆路径规划问题。遗传算法能够保证解的多样性，但不能保证求得一个较优解，而局部搜索算法即爬山算法可在遗传算法的基础上，对解进行邻域搜索，实现解的多样性与集中性。算法流程如图5所示。

图5 模因算法流程图Fig. 5 The flow chart of memetic algorithm

2.2.1 遗传算法

1）编码方式

个体编码采取实数编码方式。为了方便遗传算法的交叉变异操作，采取与图3不同的的编码方式，将所有车辆的行驶路径进行统一编码，当作一个个体，如图6所示。图中，节点2, 3为一条路径，节点4为一条路径，节点5, 1, 6为一条路径，其中0表示路径的起点和终点。

图6 解的编码Fig. 6 The coding of the solution

2）选择策略

选择策略采用轮盘赌策略。假设共有N个个体，第i个个体的适应度为fits(i)，第i个个体被选择的概率为

由式（9）可知，适应度越高的个体被选中进入下一代的概率越大。

3）交叉策略

交叉策略采取部分交叉映射（partially mapped crossover，PMX）。种群中的个体随机进行两两配对，配对成功的两个个体作为父代1和父代2进行交叉操作。首先选两个交叉点，交换中间部分，确定映射关系，最后将未换部分按映射关系恢复合法性，具体操作如图7所示。

图7 交叉策略Fig. 7 Crossover strategy

完成交叉策略后，随机选择几个位置，将表示起点和终点的0随机插入，以完成了两个完整解的交叉操作。本实验中，交叉率设置为95%。

4）变异策略

变异策略采用两点互换。随机生成两个基因位，并交换两个基因位上的基因，如图8所示。本实验中，变异率设置为10%。

图8 变异策略Fig. 8 Mutation strategy

2.2.2 爬山算法

爬山算法是从当前的节点开始，和周围邻居节点的值进行比较，然后不断向有提升的方向前进。本文采取首次改进（ first-improvement）策略的爬山算法。首次改进策略是接受搜索过程中出现的第一个改进解。如当前解为[0, 2, 3, 0, 4, 0, 5, 1, 6, 0]，由于开始位置与结束位置都必须为0，因此从第二个节点开始尝试两两节点依次进行交换，即(2, 3), (2, 0),…, (2, 6),(3, 0), …, (1, 6)，交换后计算解的提升情况，如果有提升，则接受此解。如2和6交换可得到有提升的解，则当前解变成[0, 6, 3, 0, 4, 0, 5, 1, 2, 0]。此时下一轮搜索序列变更为(6, 3), (6, 0),…, (6, 1), (3, 0), …, (1,2)，重新开始搜索并接受第一个改进解。爬山算法的终止条件设置为当某次提升后在所有邻域中都找不到改进解。

3 案例分析

某制造企业为提高资源利用率，给社会环境和企业带来可观的经济效益，需对某产品的废物进行回收。根据前期市场售卖产品情况，100个站点有产品废物，为此该企业建立了1个回收中心点。各站点的地理位置、废物质量以及所需包装时间见附表1，其中节点0为回收中心点，剩余100个节点为回收站点。

附表1 回收点的基本数据Table 1 Basic data of recycling site

3.1 禁忌搜索算法结果

禁忌搜索算法参数设置如下：总迭代次数为2000，禁忌长度分别为10, 20, 40。禁忌搜索算法运行10次，最好解如下：

回收路径1: 0→45→83→99→94→96→0；

回收路径2: 0→27→31→88→7→0；

回收路径3: 0→40→53→26→0；

回收路径4: 0→62→11→90→10→0；

回收路径5: 0→2→21→73→41→56→4→0；

回收路径6: 0 →14→44→38→43→58→0；

回收路径7: 0→36→47→19→8→46→17→0；

回收路径8: 0→12→76→78→34→35→77→0；

回收路径9: 0→65→71→9→66→1→0；

回收路径10: 0→63→64→59→48→0；

回收路径11: 0→28→29→79→50→68→0；

回收路径12: 0→39→23→67→55→25→0；

回收路径13: 0→33→81→3→54→24→80→0；

回收路径14: 0→69→30→51→20→32→70→0；

回收路径15: 0→95→98→61→86→91→100→0；

回收路径16: 0→82→18→84→60→89→0；

回收路径17: 0→72→75→22→74→0；

回收路径18: 0→52→6→0；

回收路径19: 0→92→42→15→87→57→97→0；

回收路径20: 0→59→5→16→85→37→93→0。

3.2 模因算法结果

模因算法、遗传算法、爬山算法的迭代次数设置为100代，模因算法、遗传算法的种群规模设置为100，交叉率为95%，变异率为10%。通过先验实验，发现在100次迭代过程中加入爬山算法与在最后迭代的10代中加入爬山算法的结果相差不大，但在最后迭代的10代中加入爬山算法时，算法时间有了巨大的提升。因此，本文选择在最后迭代的10代中加入爬山算法。模因算法运行10次，其中一个解的表达方式如下：

0→96→13→92→76→80→54→0→21→81→78→33→24→55→93→0→28→4→20→66→65→9→68→75→72→37→16→84→85→2→26→8→49→70→6→59→7→18→77→58→97→60→32→35→12→71→79→34→29→30→63→62→43→57→23→74→0→52→22→73→67→39→46→86→38→98→61→95→88→11→64→90→17→47→19→69→87→56→40→89→83→27→45→36→3→0→100→44→42→5→1→51→50→91→15→94→99→14→82→31→25→41→10→48→53→0。

该解可解码为：

回收路径1：0→96→13→92→76→80→54→0；

回收路径2：0→21→81→78→33→24→55→93→0；

回收路径3：0→28→4→20→66→65→9→68→75→72→37→16→84→85→2→26→8→49→70→6→59→7→18→77→58→97→60→32→35→12→71→79→34→29→30→63→62→43→57→23→74→ 0；

回收路径4：0→52→22→73→67→39→46→86→38→98→61→95→88→11→64→90→17→47→19→69→87→56→40→89→83→27→45→36→3→0；

回收路径5：0→100→44→42→5→1→51→50→91→15→94→99→14→82→31→25→41→10→48→53→0。

爬山算法、遗传算法和模因算法的算法运行时间和距离如表1所示，距离对比如图9所示。由表1和图9可知，在算法运行时间方面，模因算法相较于另外两种算法表现较差，但在求解效果上，每种算法的表现均较稳定，在解的质量方面，模因算法所求解远远好于遗传算法和爬山算法，普遍提升了30%以上。