基于时空拓展图模型的多码头间集装箱运输优化

丁 一， 何乐媚， 沙 梅

(上海海事大学 a.物流研究中心;b.交通运输学院， 上海 201306)

集装箱运输在全球贸易中扮演着重要角色，各大集装箱港口都在致力于通过扩大码头规模和增加码头数量满足日益增长的集装箱运输需求。由于中转箱码头之间拖运等原因，集装箱在大、中型港口的码头之间运输是不可避免的。OTTJES等[1]用ITT(Inter-Terminal Transportation)表示多码头间运输，这不仅是港口营运人和码头运营公司需处理的一个运营问题，而且是新建码头和集装箱港口规划中需考虑的一个战略问题。[3]水水中转和驳船作业是上海洋山港重要的作业类型，洋山港水水中转比例超过70%，其中绝大部分通过驳船进行。为保证该项业务的业务量持续增长，洋山港5期计划建设为全驳船集装箱码头，同时设立为 “驳船码头中心”，即所有港口进口和出口驳船不再停靠该码头以外的其他码头。洋山港码头分布图见图1。

图1 洋山港码头分布图

国内外学者已针对多码头间运输优化开展许多研究。HEILIG等[2]提出关于ITT问题的文献可分为优化算法[3-6]、仿真研究[9-11]和信息系统方法等3类。[12-13]现有研究主要集中在鹿特丹港马斯莱可迪地区，为进一步评估所提出方法的有效性，需考虑不同港区的实证研究。基于此，本文建立新的整数规划模型以验证洋山港新建码头的ITT成本优化结果。当前已有几种优化模型可用于研究ITT问题。TIERNEY等[3]利用时空图提出ITT完整定义的数学模型，考虑集装箱长期装卸节点，求解车流与多商品流的最优组合问题，该研究只考虑最小化因交付集装箱超过截止日期而产生的罚款，缺乏对运输中其他成本的考虑。NIEUWKOOP等[4]提出一种具有时空拓展图的确定性最小费用流模型，通过寻找最优的车辆配置，最大程度地减少延迟成本。该研究未考虑通过采取最优的ITT交付、车辆装载和发车计划降低总运营成本和延误成本。HU等[5]提出一种禁忌搜索算法，用于解决港口码头到铁路终端的ITT问题，建立ITT与铁路运输相结合的数学优化模型。该研究未考虑运输车辆的额外成本与延迟成本之间的均衡问题。在集装箱卡车运输研究方面，李顺勇等[7]建立多通路网络下的多车型低碳城市配送混合整数规划模型，根据问题特征提出一组加速模型求解的有效不等式。

分析现有研究可知:高效的ITT网络的主要目标是最小化运输延迟成本,同时，缩短运输时间和处理时间、减少空车和费用、提高占用率、避免交通堵塞[2]和减少碳排放[8]等。ITT问题研究的关键是在港口的不同码头之间实现高效、安全和可靠的运输。[4]现有文献缺乏对ITT问题中多种新型运输设备效率和成本的比较，以及通过对ITT问题进行研究，辅助港口对新建码头道路布局做出决策。本文研究的目标是为ITT系统构建可靠的数学模型，并通过定量分析估计使用特定ITT运输设备、新基础设施和交通规划的成本,帮助港口营运人正确选择码头的道路布局和码头之间的运输连接，以及车辆的类型和数量，保证港口具有高效的物流运输，提高港口ITT作业效率，降低相关成本。

1 问题描述

ITT是指集装箱在港口内各码头(海运、铁路或其他)之间的移动。本文研究的ITT问题与车辆路径问题(Vehicle Routing Problem,VRP)非常相似，都与给定网络上具有给定释放和交付时间的装运集装箱有关。与典型的码头内运输(即在有限的距离内将集装箱从起重机移动到堆垛机)相比，ITT拥有专用的封闭路线运输网络，且不与其他模式或系统交互。为在港口不同的码头之间实现高效、安全和可靠的集装箱运输，并确定与ITT系统不同需求水平相匹配的最佳车辆配置，本文提出一种基于时空拓展图的确定性最小成本流整数规划模型，并将目标函数扩展到考虑整车需求和整个系统的性能水平。

实现集装箱ITT作业的运输设备有自动引导车(Automated Guided Vehicles，AGV)、自动举升车辆(Automated Lift Vehicles，ALV)和多挂车系统(Multi Trailer System，MTS)。DUINKERKEN等[9]对这几种运输设备的性能进行对比，并通过仿真模型对其实际运行效率进行分析。ITT研究需确定合理的运输设备和设备的数量，以提高港口车辆资源配置效率；生态目标是进一步减少通过ITT产生的CO2排放。近年来,国内外很多港口都在推进无人驾驶电动集卡在港口运输作业中的应用，本文考虑多种ITT运输设备，如AGV、ALV、MTS和无人驾驶电动集卡，并对多种运输设备的运输效率和成本进行比较分析。

时空拓展图[4]是能通过ITT系统在时间和空间上对集装箱流进行建模的图，可详细描述集装箱随时间的移动过程。因此，引入一个基于时空拓展图的优化模型确定ITT网络中车辆和集装箱的最优流动。首先建立一个基本图V(N,A)，其中:N为基本图节点集合，N={1,2,…,n+m}，n为码头节点数，m为交叉路口节点数；A为连接基本图弧线(i,j)的集合。通过对时间进行扩展，即通过复制基础图，每次复制1个时间步长λ，提出时空扩展图TLD(NT,AT)，其中:NT为时空扩展图的节点集合，NT={1,2,…,τλ(n+m)}，τ为时间段的数量，λ为时间步长；AT为时空扩展图弧线的集合;Nint为交叉路口节点的集合，Nint={1,2,…,m}。车辆在时间周期范围内开展集装箱运输活动，时间t=1,2,…,τλ，其中:τλ为时间周期的长度。通过该时空拓展图ITT系统，可在时间和空间上对集装箱流进行建模，并通过时间拓展和空间描述，更好地解释基于ITT网络的各码头之间集装箱转运的过程。

时空拓展图见图2。图2中：左边部分为基本图，包含3个港口码头节点和1个交叉口路口节点;右边部分为时空拓展图。设时间步长为10 min，假设2个转运任务，其中：任务1为将集装箱从码头1运输到码头5;任务2为将集装箱从码头3运输到码头1。假设执行这2个任务的运输设备为同一辆AGV，任务释放时间均为t=0，交货时间为t=40 min。执行任务的运输车辆在t=0时接到任务后，分别在码头1和码头3的堆场装载集装箱运往目标码头, 到达目标码头之后在码头堆场卸下集装箱。图2中，带箭头的实线表示运输任务1的车辆行驶路线；带箭头的虚线表示运输任务2的车辆行驶路线。运输任务1在规定交货时间内完成运输任务，而运输任务2由于交叉路口拥堵，导致延迟5 min完成运输任务，因此运输任务2将产生延迟成本。

图2 时空拓展图

2 模型构建

2.1 数学模型构造

文献[3]提出的数学模型用于尽量避免集装箱交货延误，该模型考虑4个码头节点和2个交叉口，规划时间为8 h，时间步长为5 min。本文基于时空拓展图提出一个新的整数规划模型，用以优化ITT问题。与文献[3]提出的模型相比，该模型能包含ITT网络所需的车辆数量和运输需求,对堆场中集装箱装卸[14]、实载行程、空车行程、处理时间和道路拥堵进行建模。同时,该模型考虑集装箱延误惩罚成本、运输车辆启用成本、运输车辆司机工资成本、车辆运输和装卸成本。

最小化运输车辆由于集装箱运输延迟而造成的惩罚成本，表达式为

(1)

使车辆启用总成本之和最小的目标函数为

(2)

式(2)中:Tsθ为满足运输需求θ的集装箱释放时间，为λ的整数倍；bh为h型车辆每次运输启用费用；Ch为h型车辆的承载集装箱能力，Ch∈{1,5}。

使车辆支付的司机工资成本之和最小的目标函数为

(3)

使运送集装箱所花费的车辆运输成本之和最小的目标函数为

(4)

为保证在运输需求的起始点、中间流转位置和终点流动的集装箱流平衡设置约束条件为

(5)

Tsθ≤t≤τλ;k∈NθD;θ∈Θ;h∈H

(6)

(7)

式(5)～式(7)中:Oθ为运输需求θ的起始点；∂θ为运输需求θ需要运输的集装箱数量;NθD为不与需求θ起点和终点匹配的其他节点集合，NθD={i∈NT|i/τ≠Oθ∧i/τ≠dθ}；H为所有车辆类型的集合，H={1,2,…,h}。

限制运输线路启用的运输车辆数要小于等于该线路持有车辆总数上限，有

Tsθ≤t≤τλ;h∈H

(8)

为防止集装箱被存储在交叉路口节点，有

Tsθ≤t≤τλ;(i,j)∈Asta;h∈H

(9)

式(9)中:Asta为静止弧的弧线集合，静止弧上的车辆和集装箱不会在空间中移动，在给定的时间周期内停留在同一节点。

为限制规定时间步长内在交叉路口节点的持有车辆总数上限，防止交叉口车辆拥堵有

r∈Nint;Tsθ≤t≤τλ;h∈H

(10)

式(10)中:Γint为交叉路口节点的最大车辆吞吐量。

为保证在堆场装卸节点内的集装箱流平衡,有

(11)

为将装卸节点与运输需求起始码头节点相连接，即在堆场上将集装箱通过堆场装卸设备装载在运输车辆上，有

(12)

为将装卸节点与运输需求终点码头节点相连接，即在堆场上将集装箱通过堆场装卸设备从运输车辆上卸载下来，有

θ∈Θ;h∈H

(13)

j∈NLT;θ∈Θ;h∈H

(14)

j∈NLT;θ∈Θ;h∈H

(15)

考虑装载和卸载集装箱所花费的时间，约束每种车辆在规定时间步长内可在节点上执行的装卸操作的最大数量，有

j∈NLT;θ∈Θ;h∈H

(16)

式(16)中:ldi为在给定时间段中节点i同时运动的集装箱最大数量。

在运输需求起始点与终点装载的集装箱数量的表达式为

θ∈Θ;h∈H

(17)

(18)

限制车辆运输过程总花费时间要大于等于运输时间与运输车辆充电时间之和为

(i,j)∈AT;θ∈Θ;h∈H

(19)

式(19)中:当h型车辆不是电动车辆时，σh等于无穷大;当h型车辆为AGV时，σh=600(时间步长以min为单位);当h型车辆为无人驾驶电动集卡时，σh=240;Ba为无人驾驶车辆每次充电时间，为λ的整数倍；σh为h型车辆充电系数。

在运输开始之前，集装箱不需要被交付的表达式为

(20)

式(20)中:Ts′为满足运输需求θ的集装箱最早释放时间，Ts′=min(Tsθ)。

运输车辆在交叉路口节点的起始数量为0,表达式为

(21)

运输车辆在运输开始之前数量为0，表达式为

(22)

2.2 有效不等式

首先运行式(5)～式(22)，并求解相应的整数规划模型。式(5)～式(22)对应于集装箱多商品流[3]，通过GUROBI或其他开源的混合整数规划求解器即可求解出最优解，但像GUROBI这样的求解器对多商品流结构有很大的削减作用。通过分析问题的结构，构建以下有效不等式形成割平面，控制车辆的流动并确保集装箱由车辆运输，可收紧模型的可行域，加快收敛过程和求解速度。然后加入式(23)～式(25)有效不等式与式(5)～式(22)一起运行这些求解整数规划问题。

1)车辆在运输需求的最早释放时间出发，有

(23)

式(23)中:V为所有车辆的集合，V={1,2,…,v}。

2)限制进入节点车辆数量与离开节点车辆数量相等，有

k∈NθD;Tsθ≤t≤τλ;h∈H

(24)

3)车辆交付的集装箱数量不能超过其承载能力，有

Tsθ≤t≤τλ;h∈H

(25)

将车辆与集装箱连接在一起，限制在ITT网络上行驶的车辆所能装载的集装箱最大数量要大于等于在ITT网络上流动的集装箱的总数量。不同类型车辆的最大承载能力不同，其中MTS每次最多能运输5个集装箱。

3 算例分析

根据洋山港码头区域的ITT网络布局、运输需求和运输设备的属性生成多组数据集，对数学模型进行求解，并对运算结果进行系统分析。

3.1 ITT网络布局

洋山港坚持将水水中转作为集装箱业务增长的重要支撑，持续优化航线航班配置和集、疏运网络。洋山港共有5个集装箱码头，其中洋山5期驳船码头为新建码头，最远的2个码头之间的直线距离为10 km。若新建码头与原有码头都有驳船停靠，则ITT 网络图见图3，设此“无驳船码头中心”的ITT运输网络为运输网络1;若只有洋5能停靠驳船，则ITT 运输网络图见图4，设此“有驳船码头中心”的ITT运输网络为运输网络2。

图3 “无驳船码头中心”运输网络1

图4 “有驳船码头中心”运输网络2

3.2 运输需求

当每天不同运输需求的情形发生时，为测试不同运输方式和2种ITT运输网络的性能表现，各码头之间的集装箱运输需求由需求生成器产生[4]，该需求生成器根据3种场景创建需求(见表1)，且各阶段的需求量区间都服从均匀分布。

表1 3种运输需求场景的属性

需求生成器的其他属性还包括起始码头与目标码头、集装箱释放时间与交付时间。在“无驳船码头中心”的运输网络1中，将洋山港的任一码头a匹配其他任一的码头b，需求释放时间为[0,tmax-2time(a,b)]范围内随机均匀选择的释放时间;在“有驳船码头中心”的运输网络2中，将洋山5期码头与其他任一码头c匹配，需求释放时间为[0,tmax-2time(5,c)]范围内随机均匀选择的释放时间。tmax为运输车辆在码头之间运输的最大时间值;time(a,b)和time(5,c)为运输车辆在码头之间运输的最小时间值。

3.3 运输设备的属性

基于对洋山港各码头实际情况的调查研究，根据港口区域相关数据和ITT运输设备相关数据(见表2),可得到用于算例分析的人工试验数据集。

表2 ITT运输设备相关参数

3.4 测评结果分析

通过将码头节点、交叉路口节点和运输道路建模为一系列节点和弧线，输入需求生成器创建的集合和4种运输设备相关参数，共生成240个实例。采用PYTHON编程，并用GUROBI求解器进行求解，使用Intel Core i5、1.80 GHz CPU和8G内存的计算机运算。测评部分结果汇总表见表3，展示了求解模型本身加上有效不等式之后(模型+VI)的运算时间，以及两者的对比倍数。由表3可知:随着运输任务数量与运输集装箱总数的增加，有效不等式的加速作用更加明显。

表3 测评结果汇总表(部分)

对4种不同ITT运输设备的测试进行汇总，结果见图5。由图5可知：在“有驳船码头中心”运输网络2与“无驳船码头中心”运输网络1对比下，4种ITT车辆的总成本和最低调用车辆数都有所下降；在低谷需求下，总成本下降比率分别为15.22%、6.46%、25.73%和19.81%，调用车辆数下降比率分别为15.21%、17.99%、21.25%和30.07%;在常规需求下，总成本下降比率分别为23.04%、13.85%、22.29%和13.26%，调用车辆数下降比率分别为42.86%、18.55%、25.27%和13.07%;满足在高峰需求的总成本下降比率分别为25.27%、12.78%、16.74%和9.50%，调用车辆数下降比率分别为22.28%、12.50%、12.64%和4.81%。

通过对测评结果进行整体分析可知：就2种运输网络而言，在满足3种不同运输需求的情况下，“有驳船码头中心”相比“无驳船码头中心”运输网络,在码头节点最低调用车辆数量和总成本上都更低。随着运输需求数量的增加，人工驾驶车辆(ALV和MTS)总体上相比无人驾驶车辆,启用比率下降，速度和总成本下降速度更快， MTS在最低调用车辆数上的表现最好，成本偏高。港口可根据实际需求情况使用哪种ITT运输方式完成运输。

a)AGV b)无人驾驶电动集卡

c)MTS d)ALV

4 结束语

本文对新建港口的多码头间集装箱运输问题进行研究，基于时空拓展图提出一种整数规划模型。结合港口实际运输数据，包括需求任务集和作业时间要求等，确定最佳的车辆配置和最小化成本，研究ITT问题的特性和影响。同时，对洋山港ITT问题进行算例分析。结果表明:将新建码头设立为“驳船码头中心”能有效降低ITT成本和减少调用车辆数量，验证有效不等式对大规模问题的加速作用。本文的研究结果可为港口营运人员对ITT运输设备、车辆数量和配置等进行相关战略决策及对港口扩建码头的道路进行布局提供支持。该研究也存在不足之处，例如：ITT模型中并未考虑驳船等长期运输工具，也未结合智能优化算法对ITT数学模型进行更深入的研究，这是港口ITT问题研究的一个方向。