论文部分内容阅读
近年来，随着港口货运量的增长及船舶大型化的发展，集装箱码头为降低成本和增强竞争力，不断研究新技术，加强系统管理。其中，集装箱卡车（以下简称集卡）的路径安排对码头生产效率有着很大的影响，已成为国内外研究的热点之一。
STEENKEN等[1]运用启发式算法研究集装箱码头的集卡运输路径安排问题；BYUN等[2]提出最短路径算法，寻找集卡行驶时间最短的路径；杨静蕾[3]以集卡行驶里程最短为目标，建立集卡路径优化模型，求解集卡最优行驶路径；张维英等[4]以集卡将码头堆场的集装箱送到岸边桥式起重机（以下简称岸桥）所运行的最短距离为目标，建立配载模型，并应用Hopfield神经网络模型进行计算机模拟。
目前大部分港口的集卡运输采用传统作业工艺，司机操作较简单，不易出错，便于管理和考核；但是，随着科学技术的进步和港口物流业的发展，该模式的弊端逐渐暴露。首先，单条作业路上的集卡配置量为固定值，配置不足可能导致岸桥等待集卡，在码头前方作业区形成瓶颈；配置过剩又会浪费资源，影响港口生产效率。其次，在传统作业工艺中，集卡为指定的岸桥服务，移动仅限于单条作业路，即集卡在完成装船、卸船、转堆等作业后，必须空驶回到堆场或者码头，然后进行下一次作业，造成集卡空载率较高、利用率低下。最后，集卡分配给岸桥后沿固定路径行驶，当集卡数量过多时可能发生交通堵塞，给码头的生产效率带来很大影响。
本文打破传统作业工艺的束缚，主要从环保节能和经济性的角度出发，在利用现有集卡运输且满足特定工作任务总量的前提下，为使运输成本最小，建立整数规划的数学模型，运用LINGO软件，求得各箱区配备的龙门吊数量和集卡总量，以及从每个箱区至卸箱点单个班次内分配运箱量的最优调运方案。
1问题描述
集装箱码头堆场中分为若干个箱区，每个箱区的集装箱预先根据船舶航次（分别有2艘船舶同时进行装卸作业）分成A类和B类。每个箱区A类箱和B类箱的数量已知，并且最多只能安排1台龙门吊，龙门吊的平均装车时间为5 min。
集卡的卸箱点共4个，1号和2号桥吊为A船舶进行装卸作业，3号和4号桥吊为B船舶进行装卸作业，每个卸箱点都有各自总的作业量要求。从长远来看，卸箱点可以移动，但单个班次（8 h）内卸箱点不变，集卡的平均卸车时间为3 min。
集卡每次只能载运1个集装箱，平均时速28 km/h。集卡在等待时的能耗也是相当大的，因此原则上不允许发生集卡等待的情况。龙门吊装车点和桥吊卸箱点都不能同时为2辆及以上的集卡服务。集卡每次都满载运输。
龙门吊装车点到桥吊卸箱点的道路是专用的双向六车道（宽60 m），不会出现堵车现象。每段道路的里程是已知的。
本文所研究的集装箱堆场有箱区6个，卸箱点4个，龙门吊5台，集卡15辆。各卸箱点单个班次的装船量要求为1号桥吊78 TEU，2号桥吊，3号桥吊85 TEU，4号桥吊124 TEU。
各龙门吊装车点和桥吊卸箱点如图1所示。各装车点到卸箱点之间的距离见表1，各箱区拥有的A类箱和B类箱的数量见表2。
2基本假设
（1）忽略各种随机因素引起的龙门吊或集卡的临时停顿，即认为其在单个班次内连续工作；
（2）集卡在途中不发生堵车现象，空载与重载的行驶速度一样；
（3）龙门吊定好工作箱区后，单个班次内不再换箱区；
（4）如果8 h内完成任务，集卡可以提前退出系统；
（5）对所有集卡来说，本文所计算的单个班次是同时开始的；
（6）本算例中的数值仅限于小型且装卸效率较低的集装箱码头堆场。
3问题分析
3.1研究目标
单个班次的生产计划应当包括以下内容：出动几台龙门吊，分别安排在哪些箱区；出动几辆集卡，分别安排在哪些作业路上，单个班次内最多运输多少次（受随机因素影响，装卸时间和运输时间都不精确，因此排时计划无效，只需求出各条作业路上的集卡数量及安排即可）。合格的生产计划应在集卡不等待的条件下满足作业量的要求，而良好的计划还应当考虑以下原则：周转量最小，同时出动的集卡数量最少，运输总成本最低。
基于以上原则建立数学模型，并给出单个班次生产计划的快速算法；再针对实例，给出具体的生产计划和最优调运方案。
3.2约束条件
3.2.1集卡不等待的条件
刚开工时，集卡同时上班，会发生等待装车的现象。在正常运作后，应当限制同一作业路上的集卡数量，使之不发生等待现象。如从装箱点b到卸车点2的距离为0.99 km，集卡来回需要4.243 min，加上装卸车时间，单次运输周期合计12.243 min，那么该作业路上最多安排几辆集卡才不需要等待装车呢？安排2辆没有问题：第一辆开走后要过才回来；在这段时间内花5.000 min装第二辆，还余2.243 min；但来不及装第三辆。由此可见，该作业路上最多安排2辆集卡才能不发生等待，如果安排3辆则必定发生等待装车现象。
集卡从箱区Pi到卸箱点Qj的作业路上运行所需的时间为
式中：cij为从装车点i到卸箱点j的距离（i＝1，2，…，6； j＝1，2，3，4）；v为集卡平均速度。
1台桥吊（卸箱点）不能同时为2辆集卡服务，所以1条作业路上同时运行的集卡数量是有限制的。由于装车时间大于卸车时间，因此从Pi到Qj在集卡不等待的条件下最多能同时运行的集卡数为Aij＝[Tij / 5]，式中符号“[ ]”表示向下取整数。经过计算，各作业路上最多能同时运行的集卡数如表3所示。
3.2.2集卡运输能力限制
每辆集卡在从Pi到Qj作业路上单个班次内最多可运行的次数为
式中：60×8是每个班次的工作时间；（Aij－1）×5是开始装车时最后一辆车的延时时间；Bij是以该作业路上开始装车时最后那辆车来计算的。如果按第一辆车来计算，则
如果取该作业路上的平均延时，则
求得各作业路上每辆集卡的最多运行次数（见表4）。
从Pi到Qj作业路上Aij辆集卡单个班次内合计最多可运行次数为Mij＝Aij×Bij，每次载运1 TEU，则总箱量大约为Mij TEU。
3.2.3龙门吊和桥吊的总能力限制
对于不同作业路上的集卡是否会等待同一台龙门吊来装车的问题，可以通过宏观控制的方式尽量避免。因为单个班次内1台龙门吊最多装96辆集卡，所以控制每台龙门吊单个班次内的装车总数不超过96辆。每个卸箱点单个班次内最多卸车160辆，因此对于装箱点或卸箱点由不同作业路造成的冲突问题，只要平均时间内能完成任务，就认为不冲突，而不对集卡的运行时间作具体安排。考察以上数据可以看到，4号桥吊的卸车量最大，为124辆，小于160辆，则认为单个班次内不发生等待卸车的现象。
3.2.4工作任务约束
4个卸箱点的工作任务约束为dj＝（78，85，124，85）车次。
3.2.5箱区所储箱量约束
第i号箱区A类箱的储箱量为si＝（81，71，87，68，74，87）TEU，第i号箱区B类箱的储箱量为ki＝（61，68，64，68，71，81）TEU，从各箱区运出的A类箱和B类箱的箱量不能超过其所储箱量。
3.2.6龙门吊数量约束
龙门吊只有5台，而箱区有6个，龙门吊上班时一旦确定对应箱区，单个班次内不移动箱区，故只有5个箱区能各安排1台龙门吊，剩余1个箱区轮空。引入决策变量Yi，标志第i号箱区是否安排龙门吊：如果 Yi＝1则安排龙门吊，取 Yi＝0则不安排龙门吊。Yi在模型中与决策变量 xij一起进行优化，其值取决于优化的结果。
3.2.7集卡数量约束
最多能出动的集卡总数为15辆。按照运输计划，从箱区 Pi运到卸箱点 Qj的总箱量为xij，每辆集卡在该作业路上单个班次内最多可运行次数为Bij，故该作业路上应安排集卡辆，各路线合计不超过15辆，即
式中：决策变量xij是非负整数。
4模型的建立与求解
4.1目标函数和约束求解
求解原则如下：（1）周转量最小；（2）出动的集卡最少；（3）运输成本最低。其中，（3）与（1）（2）是因果关系，（1）与（2）是一致的目标。因集卡的安排必须以完成运输方案为前提来设计最优调运计划，故周转量最小是大前提和首要目标。周转量最小可以表示为，由于1是常数，故目标函数可以写成。
根据前文分析，约束条件可用下式表示
目标函数与约束条件构成整数规划，作为本文的求解模型。
4.2模型求解
编写LINGO程序并运行[5]，求得最优调运方案。最优调运方案的目标函数值为722.410辆km，实现运箱量为372 TEU，其中卸给A船的A类箱，卸给B船的B类箱209 TEU。5台龙门吊分别安排在a，b，c，e，f箱区，需要集卡13辆，各作业路上的车次数如表5所示。
如果龙门吊的数量减少1台，则最小周转量为778.970辆km，比出动5台龙门吊多56.560辆km，故龙门吊的数量不宜减少。
4.3模型存在的问题
（1）以上调运方案的车次数是优化结果，仅求出龙门吊安排的箱区及各作业路上载运的箱量，对所需集卡的数量也只是估算，没有具体到各作业路的集卡派车计划，故还可进一步深入求解；
（2）带入模型的算例数值与现代化集装箱码头的实际数据仍存在较大差距，且未考虑码头可能在集卡装载重箱进场时就将待装各船舶的集装箱集中分配在各箱区的情况；
（3）将运输成本最低作为模型的目标函数仍存在一定问题，因为码头不仅要考虑成本问题，还要考虑整个系统的运行效率等问题。
文中的假设条件使得模型与现实情况仍存在一定差距，故本文只是给出单个班次生产计划的快速算法，作为码头堆场调度人员合理安排车辆调度和具体路径计划的参考依据之一，并不能作为码头的最终计划，所以本文的模型仍需要进一步讨论和探究。
参考文献：
[1] STEENKEN D，HENNING A，FREIGANG S，et al. Routing of straddle carriers at a container terminal with the special aspect of internal moves[J]. OR Spektrum，1993，15（3）：167-172.
[2] BYUN J W，JO K H，LEE Y S．Optimal supervisory control systems for automated unmanned container transporters in the automated container terminals[C]// Proc 4th Korea-Russia Int Symp Sci & Technol，Ulsan，South Korea，2000：206-211.
[3] 杨静蕾．集装箱码头物流路径优化研究[J]．水运工程， 2006（1）：32-35.
[4] 张维英， 林焰， 纪卓尚．基于拖车路径优化的集装箱船配载模型研究[J]．大连理工大学学报，2005，45（6）：827-831.
[5] 袁新生，邵大宏，郁时炼．LINGO和Excel在数学建模中的应用[M]．北京：科学出版社，2007：230-246.
（编辑：张婕收稿日期：2011-01-05）
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
STEENKEN等[1]运用启发式算法研究集装箱码头的集卡运输路径安排问题；BYUN等[2]提出最短路径算法，寻找集卡行驶时间最短的路径；杨静蕾[3]以集卡行驶里程最短为目标，建立集卡路径优化模型，求解集卡最优行驶路径；张维英等[4]以集卡将码头堆场的集装箱送到岸边桥式起重机（以下简称岸桥）所运行的最短距离为目标，建立配载模型，并应用Hopfield神经网络模型进行计算机模拟。
目前大部分港口的集卡运输采用传统作业工艺，司机操作较简单，不易出错，便于管理和考核；但是，随着科学技术的进步和港口物流业的发展，该模式的弊端逐渐暴露。首先，单条作业路上的集卡配置量为固定值，配置不足可能导致岸桥等待集卡，在码头前方作业区形成瓶颈；配置过剩又会浪费资源，影响港口生产效率。其次，在传统作业工艺中，集卡为指定的岸桥服务，移动仅限于单条作业路，即集卡在完成装船、卸船、转堆等作业后，必须空驶回到堆场或者码头，然后进行下一次作业，造成集卡空载率较高、利用率低下。最后，集卡分配给岸桥后沿固定路径行驶，当集卡数量过多时可能发生交通堵塞，给码头的生产效率带来很大影响。
本文打破传统作业工艺的束缚，主要从环保节能和经济性的角度出发，在利用现有集卡运输且满足特定工作任务总量的前提下，为使运输成本最小，建立整数规划的数学模型，运用LINGO软件，求得各箱区配备的龙门吊数量和集卡总量，以及从每个箱区至卸箱点单个班次内分配运箱量的最优调运方案。
1问题描述
集装箱码头堆场中分为若干个箱区，每个箱区的集装箱预先根据船舶航次（分别有2艘船舶同时进行装卸作业）分成A类和B类。每个箱区A类箱和B类箱的数量已知，并且最多只能安排1台龙门吊，龙门吊的平均装车时间为5 min。
集卡的卸箱点共4个，1号和2号桥吊为A船舶进行装卸作业，3号和4号桥吊为B船舶进行装卸作业，每个卸箱点都有各自总的作业量要求。从长远来看，卸箱点可以移动，但单个班次（8 h）内卸箱点不变，集卡的平均卸车时间为3 min。
集卡每次只能载运1个集装箱，平均时速28 km/h。集卡在等待时的能耗也是相当大的，因此原则上不允许发生集卡等待的情况。龙门吊装车点和桥吊卸箱点都不能同时为2辆及以上的集卡服务。集卡每次都满载运输。
龙门吊装车点到桥吊卸箱点的道路是专用的双向六车道（宽60 m），不会出现堵车现象。每段道路的里程是已知的。
本文所研究的集装箱堆场有箱区6个，卸箱点4个，龙门吊5台，集卡15辆。各卸箱点单个班次的装船量要求为1号桥吊78 TEU，2号桥吊，3号桥吊85 TEU，4号桥吊124 TEU。
各龙门吊装车点和桥吊卸箱点如图1所示。各装车点到卸箱点之间的距离见表1，各箱区拥有的A类箱和B类箱的数量见表2。
2基本假设
（1）忽略各种随机因素引起的龙门吊或集卡的临时停顿，即认为其在单个班次内连续工作；
（2）集卡在途中不发生堵车现象，空载与重载的行驶速度一样；
（3）龙门吊定好工作箱区后，单个班次内不再换箱区；
（4）如果8 h内完成任务，集卡可以提前退出系统；
（5）对所有集卡来说，本文所计算的单个班次是同时开始的；
（6）本算例中的数值仅限于小型且装卸效率较低的集装箱码头堆场。
3问题分析
3.1研究目标
单个班次的生产计划应当包括以下内容：出动几台龙门吊，分别安排在哪些箱区；出动几辆集卡，分别安排在哪些作业路上，单个班次内最多运输多少次（受随机因素影响，装卸时间和运输时间都不精确，因此排时计划无效，只需求出各条作业路上的集卡数量及安排即可）。合格的生产计划应在集卡不等待的条件下满足作业量的要求，而良好的计划还应当考虑以下原则：周转量最小，同时出动的集卡数量最少，运输总成本最低。
基于以上原则建立数学模型，并给出单个班次生产计划的快速算法；再针对实例，给出具体的生产计划和最优调运方案。
3.2约束条件
3.2.1集卡不等待的条件
刚开工时，集卡同时上班，会发生等待装车的现象。在正常运作后，应当限制同一作业路上的集卡数量，使之不发生等待现象。如从装箱点b到卸车点2的距离为0.99 km，集卡来回需要4.243 min，加上装卸车时间，单次运输周期合计12.243 min，那么该作业路上最多安排几辆集卡才不需要等待装车呢？安排2辆没有问题：第一辆开走后要过才回来；在这段时间内花5.000 min装第二辆，还余2.243 min；但来不及装第三辆。由此可见，该作业路上最多安排2辆集卡才能不发生等待，如果安排3辆则必定发生等待装车现象。
集卡从箱区Pi到卸箱点Qj的作业路上运行所需的时间为
式中：cij为从装车点i到卸箱点j的距离（i＝1，2，…，6； j＝1，2，3，4）；v为集卡平均速度。
1台桥吊（卸箱点）不能同时为2辆集卡服务，所以1条作业路上同时运行的集卡数量是有限制的。由于装车时间大于卸车时间，因此从Pi到Qj在集卡不等待的条件下最多能同时运行的集卡数为Aij＝[Tij / 5]，式中符号“[ ]”表示向下取整数。经过计算，各作业路上最多能同时运行的集卡数如表3所示。
3.2.2集卡运输能力限制
每辆集卡在从Pi到Qj作业路上单个班次内最多可运行的次数为
式中：60×8是每个班次的工作时间；（Aij－1）×5是开始装车时最后一辆车的延时时间；Bij是以该作业路上开始装车时最后那辆车来计算的。如果按第一辆车来计算，则
如果取该作业路上的平均延时，则
求得各作业路上每辆集卡的最多运行次数（见表4）。
从Pi到Qj作业路上Aij辆集卡单个班次内合计最多可运行次数为Mij＝Aij×Bij，每次载运1 TEU，则总箱量大约为Mij TEU。
3.2.3龙门吊和桥吊的总能力限制
对于不同作业路上的集卡是否会等待同一台龙门吊来装车的问题，可以通过宏观控制的方式尽量避免。因为单个班次内1台龙门吊最多装96辆集卡，所以控制每台龙门吊单个班次内的装车总数不超过96辆。每个卸箱点单个班次内最多卸车160辆，因此对于装箱点或卸箱点由不同作业路造成的冲突问题，只要平均时间内能完成任务，就认为不冲突，而不对集卡的运行时间作具体安排。考察以上数据可以看到，4号桥吊的卸车量最大，为124辆，小于160辆，则认为单个班次内不发生等待卸车的现象。
3.2.4工作任务约束
4个卸箱点的工作任务约束为dj＝（78，85，124，85）车次。
3.2.5箱区所储箱量约束
第i号箱区A类箱的储箱量为si＝（81，71，87，68，74，87）TEU，第i号箱区B类箱的储箱量为ki＝（61，68，64，68，71，81）TEU，从各箱区运出的A类箱和B类箱的箱量不能超过其所储箱量。
3.2.6龙门吊数量约束
龙门吊只有5台，而箱区有6个，龙门吊上班时一旦确定对应箱区，单个班次内不移动箱区，故只有5个箱区能各安排1台龙门吊，剩余1个箱区轮空。引入决策变量Yi，标志第i号箱区是否安排龙门吊：如果 Yi＝1则安排龙门吊，取 Yi＝0则不安排龙门吊。Yi在模型中与决策变量 xij一起进行优化，其值取决于优化的结果。
3.2.7集卡数量约束
最多能出动的集卡总数为15辆。按照运输计划，从箱区 Pi运到卸箱点 Qj的总箱量为xij，每辆集卡在该作业路上单个班次内最多可运行次数为Bij，故该作业路上应安排集卡辆，各路线合计不超过15辆，即
式中：决策变量xij是非负整数。
4模型的建立与求解
4.1目标函数和约束求解
求解原则如下：（1）周转量最小；（2）出动的集卡最少；（3）运输成本最低。其中，（3）与（1）（2）是因果关系，（1）与（2）是一致的目标。因集卡的安排必须以完成运输方案为前提来设计最优调运计划，故周转量最小是大前提和首要目标。周转量最小可以表示为，由于1是常数，故目标函数可以写成。
根据前文分析，约束条件可用下式表示
目标函数与约束条件构成整数规划，作为本文的求解模型。
4.2模型求解
编写LINGO程序并运行[5]，求得最优调运方案。最优调运方案的目标函数值为722.410辆km，实现运箱量为372 TEU，其中卸给A船的A类箱，卸给B船的B类箱209 TEU。5台龙门吊分别安排在a，b，c，e，f箱区，需要集卡13辆，各作业路上的车次数如表5所示。
如果龙门吊的数量减少1台，则最小周转量为778.970辆km，比出动5台龙门吊多56.560辆km，故龙门吊的数量不宜减少。
4.3模型存在的问题
（1）以上调运方案的车次数是优化结果，仅求出龙门吊安排的箱区及各作业路上载运的箱量，对所需集卡的数量也只是估算，没有具体到各作业路的集卡派车计划，故还可进一步深入求解；
（2）带入模型的算例数值与现代化集装箱码头的实际数据仍存在较大差距，且未考虑码头可能在集卡装载重箱进场时就将待装各船舶的集装箱集中分配在各箱区的情况；
（3）将运输成本最低作为模型的目标函数仍存在一定问题，因为码头不仅要考虑成本问题，还要考虑整个系统的运行效率等问题。
文中的假设条件使得模型与现实情况仍存在一定差距，故本文只是给出单个班次生产计划的快速算法，作为码头堆场调度人员合理安排车辆调度和具体路径计划的参考依据之一，并不能作为码头的最终计划，所以本文的模型仍需要进一步讨论和探究。
参考文献：
[1] STEENKEN D，HENNING A，FREIGANG S，et al. Routing of straddle carriers at a container terminal with the special aspect of internal moves[J]. OR Spektrum，1993，15（3）：167-172.
[2] BYUN J W，JO K H，LEE Y S．Optimal supervisory control systems for automated unmanned container transporters in the automated container terminals[C]// Proc 4th Korea-Russia Int Symp Sci & Technol，Ulsan，South Korea，2000：206-211.
[3] 杨静蕾．集装箱码头物流路径优化研究[J]．水运工程， 2006（1）：32-35.
[4] 张维英， 林焰， 纪卓尚．基于拖车路径优化的集装箱船配载模型研究[J]．大连理工大学学报，2005，45（6）：827-831.
[5] 袁新生，邵大宏，郁时炼．LINGO和Excel在数学建模中的应用[M]．北京：科学出版社，2007：230-246.
（编辑：张婕收稿日期：2011-01-05）
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文