题目：Models on ship scheduling in transshipment hubs with considering bunker cost
作者：Lu Zhen,Tao Shen,Shuaian Wang,Shucheng Yu

摘要

This paper studies a decision problem for scheduling ships’ starting operation time in a transshipment hub with considering the bunker cost and the transshipment cost of containers. Based on the information about the handing capacity of the container port in each period, the port operator makes a proper decision and informs the shipping companies about the start operation days of each liner route. The optimized decision may help shipping companies significantly reduce the cost. This study proposes a mixed integer programming model. The NP-hardness of the problem is proved. A local branching based solution method is also developed for solving the model. Extensive numerical experiments demonstrate the optimality of the solution by the proposed method is less than 3% for large-scale problem instances.

批注：这篇论文就是针对需要进行中转作业的船只，决策starting operation time（这个词组就是指船舶从哪个period（文中在建模的时候考虑的规划期是1周，也就是168小时，把1个period定义为1个小时）起开始在转运港作业，对应模型中的变量和。关键是这个starting operation time为什么会对成本产生影响呢？因为作者研究的场景，见Fig3，有一个非常重要的假设，就是说船舶离开previous port和到next port的时间是确定的，这就会导致什么呢？比如你第一个leg跑的很慢，非常晚才到中转港，那为了保证货物准时送达next port，第二个航段就得加足马力狂奔，这么一来燃油成本一下子就上去了）以最小化燃油成本和中转货物在中转港的库存成本（这里涉及到中转港的库存成本的原因是作者研究的对象是拥有dedicated terminal的航运公司，这一点在后文也提到了，文中提出的那个模型追求的是航运公司和港口整个系统的最优）。在模型求解方面，作者先证明了提出的模型是一个NP难问题，所以用精确求解算法求解一些规模较大的问题就不现实了，然后他们提出了一种局部分支的算法，并且和Cplex、一种基于序列的启发式算法进行了比较（比较用的指标是CPU时间和GAP值，后面去估计他们提出的算法在大规模问题上GAP小于3%的过程很巧妙，用了Cplex算的Lower Bound作为桥梁）。

批注：这个Fig3就是这篇文章研究的场景，只考虑一个dedicated terminal的情况（当然，后面作者通过拓展的模型考虑了两个dedicated terminal的情况），最左端和最右端的竖线指的应该就是文中的previous port和next port，中间的圆代指的就是tansshipment hub。上图描述的情况是这样——船舶1部署在1号航线上，船舶2、3部署在2号航线上，并且船舶1上边有货物需要转到船舶2上在2号航线上航线，由于船舶1、2到达中转港的period可能是不一致的，所以start operation time的差异就会导致中转集装箱库存成本的产生。此外，它还直接影响着左右两个航段的燃油成本。

背景部分

Container shipping is vital to global trade. The international ocean freights are mainly containerized especially in the transshipment hubs. There are two major players in container shipping: container shipping lines and container port operators (Talley and Ng, 2013). The benefits and cost issues on their sides (port operators & shipping lines) are intertwined. Efficient operations on one of the two sides will benefit the other side. This paper focuses on port operation problems in transshipment hubs, as the transshipment has become more and more important in terminals around the world. This trend is expected to continue especially when ocean liners are using larger ships and visiting fewer ports.

批注：这段话来自于Introduction部分，就是说转运变得越来越重要，所以要研究转运港运营的问题。另一方面，参与在转运过程中的两个主体——集装箱航运公司和集装箱港它们的收益和成本是紧密交织在一起的，所以要系统考虑双方，实现系统的最优，而不单单是某一参与主体（这一点在7.1节也有提到:“The port operator and the shipping line must collaborate closely to achieve the overall system optimization (i.e., the minimization of fuel cost and transshipment container holding cost). Otherwise, the port operator may be more concerned about its own interest. The port operator and the shipping line can make decisions in a holistic manner if the terminal is a dedicated one operated/used by the shipping line. This is common in reality, and this is the motivation of our study.”）。

模型部分

符号说明

集合和参数

：船舶的索引。
：所有船舶的集合。
：period的索引。
：所有period的集合，考虑服务周期是1周，1个period对应1个小时，所以的cardinality就是168。
：索引为的船舶可以在哪个period到达中转港的集合，计算方法应该是 $船舶能在规定时间到达$ 。
：允许船舶在中转港停留的period数的集合，比如就表示船舶最少可以在中转港停留1个period，最多可以在中转港停留48个period。
：船舶在第个period到达中转港，停泊个period，且这个period中包含了第个period的所有的集合。
：一个集装箱在中转港存放一个period的费用。
：岸桥在一个period可以移动的次数，衡量的是中转港口的装卸货物效率。
：泊位的数量。
：船舶在第个period从previous port到中转港的燃油成本。作者用回归分析方法给出了它的计算公式，它是航段长度（与，即是哪一个船有关）和t的函数。
：船舶在第个period从previous port到中转港并在中转港停泊个period的情况下，从中转港到next port的燃油成本。作者用回归分析方法给出了它的计算公式，它是航段长度（与，即是哪一个船有关）和t的函数。
：需要从从船搞到船上运输的集装箱的数量。
：船舶分别在第个period到达中转港的情况下船上的这批集装箱需要在港口放多长时间。文中是直接给了一个很简单的公式去计算这个参数，但没说公式咋来的…

决策变量

：0-1变量，取1就表示船舶在第个period到中转港，反之亦反之。
：0-1变量，取1就表示船舶在第个period到中转港并在中转港停泊个period。

模型建立

批注：目标函数相对比较好理解，第一项就是整个船队在previous port到中转港这个leg上花费的燃油成本，第二项是整个船队在中转港到next port这个leg上花费的燃油成本，第三项是在中转港总的集装箱存储成本。约束条件中前三项也比较好理解，分别表示一艘船舶什么时候到中转港、停留多久是唯一的，船舶不可能在之外的period到达中转港，和之间的关系。第四个约束条件（装卸能力限制）是最难理解的，其中表示的是需要从船卸下和装上的集装箱的数量，就表示船平均每个period需要使用多少次岸桥，所以就表示船在第个period所需使用的岸桥移动总数，最后对求和自然就表示整个船队在期需要多少次岸桥移动了，这个总的移动数不能超过港口在1个period的最大岸桥移动次数。第五个约束就是泊位数量的限制。整个模型在形式上是一个非线性的MIP（目标函数中存在的两个0-1变量相乘，）,为了降低求解难度，可以做一下线性化处理，同时注意到前三个约束就保证了，所以这个变量限制也可以直接松弛掉。

的线性化处理：引入一个连续变量，将目标函数中的替换为，并加入如下约束。

批注：这就是两个0-1变量相乘线性化的问题，我比较不确定的是为什么原文中并没写前两条约束，是否是因为出现在最小化目标函数中，所以可以忽略上界条件？

The model can incorporate a number of other practical considerations.

The shipping line may not only be interested in the optimal solution, but also interested in obtaining the best few solutions and then choosing one from them. The shipping line may not choose the optimal solution as it may have other considerations that are not modeled.

批注：多模态问题在GA常见有两种思路——并行小生境（通过共享机制对处于拥挤小生境的个体适应度值进行惩罚）、串行小生境（可以通过对搜索空间施加约束来避开已经找到过的最优解）。感觉他这里应该用的是后者，约束（17）的作用是保证当前解和下一次迭代的解至少有一项是不同的，从而避开已经找到过的最优解。

If a ship cannot arrive at the port in a particular period , for instance, because a major shipper objects the arrival time , then we could easily incorporate this consideration by adding the following constraint:
If Ship and Ship must arrive at the port at the same period for commercial reasons, then we could add the following constraint:
The shipping line may want to know, given the arrival time of each ship , if in a particular week the demand is higher than the forecasted values , how many extra containers can be handled. Suppose that an extra (percentage) of containers can be handled, then we can solve:

批注：（4）考虑的是在估计的下我们可以用前面提出的那个模型确定出，现在的问题是在已知的情况下想知道还能在港口“压榨“出多少装卸能力。此外，这个模型也是可以线性化的，第三个约束中的移到右侧，令。

算法部分

The model is a mixed-integer programming model containing both continuous variables and and binary variables . As we know linear programming is polynomially solvable while general integer optimization problems are NP-hard, the bottleneck for solving model lies in how to efficiently handle the large feasible set of decision variables . We do not expect to solve all of the large-scale instances of to optimality in reasonable time, but apply an effective approach that could obtain high-quality solutions efficiently. In view of the development of the state-of-the-art mixed-integer linear programming solvers, we apply a local branching strategy to solve the model (Fischetti and Lodi, 2003). The core idea of our local branching based method is to use the CPLEX solver as a black-box ‘tactical’ tool for exploring suitable solution subspaces, which are defined and controlled at a ‘strategic’ level by a simple external branching framework. Different from the conventional branch and bound search process, local branching uses a highly imbalanced search tree: one branch has a very small feasible set and is solved to optimality by CPLEX; the other branch has a feasible set that is too large to be explored completely. After the smaller branch is solved, the larger branch is branched again into two imbalanced branches. The branching strategy favors early updating of the incumbent solution, thereby producing improved solutions at early stages of the computation. In other words, high-quality solutions are obtained.

批注：这个算法的终止条件我是第一次见，一般的算法都是通过最大迭代次数、GAP或最长求解时间来决定何时终止，他这里用的是解的最大未改进次数。另外需要注意的就是算法中用来产生imbalanced search tree的约束（37），表示的是的1范数，即，几何上表示一个以为中心，半径为的超立方体的内部，当取得比较小的时候，它应该分出来的是原来可行域中很小的一部分，因此就可以使用solver直接解出来了，然后就是的问题，这个东西的作用应该就是来微调超立方体的大小的。

For evaluating the performance of the local branching based solution method, we compare it with the optimal solution directly obtained by the widely used CPLEX solver. In addition, we also compare with another meta-heuristic based on a given sequence of ships. This heuristic is called sequence based method (heuristic) and was proposed by Lee et al. (2006) and widely used in solving some optimization models on port operations.

批注：这块儿主要是学习做算法有效性分析的思路，作者用的算法性能评价指标是CPU时间和GAP值，Table1是在船舶规模为20的算例上进行的实验，比较好理解。但在大规模算例的比较就比较有技巧了，因为cplex没办法短时间解出大规模问题的最优解，所以作者考虑用原问题的下界作为桥梁去评估算法，具体操作是——把目标函数中关于转运成本的项删除掉，再把装卸能力约束去掉得到一个新模型，Cplex求这个模型的最优解是很容易的（无论规模多大），把这个模型的最优值作为Lower Bound。然后，注意到Cplex解规模为20条船问题的最优解都和对应Lower Bound有1.704%的GAP，而局部分支算法在规模为40条、50条船的问题上和对应Lower Bound也只有1.915%和2.094，把Lower Bound作为桥梁即可得出本文提出的局部分支算法在大规模算例上GAP可能远小于3%的结论。

术语积累

transshipment hub：中转枢纽港
shipping lines：航运公司，注意line这个词可以指运输公司
berth,quay cranes,yard cranes,yard trucks：泊位、岸桥、场桥、堆场集卡
terminal：码头，注意码头和港口的关系，一个港口可以有若干码头
consolidation of services：服务整合
empty container repositioning：空箱调运
port call：港口停泊
Berth allocation problem(BAP)：泊位分配问题
leg：航段
route：航线，一个航线包含若干航段
free time of transshipment containners：转运集装箱的免费存储时长
state-of-art：最先进的
dedicated terminal：专用码头
P问题：有多项式时间算法求解的问题
NP问题：不确定多项式时间求解的问题，就是说还没发现多项式时间算法，但是可以用多项式时间算法验证一个解到底是不是这个问题的解的问题
NPC问题：NP完全问题，即NP难问题和NP问题的交际，满足：（1）是NP问题（2）有多项式规约算法把所有NP问题归结为它
NP-Hard问题：NP难问题，满足：有多项式规约算法把所有NP问题归结为它。如果知道一个算法是NP难的，基本就别想用精确算法找最优解了

读后批注

This study also has limitations. For example, this study only considers the time cost for the transshipped containers in a port but the transportation cost for them is not taken into account. In addition, global maritime transportation contains a lot of uncertainty (Zhen, 2015; Zhen and Wang, 2015), which will further complicate the current model which is mainly for a deterministic decision environment. The above issues could be some interesting research directions for our future study.

批注：这是作者认为本文的不足之处——（1）只考虑了时间成本通过中转集装箱的库存成本体现但是没有考虑运输成本。不太理解这里说的中转集装箱的运输成本是什么，是它们在中转港内运输的成本吗？（2）模型是在确定性环境下搭建的，没有考虑任何不确定性因素。

Proposition 1: The ship scheduling problem described by model is NP-hard.

批注：看不懂作者在4.3节是怎么证明是NP-Hard问题的。需要补数学知识？