需求随机条件下冷藏集装箱堆场机修工路径优化

马千里　杜木子　李浩　李明骏

摘要：由于在集装箱码头堆场冷藏集装箱插拔电需要由机修工手动完成，为降低未能及时对冷藏集装箱插电而造成箱内货物腐败的风险，对机修工路径进行优化来减少总完工时间。建立考虑机修工的准备时间和惩罚时间的机修工插拔电路径规划模型，选用遗传算法对模型进行求解。通过算例实验证明了模型和算法的有效性。

关键词：  冷藏集装箱; 带有时间窗的旅行商问题; 路径优化; 遗传算法

中图分类号：  U691+.31文献标志码：  A

Mechanic path optimization of reefer container yard

under random demand

Abstract：
As the power supply connection and disconnection operation of reefer containers in the container terminal yard needs to be manually completed by mechanics， in order to reduce the risk of cargo corruption caused by the failure to timely connect reefer containers to power supply， the mechanic path is optimized to reduce the total completion time. A mechanic path planning model for the power supply connection and disconnection operation is established considering the preparation time and the penalty time of mechanics. The model is solved by the genetic algorithm. The effectiveness of the model and the algorithm is proved by numerical examples.

Key words：
reefer container; traveling salesman problem with time window; path optimization; genetic algorithm

引言

伴隨着食品冷链物流的市场规模越来越大，越来越多的冷藏集装箱（简称“冷藏箱”）需要在相对较短的时间内进行转运。冷藏箱在转运过程中需要插电以保持箱内温度，这一过程目前只能通过机修工完成。作为随机事件，冷藏箱的到港和离港时间并不能事先确定，因此为进一步满足冷藏箱的插拔电需求，码头的管理人员需要对现有机修工的工作流程进行优化，加速冷藏箱的流转，降低因不能及时插电而造成的货物腐败风险。

机修工的运动轨迹模型可以看成经典的旅行商问题（traveling salesman problem， TSP），由于冷藏箱区场地过大，需要配置多名机修工，故将此问题视为多旅行商问题（multiple TSP， MTSP）。同时，由于提前拔电或者延后插电都可能造成冷藏箱制冷量不足，导致货物腐败，所以每个冷藏箱的插拔电时间都有一个严格的时间窗。目前，许多国内外学者对TSP和MTSP进行了深入研究，取得了丰富的成果。HOUGARDY等[1]提出利用2opt启发式算法对TSP进行求解;胡立栓等[2]对蚁群算法进行改进以增强算法的全局搜索能力;HU等[3]通过建立共享图神经网络和分布式策略网络来学习一个通用策略以求得近似最优解;胡士娟等[4]提出一种模糊C均值聚类单亲遗传算法来加速求解过程;TOTH等[5]将MTSP看作车辆路径问题（vehicle routing problem， VRP），取消运载能力限制后再进行求解;SOLOMAN等[6]首次在 VRP 的研究中引入时间窗概念;俞武扬等[7]以总成本最低为目标，分别考虑冷链车卸货过程和运输过程，建立了带软时间窗的优化模型，利用蚁群算法仿真求解;邵举平等[8]通过设计软时间窗，将时间窗作为评判顾客满意度的标准，建立了最大化顾客满意度和最小化配送成本的多目标优化模型;何小锋等[9]在考虑时间窗的情况下，提出了量子蚁群算法，提高了算法的全局搜索能力，尽可能地避免算法陷入局部最优;夏文明等[10]基于最少旅行商数，在时间窗等约束条件下建立数学模型，利用改进的模拟退火算法进行求解，该算法增加了记忆因子，记住最小的局部最优点，防止程序跳过全局最优点后无法返回。在研究实际问题上，沈丽等[11]在细致量化货损成本和碳排放成本的基础上，考虑固定成本、燃油成本和时间惩罚成本，建立了总成本最低的生鲜产品配送路径优化模型;何继红等[12]通过分析冷藏箱堆场作业的特殊性，结合上海洋山深水港四期全自动化集装箱码头的工程特点和装卸工艺，提出该码头冷藏箱区布置方案。在研究冷藏箱堆场机修工插拔电路径优化问题上，国外有2个研究方向：HARTMANN[13]偏向于将码头作为整体，设计整体仿真系统进行研究;ZHANG等[14]偏向于对码头进行一定的简单模拟，主要专注于求解MTSP的启发式算法的创新。对应的国内研究起步较晚，张晓龙等[15]以机修工行走路径最短为目标，建立整数规划模型来确定冷藏箱的插拔电作业顺序。

上述文献虽均对冷藏箱插拔电问题进行了较为深入的研究，但考虑的机修工移动因素较为简单、单一，且建立的机修工移动模型较为简化，与现实中机修工的工作方式难以吻合。本文在上述文献的基础上，进一步考虑机修工乘坐场地皮卡时的水平移动速度、攀登梯子时的移动速度、完成每个任务的时长等，充分模拟机修工在堆场内部的移动轨迹。李敏等[16]验证了遗传算法在求解TSP上具有优化过程短、运行速度快的优点，因此本文利用遗传算法对机修工插拔电路径进行优化，并对机修工的水平移动速度和机修工人数的变化对路径优化的影响进行分析。

1问题描述与数学建模

1.1问题描述

机修工插拔电路径优化问题可以看作一个MTSP，每当有插拔电需求产生时，便会对应产生一次任务。每次插电需求与到达堆场的冷藏船（车）有关，每次拔电需求与该冷藏船（车）需要离开堆场有关。在本文研究中，由于集装箱码头现实问题往往十分复杂多变，为使模型更加准确且具有更强的普适性和参考价值，根据集装箱码头的实际运营情况和冷藏箱区工作人员的工作内容和方式，假设：（1）机修工乘坐的场地皮卡的移动始终是匀速的;（2）扶梯位于每排冷藏箱的正下方，以方便计算机修工到达各任务点的时间。

机修工完成一次任务的流程如下：（1）机修工通过通信设备接收有插拔电需求的集装箱的位置信息的任务指令;（2）机修工乘坐场地皮卡到达相应位置，完成插拔电的工作;（3）机修工将完成任务的信息通过通信设备回传给码头管理系统（ terminal operating system， TOS），等待下一任務指令的发布。

机修工在2种情况下将接收到任务：（1）当某位机修工完成了当前的任务，并将完成任务的信息通过通信设备回传给TOS后，则由TOS继续向该机修工发布新任务。（2）有新的任务产生，且至少有一名机修工处于空闲状态，此时会有处于空闲状态的机修工接收到新任务。

由于提前拔电或者延后插电都可能造成冷藏箱制冷量不足，导致货物质量下降，所以每个冷藏箱的插拔电时间都有一个严格的时间窗，即最早开始时刻和最晚开始时刻，不同作业任务的时间窗定义如下：（1）插电作业时间窗。最早开始时刻等于冷藏箱进入堆场的时刻;最晚开始时刻取决于冷藏箱在无外接电源情况下能保持箱内温度的时间。（2）拔电作业时间窗。最早开始时刻取决于拔电需求产生的时刻和冷藏箱在无外接电源情况下能保持箱内温度的时间;最晚开始时刻等于冷藏箱离开堆场的时刻减去机修工进行拔电工作的处理时间。

在实际工作环境中，冷藏箱是按顺序进行提取的，断电时间过长会对货物冷藏效果造成影响从而产生货物损失，因此针对机修工的工作时间设立时间窗，根据顺序对冷藏箱进行操作。以拔电作业为例，在时间窗外开始工作，提前开始会导致冷藏箱断电时间延长增加货损风险、延后开始会导致总工作时间延长，将这2种情况都视作延误。本文针对不同任务下存在的随机延误情况设立惩罚系数，以此来对延误时间进行约束。惩罚系数选取延误时间与准备时间的权重比，考虑其影响程度较大，结合实际经验，取值为10。惩罚系数与延误时间相乘后得到惩罚时间，并与准备时间合并设立目标函数，优化目标为目标函数值最小，这样设计不再单纯考虑准备时间，与提升数量级后的惩罚时间相加，使得结果能够以更好的效果呈现。

1.2符号说明

N为任务集合，N={1，2，…，n}，i∈N;M为机修工集合，M={1，2，…，m}，k∈M;[si，ei]为任务i的插拔电时间窗，其中Ti，s为任务i最早开始时刻，Ti，e为任务i最晚开始时刻;dij，h为机修工乘坐场地皮卡从任务i到任务j的水平移动距离;vh为机修工乘坐场地皮卡时的水平移动速度;hi，v为任务i所在的高度;vv为机修工上下攀爬梯子的速度;tij，s为从任务i处到任务j处的准备时间，tij，s=dij，h/vh+（hi，v+hj，v）/vv;ti，p为任务i的处理时间;Tki为机修工k完成任务i的时刻;tki为机修工k未在规定的时间窗内完成任务i所延误的时间，tki=max{0，Tki-Ti，e}+max{0，Ti，s-Tki};λ为惩罚系数，表示与准备时间比较，延误时间所占的权重;M为无穷大的整数;xkij为01变量，若任务i为任务j的紧前任务，且都由机修工k完成，则xkij=1，否则为0。

1.3数学模型

目标函数为

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

以上公式中，i，j∈N;k∈M。式（1）为目标函数，即优化目标为最小化延误时间与准备时间之和;式（2）限制每个任务只能被某位机修工完成一次;式（3）保证每位机修工从起点出发一次;式（4）用于保证每位机修工按照正确的工作顺序完成工作;式（5）明确两个任务的优先级顺序，如果机修工k的任务i的优先级高于任务j的优先级，则任务j的完成时间要大于等于任务i的完成时间、任务i到任务j的准备时间、任务j的完成时间之和，以保证任务的连续性;式（6）表示每位机修工的延误时间;式（7）和（8）定义变量的取值范围;式（9）确保被安排任务的机修工人数不超过机修工总人数;式（10）确保无子回路。

2遗传算法

在寻优算法中，遗传算法具有如下优势：可以直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法，不需要确定的规则就能自动获取和优化搜索空间，自适应地调整搜索方向。因此，本文根据整体优化法的思路和上述模型，设计遗传算法。具体步骤如下：

步骤1初始值设置。设置各冷藏箱位置信息、冷藏箱之间的距离、机修工人数、机修工移动速度、算法迭代次数。

步骤2设置适应度评估值。

步骤3初始化种群。

步骤4对当前种群进行路径规划，规划出当前种群最优路线，进行绘图。

步骤5进行适应度评估。如果满足适应度评估条件，输出结果。否则，进行步骤6。

步骤6利用遗传算法因子对种群进行选择、交叉、变异操作，得到子代种群，然后返回步骤5。

3算例分析

3.1算例构建

为验证本文所描述的冷藏箱堆场机修工插拔电路径优化模型的有效性，使用上海洋山深水港四期全自动化集装箱码头相应数据进行实验。算例设计如下：

该码头共有6个冷藏箱区，分别位于第14、15、30、31、46、47号箱区，每个箱区靠近陆侧垂直于码头岸线布置。在相邻的2个箱区之间设有场地皮卡通道，机修工只能在通道上驾车通行;如果需要跨箱区作业，只能通过跨箱区通道进入另一箱区。

每个箱区包含有8个大贝和2个小贝，每个贝位可以堆放7排，除第1排只能码放2层冷藏箱外，其余每排可以码放4层冷藏箱。第14和15号冷藏箱区结构示意图见图1。

电源支架有4层，40英尺（1英尺=0.304 8 m）冷藏箱长度为12 m，20英尺冷藏箱长度为6 m，宽度均为3 m，层高均为 2.5 m，且上下电源支架的楼梯位于支架中部，跨箱区通道长为50 m。机修工攀爬楼梯时的移动速度为1 m/s。

各冷藏箱位置可以按照其所在箱区、贝位、排位、层数编码：若需要插拔电的冷藏箱位于第30号箱区的第9贝第1排第4层，则该冷藏箱位置为（30，9，1，4）。用ai、bi、ci、di分别表示冷藏箱i所在箱区、贝位、排位及层数，则从任务点i（ai，bi，ci，di）到任务点j（aj，bj，cj，dj）的准备时间为

3.2算法参数设置

本文使用的测试数据参考上海洋山深水港四期全自动化集装箱码头冷藏箱区的真实数据，根据某一时间点的实时堆存情况构建三维立体坐标系，在冷藏箱区随机产生40个插拔电需求点，再通过参考实际集装箱调度数据对模型进行时间窗和工作时间的相应模拟。

共有40个插拔电任务，设第1个任务为所有机修工的出发点，非任务点。若某一任务的时间窗为（0， 3 600），则表示该任务的最早开始时刻是第 0 s，最晚开始时刻是第3 600 s。由于未能按时插拔电会使得货物有腐烂的风险，造成的影响较大，故设惩罚系数为10。

3.3算例求解分析

设有4名机修工，其水平移动速度为5 m/s。求解出的路径见表1，对应的路径示意图见图2。求解结果显示，4名机修工在水平移动速度为5 m/s时的总完工时间为51 463 s，其中总惩罚时间为45 698 s，总准备时间为5 765 s。总惩罚时间占比较高，其主要原因为惩罚系数为10。由此引发了新的问题：能否通过增加机修工人数来减少总惩罚时间和总完工时间？

3.3.1机修工人数对路径优化的影响

在机修工水平移动速度为5 m/s时，将机修工人数从2人逐渐增加至8人，模型求解结果见表2。表2反映了机修工人数与总完工时间、总惩罚时间和总准备时间的关系。

分2种情况进行讨论：

（1）将机修工人数从4人逐渐增加至8人，分析其结果可以看出：当机修工人数超过5人后，并不能对总完工时间、总惩罚时间起到明显的优化效果，反而会出现小幅度增长现象。8名机修工在水平移动速度为5 m/s时的路径见表3，对应的路径示意图见图3。

（2）将机修工人数从4人减至2人，分析其结果可以看出：减少机修工人数并不能实现更好的优化，反而会增加总惩罚时间和总完工时间。2名机修工在水平移動速度为5 m/s时的路径见表4，对应的路径示意图见图4。

由图5和6可以看出：随着机修工人数的增加，总完工时间和总惩罚时间均呈现先降后升的趋势。

3.3.2机修工水平移动速度对路径优化的影响

在机修工人数为4人时，将机修工水平移动速度从2 m/s逐渐增加至8 m/s，模型求解结果见表5。

分2种情况进行讨论：

（1）当机修工水平移动速度从5 m/s逐渐增加至8 m/s时，分析其结果可以看出，每次的速度增加都会对总完工时间和总惩罚时间产生优化。然而，速度的增加是有上限的，可以考虑在一定合理范围内提高速度。4名机修工在水平移动速度为8 m/s时的路径见表6，对应的路径示意图见图7。

（2）当机修工水平移动速度从5 m/s逐渐降低至2 m/s时，分析其结果可以看出，随着机修工水平移动速度的降低，总惩罚时间大幅度增加，总准备时间小幅度增加，从而造成总完工时间大幅度增加。4名机修工在水平移动速度为2 m/s时的路径见表7，对应的路径示意图见图8。

从图9和10可以得出：逐渐增加机修工水平移动速度，总完工时间和总惩罚时间均呈现逐步下降的趋势，且下降速度逐渐减缓。

4结论

本文建立考虑需求随机的冷藏集装箱（简称“冷藏箱”）堆场机修工插拔电路径优化模型，计算包含机修工的准备时间和惩罚时间的总完工时间。采用上海洋山深水港四期全自动化集装箱码头的真实数据进行算例分析，并对机修工人数和其水平移动速度进行敏感性分析，较为完整地研究了机修工人数及其水平移动速度的变化对机修工路径优化的影响。在实际工作中，导致冷藏箱货损的因素不仅仅涉及冷藏箱插拔电环节，还涉及运输途中的各类状况，因此在堆场环节能做到的就是稳定工作时间，使插拔电时间与后续集装箱处理环节相匹配，将间隔时间做到最小化。本文考虑的数学模型规模较小，且在研究过程中只研究了在某个时刻的路径规划，而在实际的机修工工作过程中，任务是随时间不断变化的，甚至在某些时刻将会把某些任务设置为更高的优先级去进行处理，这些将作为下一步研究的方向。

参考文献：

[1]HOUGARDY S， ZAISER F， ZHONG X H. The approximation ratio of the 2opt heuristic for the metric traveling salesman problem[J]. Operations Research Letters， 2020， 48（4）：
401404. DOI：
10.1016/j.orl.2020.05.007.

[2]胡立栓， 王育平， 亓呈明. 基于改进蚁群算法的物流配送车辆路径优化[J]. 智能建筑， 2017（6）：
6062， 80..

[3]HU Y J， YAO Y， LEE W S. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs[J]. KnowledgeBased Systems， 2020， 204：
106244. DOI：
10.1016/j.knosys.2020.106244.

[4]胡士娟， 鲁海燕， 向蕾， 等. 求解MMTSP的模糊聚类单亲遗传算法[J]. 计算机科学， 2020， 47（6）：
219224. DOI：
10.11896/jsjkx.190500137.

[5]TOTH P， VIGO D. The vehicle routing problem[M]. Philadelphia：
Society for Industrial and Applied Mathematics， 2002：
225242.

[6]SOLOMAN M M， DESROSIERS J. Time window constraint routing and scheduling problems[J]. Transportation Science， 1988， 22（1）：
113.

[7]俞武扬， 杨沈记. 带软时间窗的冷链物流配送路径优化研究[J]. 生产力研究， 2017（6）：
6770， 116. DOI：
10.19374/j.cnki.141145/f.2017.06.015.

[8]邵举平， 曹倩， 沈敏燕， 等. 生鲜农产品配送中带时窗的VRP模型与算法[J]. 工业工程与管理， 2015， 20（1）：
122127， 134. DOI：
10.19495/j.cnki.10075429.2015.01.019.

[9]何小锋， 马良. 带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践， 2013， 33（5）：
12551261.

[10]夏文明， 李国富. 有路径均衡和时间窗约束的MTSP问题研究[J]. 内蒙古科技与经济， 2011（8）：
7980.

[11]沈丽， 李成玉， 甘彦， 等. 考慮货损和碳排放的生鲜产品配送路径优化[J]. 上海海事大学学报， 2021， 42（1）：
4449. DOI：
10.13340/j.jsmu.2021.01.008.

[12]何继红， 姜桥， 张晓龙. 自动化集装箱码头冷藏箱箱区布置[J]. 水运工程， 2016（9）：
5255. DOI：
10.16233/j.cnki.issn10024972.2016.09.011.

[13]HARTMANN S. Scheduling reefer mechanics at container terminals[J]. Transportation Research Part E， 2013， 51：
1727. DOI：
10.1016/j.tre.2012.12.007.

[14]ZHANG J T， SONG Y J. Mathematical model and algorithm for the reefer mechanic scheduling problem at seaports[J]. Discrete Dynamics in Nature and Society， 2017（3）：
113. DOI：
10.1155/2017/4730253.

[15]张晓龙， 浦新平， 林洋. 自动化集装箱码头冷藏箱区插拔电路径优化[J]. 港口装卸， 2019（1）：
1013， 49.

[16]李敏， 吴浪， 张开碧. 求解旅行商问题的几种算法的比较研究[J]. 重庆邮电大学学报（自然科学版）， 2008， 20（5）：
624626， 630.

（编辑赵勉）

收稿日期：
20210713修回日期：
20211227

基金项目：
辽宁省社会科学规划基金（L21CGL006）

作者简介：
马千里（1989—），河南襄城人，博士，研究方向为交通运输系统优化、冷链物流、港口规划，（Email）qianlima@dlmu.edu.cn

*通信联系人。（Email）dumuzi@pdiwt.com.cn

猜你喜欢 路径优化遗传算法 面向成本的装配线平衡改进遗传算法河南科技(2022年8期)2022-05-31基于遗传算法对广义神经网络的优化智富时代(2018年7期)2018-09-03基于遗传算法对广义神经网络的优化智富时代(2018年7期)2018-09-03基于遗传算法的临床路径模式提取的应用研究智富时代(2018年4期)2018-07-10基于遗传算法的临床路径模式提取的应用研究智富时代(2018年4期)2018-07-10遗传算法在校园听力考试广播系统施工优化中的应用大陆桥视野·下(2017年12期)2017-11-29物流配送车辆路径的免疫遗传算法探讨科学家(2016年13期)2017-09-29基于GEM模型的现代化物流产业集群竞争力评价和路径优化商业经济研究(2016年24期)2017-01-10信息时代数控铣削的刀具路径优化技术无线互联科技(2016年13期)2017-01-10经济发展方式转变背景下流通体系路径优化策略探讨商业经济研究(2016年22期)2016-12-27