论文部分内容阅读
由于冷藏箱对温度控制有特殊要求，集装箱码头装卸冷藏箱时需要安排工作人员进入箱区实施插拔电辅助操作。就自动化集装箱码头而言，为了确保冷藏箱区正常作业，工作人员必须在规定时间内完成插拔电操作。本文以上海港洋山深水港区四期自动化集装箱码头（以下简称“洋山四期码头”）为例，在考虑冷藏箱作业时间窗约束的条件下，结合旅行销售员问题（travelling salesman problem，TSP）的特点，以工作人员行走路径最短为目标，建立自动化集装箱码头冷藏箱区插拔电路径规划模型，并通过算例分析验证模型的有效性。
1 研究背景
目前国内学者对时间窗和路径规划问题已有较多研究，例如：杨燕霞等[1]针对带时间窗的非满载车辆调度问题建立数学模型，并设计启发式算法，得到最优结果；潘振贞[2]针对T公司物流配送存在的问题，以行驶路径最短、运输成本最低、配送车辆最少和客户满意度最高为目标，以车辆装载能力、时间窗、车辆行驶距离等为约束条件，在考虑T公司物流配送特殊性的基础上，建立带时间窗的车辆路径问题多目标规划模型，并运用简单的遗传算法求解和分析实例；罗耀波[3]运用非线性混合整数规划理论，在考虑仓库容量限制和路径容量约束的条件下，针对客户同时存在送货和取货需求以及客户可配送时间范围模糊的情况，建立基于模糊时间窗的同时送取货的多仓库、多车型选址路径模型；何继红等[4]分析冷藏箱堆场作业的特殊性，并结合洋山四期码头的工程特点和装卸工艺，提出该码头冷藏箱区布置方案。本文在上述研究成果的基础上，研究自动化集装箱码头冷藏箱区插拔电路径规划问题，以期进一步提高自动化集装箱码头作业效率。
2 问题描述
洋山四期码头共有6个冷藏箱区。为了方便研究，对冷藏箱区作如下假设：（1）每个冷藏箱区纵向可堆放8个大箱和2个小箱，横向可堆放7个集装箱；（2）集装箱的宽度和高度均为2.5 m，长度为12 m，集装箱间距忽略不计；（3）插拔电支架有4层，宽度为3 m，层高为2.5 m，与集装箱间距为3 m，且上下支架的楼梯位于支架中部。
本文主要考虑相邻冷藏箱区的插拔电任务，并要求工作人员在规定时间内完成插拔电操作。假设共有n项插拔电任务，任务点i与任务点j之间的距离为dij且路径唯一，工作人员必须从起点出发，每个任务点只去1次，直至完成所有任务。要求合理安排任务顺序，使工作人员在规定时间内完成任务，并使其行走路径最短。
3 模型构建
3.1 符号说明
3.2 自动化集装箱码头冷藏箱区插拔电路径规划模型
式（2）和式（3）表示每个箱位均被且只能被经过1次；式（4）表示流守恒，即工作人员到达任务点后必须离开；式（5）表示工作人员到达指定任务点的时间范围；式（6）表示工作人员完成操作后离开任务点的时刻；式（7）表示上一项任务至下一项任务的时间约束；式（8）表示决策变量，取0或1。
4 算例分析
4.1 数据输入
假设共有10项任务，每个任务点的具体位置及每项任务的最早开始时刻和最晚开始时刻见表1。工作人员的行走路径唯一，行走速度为1 m/s，插拔电操作时间为20 s，起点在1号箱区入口处。若工作人员早于任务最早开始时刻到达任务点，则须等待至任务最早开始时刻；若工作人员晚于任务最晚开始时刻到达任务点，则赋予其100万m的惩罚距离。
4.2 模型求解
4.2.1 按距离起点由近到远排序
工作人员优先完成距离起点最近的任务，则任务排序及每项任务的实际开始时刻见表2。经计算，工作人员行走总距离为3 001 380 m，并且第8项任务的实际开始时刻晚于最晚开始时刻，导致任务无法按时完成。由此可见，按距离起点由近到远排序无法得到最优结果。
4.2.2 按开始时刻由先到后排序
工作人员优先完成开始时刻最早的任务，则任务排序及每项任务的实际开始时刻见表3。经计算，工作人员行走总距离为5 002 649 m，并且第4项任务的实际开始时刻晚于最晚开始时刻，导致任务无法按时完成。由此可见，按开始时刻由先到后排序无法得到最优结果。
4.2.3 模型优化计算
通过模型优化计算，得到任务最优排序及每项任务的实际开始时刻（见表4）。经计算，工作人员行走总距离为1 399 m，并且每项任务均满足时间约束。
5 结束语
本文以自动化集装箱码头冷藏箱区插拔电路径规划问题为研究对象，在考虑冷藏箱作业时间窗约束的条件下，以工作人员行走距离最短为目标设计模型并求解，从而得到自动化集装箱码头冷藏箱区插拔电路徑规划最优方案。需要注意的是，虽然模型计算结果较为理想，但存在任务量太少、未考虑任务随机性等问题，有待后期继续研究。
参考文献：
[1] 杨燕霞，伍岳庆，姚宇，等. 带时间窗车辆调度问题的启发式算法研究与应用[J]. 计算机应用，2013，33（S1）：59-61.
[2] 潘振贞. 基于时间窗的T公司配送路径优化研究[D]. 上海：华东理工大学，2017.
[3] 罗耀波. 基于模糊时间窗的同时送取货选址路径规划模型研究[D]. 广州：华南理工大学，2014.
[4] 何继红，姜桥，张晓龙. 自动化集装箱码头冷藏箱箱区布置[J]. 水运工程，2016（9）：52-55.
（编辑：张敏 收稿日期：2018-05-15）
1 研究背景
目前国内学者对时间窗和路径规划问题已有较多研究，例如：杨燕霞等[1]针对带时间窗的非满载车辆调度问题建立数学模型，并设计启发式算法，得到最优结果；潘振贞[2]针对T公司物流配送存在的问题，以行驶路径最短、运输成本最低、配送车辆最少和客户满意度最高为目标，以车辆装载能力、时间窗、车辆行驶距离等为约束条件，在考虑T公司物流配送特殊性的基础上，建立带时间窗的车辆路径问题多目标规划模型，并运用简单的遗传算法求解和分析实例；罗耀波[3]运用非线性混合整数规划理论，在考虑仓库容量限制和路径容量约束的条件下，针对客户同时存在送货和取货需求以及客户可配送时间范围模糊的情况，建立基于模糊时间窗的同时送取货的多仓库、多车型选址路径模型；何继红等[4]分析冷藏箱堆场作业的特殊性，并结合洋山四期码头的工程特点和装卸工艺，提出该码头冷藏箱区布置方案。本文在上述研究成果的基础上，研究自动化集装箱码头冷藏箱区插拔电路径规划问题，以期进一步提高自动化集装箱码头作业效率。
2 问题描述
洋山四期码头共有6个冷藏箱区。为了方便研究，对冷藏箱区作如下假设：（1）每个冷藏箱区纵向可堆放8个大箱和2个小箱，横向可堆放7个集装箱；（2）集装箱的宽度和高度均为2.5 m，长度为12 m，集装箱间距忽略不计；（3）插拔电支架有4层，宽度为3 m，层高为2.5 m，与集装箱间距为3 m，且上下支架的楼梯位于支架中部。
本文主要考虑相邻冷藏箱区的插拔电任务，并要求工作人员在规定时间内完成插拔电操作。假设共有n项插拔电任务，任务点i与任务点j之间的距离为dij且路径唯一，工作人员必须从起点出发，每个任务点只去1次，直至完成所有任务。要求合理安排任务顺序，使工作人员在规定时间内完成任务，并使其行走路径最短。
3 模型构建
3.1 符号说明
3.2 自动化集装箱码头冷藏箱区插拔电路径规划模型
式（2）和式（3）表示每个箱位均被且只能被经过1次；式（4）表示流守恒，即工作人员到达任务点后必须离开；式（5）表示工作人员到达指定任务点的时间范围；式（6）表示工作人员完成操作后离开任务点的时刻；式（7）表示上一项任务至下一项任务的时间约束；式（8）表示决策变量，取0或1。
4 算例分析
4.1 数据输入
假设共有10项任务，每个任务点的具体位置及每项任务的最早开始时刻和最晚开始时刻见表1。工作人员的行走路径唯一，行走速度为1 m/s，插拔电操作时间为20 s，起点在1号箱区入口处。若工作人员早于任务最早开始时刻到达任务点，则须等待至任务最早开始时刻；若工作人员晚于任务最晚开始时刻到达任务点，则赋予其100万m的惩罚距离。
4.2 模型求解
4.2.1 按距离起点由近到远排序
工作人员优先完成距离起点最近的任务，则任务排序及每项任务的实际开始时刻见表2。经计算，工作人员行走总距离为3 001 380 m，并且第8项任务的实际开始时刻晚于最晚开始时刻，导致任务无法按时完成。由此可见，按距离起点由近到远排序无法得到最优结果。
4.2.2 按开始时刻由先到后排序
工作人员优先完成开始时刻最早的任务，则任务排序及每项任务的实际开始时刻见表3。经计算，工作人员行走总距离为5 002 649 m，并且第4项任务的实际开始时刻晚于最晚开始时刻，导致任务无法按时完成。由此可见，按开始时刻由先到后排序无法得到最优结果。
4.2.3 模型优化计算
通过模型优化计算，得到任务最优排序及每项任务的实际开始时刻（见表4）。经计算，工作人员行走总距离为1 399 m，并且每项任务均满足时间约束。
5 结束语
本文以自动化集装箱码头冷藏箱区插拔电路径规划问题为研究对象，在考虑冷藏箱作业时间窗约束的条件下，以工作人员行走距离最短为目标设计模型并求解，从而得到自动化集装箱码头冷藏箱区插拔电路徑规划最优方案。需要注意的是，虽然模型计算结果较为理想，但存在任务量太少、未考虑任务随机性等问题，有待后期继续研究。
参考文献：
[1] 杨燕霞，伍岳庆，姚宇，等. 带时间窗车辆调度问题的启发式算法研究与应用[J]. 计算机应用，2013，33（S1）：59-61.
[2] 潘振贞. 基于时间窗的T公司配送路径优化研究[D]. 上海：华东理工大学，2017.
[3] 罗耀波. 基于模糊时间窗的同时送取货选址路径规划模型研究[D]. 广州：华南理工大学，2014.
[4] 何继红，姜桥，张晓龙. 自动化集装箱码头冷藏箱箱区布置[J]. 水运工程，2016（9）：52-55.
（编辑：张敏 收稿日期：2018-05-15）