论文题目：Integrated vessel traffic scheduling and berth allocation with restricted channel widths
作者：Duan Hongda et al.
问题归属：航道调度+内锚地分配+泊位分配

决策过程简述

船舶到港后首先到锚地临时停泊，VTS需要决策什么时候把船舶放进航道，亦或是是否拒绝在当前规划期为船舶提供服务，船舶进入港内水域后，港口管理人员则需要根据港内水域泊位的使用情况决定让船舶直接前往某个泊位还是先前往某个内锚地等待。作业结束后VTS需要根据航道的使用情况决定让船舶在前往某个内锚地等待还是直接进入航道。最后船舶离港。

有啥贡献？

  • 问题层面：先前研究航道调度的文章对航道宽度和船舶宽度的刻画都是固定的，进而使得船舶在航道的航行规则是固定的，要么只能单向通行（单向航道）、要么只能双向通行（双向航道）、要么某些段可以单向某些段可以双向（复式航道），他这篇文章考虑船舶的在航道的航行模式并不是固定的，而是同时取决于变化的航道宽度和异质船舶宽度（单双向切换航道）。
  • 模型层面：建模比较漂亮，频繁使用“把复杂因素隐藏到集合的构造”当中的技巧。
  • 算法层面：使用列生成算法的过程中利用机器学习模型去缩小子问题的规模，思想比较有意思。

单双向切换航道有人做过，那他这个还有啥贡献？

刘老师的Short-term berth planning and ship scheduling for a busy seaport with channel restrictions以及Corry19年那篇TS也研究的单双向切换航道，但某种程度上是假设航道宽度固定，从而船舶是否可以双向通行只取决于船舶自身的宽度。如果一艘船舶禁止双向航行，在整个航道他都只能单向航行模式。但是Duan他们这篇文章，船舶在航道的航行模式是同时依赖于航道宽度和船舶宽度的。可能船舶在某个航段只能单向航行，但是在另一个航段又可以双向航行了。

模型推导

  • 决策：船舶进入航道的时刻、内锚地选择、某个时刻是否占用内锚地、某个时刻是否占用泊位占用哪个泊位
  • 目标：最小化船舶服务拒绝惩罚+靠泊延误惩罚+离港延误惩罚
  • 考虑的因素
    1. 潮汐条件影响
    2. 船舶安全裕度
    3. 船舶宽度和航段宽度对船舶航行模式的影响（这篇文章的特色因素）
    4. 泊位使用不重叠
    5. 内锚地使用不重叠
Notation Description
set of navigation channels.
Set of channels accessible for vessel during its entry or exit from the port.
set of time steps in the planning horizon.
Set of time points when vessel is permitted to enter channel .
set of segments of channel , where denotes the total number of segments in channel .
set of inner anchorages.
set of dummy anchorages, where is the index of the dummy anchorage associated with channel .
set of berths.
Set of berths eligible for serving vessel .
set of vessels to be served during the planning horizon.
Travel duration between inner end of channel and berth .
Travel duration between inner end of channel and inner anchorage , .
Travel duration between inner anchorage and berth , .
Travel duration to navigate through channel (which equals the number of segments of channel ).
Vessel safety clearance in channel .
Width of the th segment of channel .
Arrival time of vessel .
Desired berthing time of vessel .
Desired port departure time of vessel .
Deadline on the port departure time of vessel .
Service duration of vessel at berth.
Width of vessel .
The cost incurred for the non-completion of vessel ’s service within the designated planning horizon.
The cost incurred for the berthing delay of vessel per unit of time.
The cost incurred for the departure delay of vessel per unit of time.
if vessel enters channel at time when it enters/leaves the port; otherwise.
if vessel utilizes anchorage when it enters/leaves the port; otherwise.
if vessel occupies anchorage at time when it enters/leaves the port; otherwise.
if vessel arrives at berth at time ; otherwise.
if vessel fails to receive successful service throughout the planning horizon; otherwise.

这篇文章比较有技巧的地方是他把一些复杂的因素放到集合的构造中了，这样子模型看上去会特别的简洁（目前还不太清楚能不能带来性能上面的改善，因为这种把复杂因素放入集合构造中的技巧，本身会引入大量 0-1 变量，从集合里面选择合法元素，太多的01变量会不会让求解比较慢呢？）。比如要求船舶在航道的航行过程必须处于某个潮汐窗口内部，常见的做法是引入潮汐窗口选择约束变量，然后用一个不等式约束保证船舶在航道的整个航行过程一定位于潮汐窗口内部。他是直接把潮汐窗对船舶进航道时间的影响隐藏到集合的构造中了，就是说你船舶的进港时刻必须位于这个集合中的某个值才能保证船舶在航道的整个航行过程位于潮汐窗口内部。

BIP模型咋推？

目标函数比较好理解，这一项算的是船舶开始靠泊的时刻。这一项算的是船舶出港的时刻。

约束部分，船舶进出港时间、内锚点和泊位使用都是通过01变量刻画的。

Part1：因此，对于一条船舶他的这些选择应该是唯一确定的，所以存在一批选择唯一性约束：

（1）船舶进港（出港）对航道和时刻的选择唯一

  1. 这篇文章船舶进港时刻指的是船舶处于航道的outer end的那个时刻
  2. 这篇文章船舶出港时刻指的是船舶处于航道的inner end的那个时刻

（2）船舶进港（出港）对内锚地的选择是唯一的

（3）船舶开始占用哪个泊位、开始占用时刻是唯一的

Part2： 泊位和内锚地是离散资源，可看做并行机，对于这些资源的占用要求使用时段不发生重叠。常见套路是利用资源使用次序变量结合大M约束把时间错开，可参考往期博客。但这篇文章船舶靠泊哪个泊位以及开始靠泊的时刻是通过01选择变量刻画的，所以写法不太一样了，套路是每个资源每个时刻最多被一个资源所占用：

但是泊位这块儿只能告诉我们船舶i是什么时刻开始占用泊位b的，没办法知道船舶i在某个时刻是否占用泊位b，因此想要表达船舶i在某个时刻是否占用泊位b这个逻辑需要转换成“船舶i在开始占用泊位b的时刻t’属于哪个区间，会使得船舶i在时刻t仍然占用泊位b”。对于这个区间的分析见上图。至此，船舶i在时刻t是否占用泊位b就等价转换成了船舶i开始占用泊位的时刻t’是否处于某个区间的问题。

这种写法有什么弊端？资源的占用时长必须得是已知的，如果说资源占用时长是变量，这种写法是不是就不行了呢？

Part3：然后是集成类问题里面常见的资源使用时序关系约束，我觉得这篇文章的BIP模型写的不对：

  1. 进港船开始使用内锚地的时刻在进港船到达航道inner end的那个时刻之后，缺失相关约束
  2. 出港船开始使用内锚地的时刻在船舶完成装卸作业之后，缺失相关约束
  3. 船舶开始靠泊的时刻在船舶结束使用内锚地的那个时刻+船舶在内锚地和泊位之间航行时间之后，缺失相关约束

文中有的相关约束仅仅是限制“船舶对锚地占用的时长等于离开锚地的时刻减去进入锚地的时刻”，“离开锚地的时刻在进入锚地的时刻之前”，“虚拟锚地的占用时长为0”，这些约束并不能保证1，2，3得到满足吧？

Part4：最后是航行安全的刻画，船舶在航道的航行必须保证最低安全裕度、以及船舶宽度和航段宽度对船舶航行模式的影响。

他这个考虑起来实际上比较简单，因为船舶是同航速的，所以不用考虑追击问题。所以同航向船舶保持最低安全裕度只需要保证进入航道的时间间隔保持最低安全裕度就ok了。

这句话等价于这个时间段同向最多只有一个船舶进入航道。

作者文中定义了，从而上面俩约束可以简写成：

作者应该是在创建变量的时候就没有创建非法的变量，所以写约束的时候也得用复杂的集合运算把合法的变量给取出来。

实际上我觉得可以创建变量的时候把所有可能变量创建出来，然后非法取值变量通过约束强制为0就好了，更好理解，比如：

非法变量特别多的时候用他这种写法可能性能还是会更加好一些

船舶宽度和航段宽度对船舶航行模式的影响这个约束比较难想，要求任意一个航道的任意一个航段上，如果同时存在进港和出港船舶，那么进港船宽度加上出港船的宽度要小于航段的宽度。难点在于时刻t我怎么知道船舶是不是位于航段s，没有变量直接表明这一点，所以需要转换：（1）进港船时刻t位于航段s等价于进港船什么时候进港？（2）出港穿时刻t位于航段s等价于出港船什么时候出港？。

论文里面把定义成了，把定义成了。

MP模型咋推？

关于的说明

因为Colossus框架目前不支持方案集合分组的操作，只能引入Indicator parameter表征方案的服务对象。因此，下面得到的formulation和原文在形式上略有不同。

定价子问题咋转换成SSP？