题目：Containership routing with time deadlines and simultaneous deliveries and pick-ups
作者：Matthew G. Karlaftis, Konstantinos Kepaptsoglou, Evangelos Sambracos

摘要

In this paper we seek to determine optimal routes for a containership fleet performing pick-ups and deliveries between a hub and several spoke ports. A capacitated vehicle routing problem with pick-ups, deliveries and time deadlines is formulated and solved using a hybrid genetic algorithm for establishing routes for a dedicated containership fleet. Results on the performance of the algorithm and the feasibility of the approach show that a relatively small fleet of containerships could provide efficient services within deadlines. Moreover, through sensitivity analysis we discuss performance robustness and consistency of the developed algorithm under a variety of problem settings and parameters values.

批注：这篇文章研究的就是在考虑时间限制和simultaneous delivers and pick-ups（在一般的VRP问题里面一般只考虑在喂给卸货而不考虑装货，这里也考虑了在喂给港可能装货运到枢纽港的情形）的情况下如何为同质船队的单一枢纽港的轴辐式网络设计航线以最短时间完成整个网络上货物运输的需求。模型求解方面，用的是遗传算法，创新点在编码方式上，没有使用路径分隔符，而是通过一种启发式算法提取航线。

批注：Fig2是这篇文章的研究场景，位于希腊大陆的Piraeus港口（hub port）和周边25个岛屿港口（feeder port）之间存在货物往来，要为同质船舶设计一个轴辐式网络以最小化船队在整个网络上运行的时间。

背景部分

More specifically, while total inbound cargo to islands is significantly more than outbound cargo on an annual basis (islands are constantly supplied by the mainland), there are seasons when the amount of outgoing cargo (local island production of goods) is comparable to that of incoming cargo; this suggests the need for a seasonal redesign of routes (Sambracos, 2000). Therefore, a model considering both pick-ups and deliveries would be more appropriate and, as such, simultaneous pick-ups and deliveries are considered in this work.Furthermore, time deadlines must be considered, as containerships will carry perishable goods with strict expiration dates (fresh milk, vegetables and fish for example), whose delivery cannot be significantly delayed and, as such, it is necessary to have constraints for the latest delivery times. While other studies incorporate time windows (for example Fagerholt, 2001; Sigurt et al., 2005), because of port service requirements and capabilities (such as availability of berthing positions), we employ time deadlines; berthing capacity of smaller Greek island ports for freight vessels is rarely exceeded and therefore port services are – in practice – not affected by early arrivals. Moreover, early arrivals would even be desirable and welcomed by isolated island inhabitants.

批注：这里就是在解释为什么需要同时考虑pick-ups和delivers，岛屿港口在某些季节确实会大量往枢纽港运输货物，以及为什么考虑time deadline而不是time window，因为对于这些岛屿港口来说一般泊位都是用不满的，早到没有影响，但是晚到就会由影响（比如运输牛奶、鱼类这些perishable的货物）。

算法部分

The proposed GA has some distinct features: each generated string is evaluated by an external process ensuring that capacity constraints are exhausted but not violated in any case. On the other hand, time deadlines are considered as soft constraints, implying that delays are penalized even when a solution exists. Such an approach may lead to a minimum number of vessels operating at maximum capacity, but at the possible expense of relatively increased delays.

批注：用遗传算法去求解这样一个考虑时间限制和同时取送货（在容量约束中体现）的类似于VRP的问题的基本思路是——采用不带路径分隔符的顺序编码（由1~25构成，对于各个岛屿该港口）这样能够非常轻松的去使用传统的遗传算子，如顺序交叉算子和交换变异算子。但在使用适应度函数对个体进行评估的时候必须得把个体拆成若干个航线，这个提取航线的过程是通过一个启发式程序实现的，基本思想是——在充分利用船舶运力的情况下保证始终不超载。

批注：这个提取程序的思路如Fig1所示，假设船舶的capacity为50个集装箱，我们有一个染色体，对应港口的送量和取货量用表示，记route1为第一条航线。把1放入route1那么0港船舶载箱量满足要求；继续将2放入route1，那么0港船舶载箱量，1港载箱量满足要求；再将3放入route1，那么0港载箱量，1港载箱量，2港载箱量满足要求；再将4放入route1，那么0港载箱量，1港载箱量，2港载箱量，3港载箱量不满足要求。所以不能把4港放入route1，再检查把3港放入route1是否可行，3港载箱量可行，从而从染色体中成功提取出第一条航线route1=，对应航线。

The algorithm’s running time on a 2.53 GHz computer with 512 MB of RAM ranges from 2 to 4 min. Sambracos et al. (2004) provided results for a 48 island network employing a list-based threshold acceptance (LBTA) metaheuristic, in less than a minute but did not consider pick-ups and capacity constraints (it was assumed that when capacity was exceeded, a second ship would be used on the same route). Best results are obtained for the operator combination 101, with a population of 25, a crossover rate of 0.2 and a mutation rate of 0.01. For all combinations of GA operators, fitness function values do not differ significantly (about 5% at most) and in all cases, 5 ships are needed.