1 Introduction

The liner shipping industry is situated at the center of global trade, providing efficient and secure freight transportation on over 5000 seagoing vessels (United Nations Conference on Trade and Development (UNCTAD) 2015). Each year, more and more freight is transported with standardized steel containers in liner shipping networks. In 2015, over 171 million TEUFootnote 1 of freight was carried across the oceans, representing over 1.6 billion tons of goods (United Nations Conference on Trade and Development (UNCTAD) 2015).

Liner shipping differentiates itself from other forms of maritime transportation, such as tramp or industrial shipping, due to the periodic and cyclical nature of the routes in liner shipping networks. In liner shipping, these routes, called services, visit a sequence of ports within specified time windows on a periodic (usually weekly) basis. Once a vessel reaches the last port in the sequence, it travels to the first port in the sequence and starts again. As it may take more than a week to finish a round-trip, it is often necessary to deploy more than one vessel to fulfill the periodicity at the ports. The periodicity and reliability of liner shipping services have become key selling points, resulting in liner shipping services forming the backbone of many modern supply chains (Notteboom and Rodrigue 2008). However, the planning of efficient and reliable liner shipping services is challenging, as there are many sources of delay that can send a vessel off-schedule, which can have expensive repercussions throughout the supply chain (Notteboom 2006). Sources of delays for vessels include, for example, bad weather, port congestion, equipment breakdowns, labor disputes and medical emergencies. These can cause a vessel to be late for its weekly time window or even have to cancel its stop at a particular port. Moreover, it is not only important that vessels arrive at ports when scheduled, but that the shipped containers (demands) reach their destination in the time period that was guaranteed by the liner carriers, as arrival uncertainty causes extra costs in the supply chain (Vernimmen et al. 2007).

Due to the periodicity and cyclical nature of liner shipping services, there are interdependencies between the expected travel times of a service, the number of vessels assigned to a service, and the resulting reliability of a service. When designing services for their networks, liner carriers often add buffer time before each port call to reduce the effect of such delays and increase the reliability of schedules. The amount of buffer is usually determined based on the experience of planners or simple rules of thumb. Liner carriers often have no analytical basis in the historical data for each port for decision making, nor is the order of the service optimized to provide a certain amount of reliability. Analytical tools are missing that allow for an exploration of costs and reliability of liner shipping services considering the specific structure of the schedules and the complex trade-offs.

This paper focuses on the planning of a single service within a liner shipping network that explicitly incorporates uncertainty in travel times. The ports that should be visited and the berthing windows identifying when they should be visited are given as inputs for all models. In addition to optimizing the route a service takes to ports, we also consider the number of vessels necessary for running the service in conjunction with the planned speed of the vessels. Our models provide an arrival time service level to planners in a similar fashion to the service levels in Ehmke et al. (2015) for the well known vehicle routing problem with time windows, with one key difference. In Ehmke et al. (2015), lateness accumulates over the course of each vehicle’s tour. In the case of liner shipping service design, during the execution of a route, planners have a range of actions they can take to get a vessel back on schedule (see Brouer et al. 2013b). We do not explicitly model recourse actions in our tactical model, but assume that they can be taken to avoid propagation of lateness. However, we analyze the impact that propagation can have on the reliability of a service through simulation.

We present three mathematical models of increasing complexity for planning liner shipping services to understand how different features influence the results. To establish these models, we begin with a data-driven investigation into the distribution of travel times between different kinds of ports in liner shipping (see Sect. 3). This provides an analytical background for how we model uncertainty in liner shipping. In Sect. 4, we present the mathematical models and how they are able to accommodate the derived travel time distributions. In Sect. 4.1, we start with analyzing the impact of different service level guarantees on the arrival time at different ports on the design of cost-minimizing services, assuming the vessels plan to travel at their design speed. This helps us quantify the impact of modeling uncertainty. In Sect. 4.2, we expand the first model to explicitly consider the impact of varying speed levels on the number of required vessels and the resulting arrival time service levels. Contrasting the model of Sect. 4.1, we can now trade a smaller number of vessels for higher speeds in service execution or vice versa. In order to provide acceptable service levels with regard to port time windows, our first two models often create large buffers in the services’ schedules. Thus, they ignore delivery time guarantees on freight. Our third model, in Sect. 4.3, alleviates these limitations and helps us understand how different levels of delivery time guarantees can impact the amount of freight that can be carried when there are limitations on maximum container transit times.

In Sect. 5, we experiment with the use of the presented mathematical models in a series of computational experiments. To this end, we apply the presented travel time distributions to instances based on data from the well-known LINERLIB (Brouer et al. 2013a) and compute the optimal solutions for the different models. Considering different service levels through chance constraints in our optimization models, we analyze the trade-off between a larger fleet of vessels and adaptations of speed levels from a tactical network design perspective. Then, we assess the operational performance of these optimized services with a discrete-event simulation. The simulation evaluates the optimized services by imitating individual service runs to determine the “actual” realized cost and quality of a service, analysing the impact of propagation of lateness in the course of a round-trip. We provide a set of managerial insights based on these results in Sect. 6.

In summary, our paper provides the following contributions:

  1. 1.

    a data-driven investigation of distributions of travel time for liner shipping services,

  2. 2.

    the modeling of service guarantees on arrival times through chance constraints for service design,

  3. 3.

    a model for service routing optimization with variable vessel speed (tactical perspective),

  4. 4.

    and a simulation study to evaluate the effectiveness of the models (operational perspective) and the impact of lateness propragation when executing the services.

In the following section, we delineate our modeling approach from related literature in this field.

2 Literature review

The liner shipping service design problem with arrival time service levels has connections to a number of different problem domains, including the areas of vehicle routing, tramp shipping, and liner shipping. We now discuss the similarities and differences of this work with related work in the literature, referring to Christiansen et al. (2004, 2013) for an overview of the entire area of maritime transportation and Brouer et al. (2017) for an overview of liner shipping optimization. A bibliometric overview is given in Lau et al. (2017).

2.1 Liner shipping

We divide our discussion of related work within the area of liner shipping into two subsections. First, we discuss related problems such as network design and fleet deployment and then move into work addressing single service scheduling and routing. Given the prevalence of delays in maritime applications due to storms, labor disputes, and breakdowns, considering uncertainty is a natural extension to operations research models for tramp, industrial and liner shipping. Nonetheless, there is little literature considering stochastic elements in these problems.

2.1.1 Related liner shipping problems

Liner shipping single service design can be considered a subproblem of the overall network design problem and is considered a tactical problem in Meng et al. (2013). The network design problem is very difficult to solve with exact solution approaches (Agarwal and Ergun 2008; Álvarez 2009; Brouer et al. 2013a) and even for heuristics (Brouer et al. 2014). Due to its difficulty, network design problems usually leave out or abstract a number of important side constraints that we are able to include, such as the handling of container transit times. We note that to the best of our knowledge, there has not been any work on combining uncertainty with liner shipping network design models.

Fleet deployment models are also related (see, e.g., Powell and Perakis 1997), as these assign a heterogeneous fleet of vessels to a set of services. In contrast to these models, we do not try to size the vessel to the service we are designing. In our approach, the vessel class is an input parameter. Fleet deployment models are subject to different types of uncertainty than service/network design problems. A key source of uncertainty for these types of problems is the amount of demand that is shipped each week on each service. A chance-constrained model takes this into consideration in Meng and Wang (2010), finding a minimal cost allocation of vessels to services. We do not take demand uncertainty into account in our model, but this would be a logical extension of our work. Transit time restrictions for demands were recently considered in terms of the cargo allocation problem, which assigns containers to routes in a network in Guericke and Tierney (2015), as well as for a time-constrained multicommodity flow problem in Karsten et al. (2015). We solve a simplified version of this problem as a part of our single service design. We do not consider transshipments, making our cargo allocation easier in comparison.

2.1.2 Single service scheduling

Several papers determine vessel speeds and schedules for one (or more) service(s) under uncertainty given a pre-defined port sequence. The key difference between these works and our model is that we determine both the port sequence and the schedule. Delays at ports are considered in Qi and Song (2012), in which delayed arrivals are penalized in the objective function, reflecting a potential loss of goodwill. The authors discuss how to compute the service level at each customer, acknowledging that prior delays can accumulate. Furthermore, the paper focuses on special cases, such as with 100% service levels for all customers. A drawback of this work is that the authors do not use real data for their port time distributions, instead assuming uniform and normal distributions. In a parallel work, Wang and Meng (2012a), the authors also seek vessel speeds and a schedule under uncertainty for a new liner shipping service. They create a mixed-integer non-linear stochastic programming model for the problem that minimizes ship and fuel costs while maintaining a given service level. The problem is solved using a cutting-plane algorithm.

The most relevant work in the area of liner shipping in terms of focusing on delays is Lee et al. (2015). The paper assumes the routes are given and looks at the impact of different steaming speeds for executing the route, given the stochastic nature of port operations. Buffers are planned into liner shipping schedules in order to maintain a specified arrival service level. In contrast, not only do we perform route planning, we also do not limit ourselves to only considering port delay. While port delays make up a large percentage of the sources of delay (Notteboom 2006), a number of other sources exist that we are able to account for in our model.

A feeder network design problem is presented in Santini et al. (2017) that routes and schedules several services within a geographically limited area. The authors use an expanded time space graph so that vessel speeds can be precomputed and assigned as costs directly to the arcs. The number of vessels used on the routes if fixed to a value K, meaning the set of speeds for vessels and amount of buffer that can be inserted into the schedule, is limited. Thus, Santini et al. (2017) does not consider arrival time service levels.

The paper that motivates the basic form of our model is Plum et al. (2014). The goal in this work is to design a single service given a set of ports that must be visited. A set of container demands between ports must be satisfied while taking into account the capacity restrictions of the vessels. Our first deterministic model (Phase 1) resembles this work very closely, adding only the optimization of the number of ships on the service. Furthermore, our models extend the work of Plum et al. (2014) with variable vessel speed and arrival time guarantees, which represent important characteristics for the liner shipping industry. A summary of the features of our models in relation to the literature is given in Table 1.

Table 1 A categorization of related work within the area of liner shipping service/schedule design
Full size table

2.2 Handling delays in related routing problems

There are several related problems in which delays have been considered. Ehmke et al. (2015) is among the most recent; they explicitly consider the interplay of stochastic travel times and time windows in the vehicle routing problem, ensuring service levels in routing through chance constraints. For them, the largest challenge stems from the computation of the combined arrival time distribution along a route, which we ignore in our approach since we assume statistical independence between the individual sequences on a route.

Tramp and industrial shipping involve the transportation of bulk or liquefied goods (but rarely containers) in a vehicle routing-like fashion. Tramp/industrial shipping problems differ greatly from liner shipping problems in terms of the schedule structure. Whereas liner shipping has a periodic, fixed schedule like a public bus network, tramp/industrial shipping more resembles taxis, in which ships sail wherever there is a demand to be satisfied. However, despite their differences, all of these types of shipping involve vessels that can be delayed in the same way, as well as have similar cost profiles for sailing. Speed optimization has become a standard feature of tramp shipping models (Norstad et al. 2011).

The most recent work in this area is Agra et al. (2015), which considers a maritime inventory routing problem for liquefied natural gas with stochastic sailing and port times. The authors determine routes and the quantity of gas to load/unload a priori and model the problem as a stochastic program with recourse using scenarios. In contrast, we compute distributions over the arrival times of vessels at ports. In Agra et al. (2016), this work is extended to use a log-logistic distribution to model delays as in our work. Uncertain sailing times are considered in Halvorsen-Weare and Fagerholt (2013), motivated by a real energy company, as well as uncertain production rates for a natural gas provider. In Halvorsen-Weare et al. (2013), the same problem is solved as in Halvorsen-Weare and Fagerholt (2013), but with robustness strategies added. The sailing times are fitted to a log-logistic probability distribution, based on information gathered for a gas tanker in Kauczynski (1994).

A method for creating replenishment schedules for offshore installations is proposed in Halvorsen-Weare and Fagerholt (2011). The paper defines four weather states and their impact on sailing speed and service time in ports at an offshore delivery location. A key difference with our work is that the authors assume a set of routes already exist, and they must choose which routes to use.

3 Data exploration

A key challenge that arises in guaranteeing arrival time service levels for a liner shipping service is determining what distribution underlies the travel time of the vessels. As discussed in the previous section, the maritime literature has several suggestions on appropriate travel time distributions, including the log-logistic distribution (Halvorsen-Weare et al. 2013). However, it is not clear a priori that this distribution is the best fit for travel times of liner shipping services, and furthermore, it is not clear that this distribution is appropriate for trips between all ports worldwide. To this end, we gathered data from operating liner shipping service routes, including profiles of the vessels used and the actual transit times of the vessels between ports. We first describe the data we use for distribution fitting in more detail, including a frank discussion of the strengths and weaknesses of our dataset, and finish with a presentation of the distributions we found.

3.1 Data sources and integration

We have taken care to make our dataset as realistic as possible. To do this, we use service information from the liner carrier COSCO and combine this with AIS (positioning) data from MarineTraffic regarding the vessels on 25 selected liner shipping services. We note that we have no relationship with COSCO and use data regarding their network because they offer detailed arrival time information for their services. We gathered positioning data from the vessels’ transponders for the year 2014 and use this data to check whether the vessels are on time or not by comparing it with the planned schedule from COSCO (COSCO Shipping Lines 2017). In total, our dataset contains 40 ports, 118 vessels, 125 port to port connections, and records for 1872 transits between ports. This provides us with a list of transits between the ports visited by the 25 services and an indication of how late (or early) the vessel was as compared to the planned travel time.

Figure 1 shows three sample transits and their associated histograms, chosen because they represent a range of connection types: an intra-region connection (a), a Pacific Ocean connection (b) and an Indian Ocean connection (c). While it is not possible to generalize from the data of only a few connections, it is clear that even on short connections, such as crossing the English channel, significant delays above the scheduled sailing time are possible. Furthermore, we can see that some schedules are planned with enough buffer that even delays of a couple of days do not cause lateness, as in the case of the backhaul from Long Beach to Ningbo. Finally, some schedules are tightly planned, as in the case of sailing from Singapore to the southern side of the Suez canal. Here, significant delays of up to almost five days can occur. We note that it is not unusual for connections to be assigned a speed faster than the vessel’s design speed as in Fig. 1a, c. These are likely connections where shippers wish to have fast transit times and the carrier must meet these requests to carry shipper’s cargo.

Fig. 1
figure 1

Histograms of travel times (in hours) of several port to port pairs. The x-axis shows the varying travel times in hours between the ports. The y-axis gives the frequency of a particular travel time. The scheduled transit time is shown with a dashed red line and the travel time at the vessel’s design speed with a solid magenta line. a Rotterdam, NL to Le Havre, FR, b Long Beach, US to Ningbo, CN, c Singapore, SG to Suez, EG

Full size image

The data we use from the AIS transponders is the best data we can obtain, as carriers we have spoken to do not keep track of more accurate statistics regarding travel time. There are, however, weaknesses that we want to outline. An obvious issue is that we do not know what recourse actions were taken to avoid or reduce lateness during operations. In particular, if a vessel is running late, a carrier may instruct the captain to speed up to stay on schedule. We note that AIS data does include the speed of the vessel, but even with the speed, we cannot assess whether a speed-up was part of the original service schedule or not. Another source of error in our data is that extremely late vessels may simply skip port calls to save time, meaning we do not end up knowing how late they actually were. Furthermore, if no vessel performs a particular port to port transit, we will have no data for it, and this makes it difficult to know what distribution to use to model travel time for such a connection when considering the creation of a new service. We attempt to counteract some of the weaknesses in our approach by clustering the port to port connections and by computing distributions between regions rather than individual ports. This alleviates the problem for many connections.

3.2 Distribution fitting

We compute distributions based on intra and inter-region transit times, normalized according to the average travel time for each region-to-region pair. To create distributions for any pair of ports worldwide, we aggregate and generalize the operational data as follows. First, to generalize the port-to-port observations, we follow a common idea in the network design literature (e.g. Mulder and Dekker 2014) and cluster ports into 16 regions with the well known k-means algorithm, adjusting the ports between some regions slightly by hand. The resulting clusters provide the input for our distribution fitting. Second, between two regions or within a single region, for each pair of ports, we normalize the travel times based on the mean empirical travel time between (or within) the regions containing the ports. That is, given ports i and j from regions r and s, we compute the average travel time between the regions and divide the travel time between i and j by this value. Since not every pair of regions has sufficient data to allow for an empirical fit of a distribution, we also compute a distribution across all data that can be used for such port pairs.

We use the software EasyFit (MathWave Technologies 2016) to generate a list of distributions for each inter and intra region pair to narrow down the type of distribution to use across our data. In 17 out of 28 pairs with enough port to port transfers to fit a distribution, the three-parameter log-logistic (ll3p) distribution is one of the top three best fitting distributions, and in all other cases was still one of the best fitting distributions. Other good fits included the Cauchy distribution and the four-parameter Burr distribution. Given the previous use of the ll3p distribution in the literature, we select it for the remainder of this work.

Figure 2 shows histograms and the best fitting normal and log-logistic probability distribution functions for several region-to-region pairs. The x-axis provides the normalized travel time, with the y-axis reflecting the frequency of a particular value. There is a clear trend across all of the regions we consider. The normal distribution has less probability mass than the ll3p distribution around on-time transits at time 0, which is a good indicator of why the log-logistic distribution is often the one with the best fit. In many cases, the log-logistic distribution puts more mass near on-time arrivals and is skewed to the right, reflecting a large number of vessels arrive late and across a wide range of values. For a few region-to-region pairs, the log-logistic distribution looks almost like the normal distribution, as is the case in Fig. 2b, and this further emphasizes the importance of fitting specific parameters for different parts of the world, instead of only one set of parameters.

Fig. 2
figure 2

Histogram and probability distribution functions for several region-to-region pairs. Blue bars show the histogram, a solid red line shows the fit of the ll3p distribution, and the dashed green line the fit of a normal distribution. a Intra Europe, b China/Japan to Southern Mediterranean, c Intra Western North America, d Western North America to China/Japan, e Central/South America to North America, f Indian Ocean to Southern Mediterranean

Full size image

4 Mathematical models

We construct an arc flow model that extends the one presented in Plum et al. (2014) to find a cyclical route through ports given fixed port time windows. We decompose the modeling of the extended problem into three phases, each one with added complexity. This helps us understand the impact of different problem features and also their impact on the solution time. Unlike in Plum et al. (2014), all of our models contain chance constraints requiring vessels arrive at ports on-time with a specified arrival time service level. In the first phase, we address the basic liner shipping service design problem, requiring all demand to be transported without the maximum transit times on vessels sailing at their design speeds used in Plum et al. (2014). The design speed is used to provide schedules that can serve as a reasonable baseline for Phase 2 and Phase 3. In the second phase, we relax the fixed sailing speed requirement and allow the vessel to vary its speed, taking this into account in the objective function. In the third phase, we impose maximum container transit times, but allow demand to be rejected if it is not possible to meet the transit time limitations. The objective function in this phase switches to profit maximization from cost minimization in Phases 1 and 2. As mentioned in Sect. 1, our models do not consider propagation of lateness over the course of the service. This is because route planners have a range of actions they can take to get a vessel back on schedule (see Brouer et al. 2013b) if needed, including skipping ports, negotiating new time windows, etc. We do not explicitly model these recourse actions in our tactical model, because we do not know which ones could be negotiated in each case. We assume, though, that such actions can be taken to avoid propagation of lateness, but also create expenses that a company would want to avoid if possible through on-time arrivals.

4.1 Phase 1: design speed model

In Phase 1, we impose the following assumptions:

  1. 1.

    All ports are assigned a fixed port time window per week in which they are called. The vessel must arrive before the port time window starts (planned arrival) and may not leave until the window ends (planned departure).

  2. 2.

    Vessels must wait until the start of their time window if they arrive early at a port.

  3. 3.

    Time windows must be satisfied with a confidence level of \(\alpha \) (arrival time service level). For example, \(\alpha \) may be a value such as 75% or 90%.

  4. 4.

    Travel times between ports are statistically independent.

  5. 5.

    All vessels must plan on traveling at their design speed between ports.

  6. 6.

    All pickups and deliveries of demand must be served, assuming that the vessel capacities are sufficiently large.

  7. 7.

    Forty foot containers are broken down into two twenty foot containers, and their flow can be modeled in a continuous fashion.

  8. 8.

    All ports must be called exactly once.

  9. 9.

    The objective is to minimize the cost of the single route and the number of vessels required.

  10. 10.

    The service frequency is weekly.

Note that the requirement that all ports must be called exactly once means we cannot design butterfly or conveyor belt style routes. We note our model can be adjusted to create such routes and in its current form can support having a port specified multiple times. According to Song and Dong (2013), cycle routes (i.e., those where all ports are visited once) are the most common topological structure and can be found in about 45% of services. We assume that one of the ports is arbitrarily identified as the start port for the service, and it is also the end port since the route is cyclical. The starting port is assumed, without loss of generality, to be a port that has a time window that is fully contained during the week, i.e., the time window does not intersect with Monday at 12:00 AM. We further note that delays have some correlation with the amount of loaded cargo (Hasheminia and Jiang 2017) and we do not take this into account in this model.

We now define the mixed-integer linear program for the Phase 1 model.

Parameters

\(P= \{1,\dots ,p, p+1\}\) :

Set of ports to call; ports 1 and \(p+1\) represent the initial port (and its return)

\(A\) :

Set of arcs (i, j); we assume that the network is complete, with no arcs into the initial port or out of the ending port

\(A'\) :

All of the arcs of \(A\) with the addition of a single arc connecting the ending port to the initial port

\(K\) :

Set of demands

\(o_{k}\) :

Origin of demand \(k \in K\)

\(d_{k}\) :

Destination of demand \(k \in K\)

\(a_{k}\) :

Amount of cargo of demand \(k \in K\)

\(u\) :

Capacity of a vessel in TEU

\(t^s_i, t^e_i\) :

Time window start and end (respectively) within a week for port \(i \in P\), where time 0 is Monday at 12:00 AM. The values for the time window start and end time represent hours. The latest arrival time has a domain \(t^s_i \in \{0, \dots , 167\}\), whereas the earliest departure time \(t^e_i \in \{t^s_i, \dots , 335\}\). This allows port time windows to start and end in consecutive weeks.

\(c^f_{ij}\) :

Fixed sailing cost for arc \((i,j) \in A\)

\(t^{\alpha }_{ij}\) :

Time for sailing arc \((i,j) \in A\) at the vessel’s design speed to provide a service level of \(\alpha \)

\(c^v\) :

Charter cost per vessel per week

Variables

\(w_{i}\) :

Service week at port \(i \in P\), where \(w_1=0\)

\(x_{i j}\) :

Indicates whether arc \((i,j) \in A\) is included in the service

\(\tau ^s_{i}\) :

Start service time of a vessel at port \(i \in P\) (hours from beginning of service)

\(\tau ^e_{i}\) :

End service time of a vessel at port \(i \in P\) (hours from beginning of service)

\(\tau ^a_{i}\) :

Arrival time at port \(i \in P\) (hours from beginning of service)

\(f_{k i j}\) :

Flow of demand \(k \in K\) on arc \((i, j) \in A\)

Objective and constraints

$$\begin{aligned} \min \; c^vw_{p+1} + \sum _{(i,j) \in A} c^f_{i j} x_{i j} \end{aligned}$$
(1)
$$\begin{aligned} {\hbox {subject to}}\,\sum _{(i,j) \in A} x_{i j} = 1 \quad \forall j \in P{\setminus } \{1\} \end{aligned}$$
(2)
$$\begin{aligned} \sum _{(i,j) \in A} x_{i j} = 1 \quad \forall i \in P{\setminus } \{p+1\} \end{aligned}$$
(3)
$$\begin{aligned} \tau ^s_i = t^s_i + 168 w_i \quad \forall i \in P \end{aligned}$$
(4)
$$\begin{aligned} \tau ^e_i = t^e_i + 168 w_i \quad \forall i \in P \end{aligned}$$
(5)
$$\begin{aligned} \tau ^a_i \le \tau ^s_i \quad \forall i \in P \end{aligned}$$
(6)
$$\begin{aligned} \tau ^e_i + t^{\alpha }_{i j} \le \tau ^a_j + M(1 - x_{i j}) \quad \forall (i,j) \in A \end{aligned}$$
(7)
$$\begin{aligned} w_1=0&\end{aligned}$$
(8)
$$\begin{aligned} \sum _{j \in P{\setminus } \{ o_k\}} f_{k o_k j} = a_k \quad \forall k \in K \end{aligned}$$
(9)
$$\begin{aligned} \sum _{j \in P{\setminus } \{ d_k \}} f_{k j d_k } = a_k \quad \forall k \in K \end{aligned}$$
(10)
$$\begin{aligned} \sum _{(j,i) \in A'} f_{k j i}=\sum _{(i,j)\in A'} f_{k i j} \quad \forall k \in K, i \in P{\setminus } \{o_{k}, d_{k}\} \end{aligned}$$
(11)
$$\begin{aligned} \sum _{k \in K} f_{k i j} \le ux_{i j}\quad \forall (i,j) \in A' \end{aligned}$$
(12)
$$\begin{aligned} x_{p+1, 1} = 1 \end{aligned}$$
(13)
$$\begin{aligned} x_{ij} \in \{0,1\} \quad \forall (i,j)\in A' \end{aligned}$$
(14)
$$\begin{aligned} \tau ^a_i, \tau ^s_i, \tau ^e_i \ge 0 \quad \forall i \in P \end{aligned}$$
(15)
$$\begin{aligned} f_{k i j} \ge 0 \quad \forall (i,j) \in A', k \in K \end{aligned}$$
(16)
$$\begin{aligned} w_i \in {\mathbb {Z}}^{+} \quad \forall i \in P{\setminus } \{1\} \end{aligned}$$
(17)

The objective function (1) includes the cost for vessels and the sailing cost for the complete service. The variable \(w_{p+1}\) contains the week of the last port visit. Since we are assuming a weekly service frequency, the last week also specifies the number of vessels. Constraints (2) and (3) require that the service enters and leaves each port exactly once, except for the initial and ending port. The time the vessel starts and ends its visit at each port is determined in Constraints (4) and (5). The term \(168w_i\) converts the week selected for customer i to the appropriate hour from the start of service. Constraints (6) restrict the arrival time to be before the start of the visit at a port.

We use a chance constraint to ensure that the service route has enough buffer at each port to achieve the level of punctuality requested. Constraints (7) model a general constraint that can be used with any probability distribution in which the inverse CDF can be computed. These constraints force the arrival time at the next port to always be greater than the departure time at the previous port plus the travel time with an adequate buffer. We compute a bound for M as follows. First, we compute a maximum path length (worst case tour) traveling salesman problem (TSP) through all of the ports.Footnote 2 Given this “slow” TSP path, we then add extra buffer based on our service level formulas to the path if required to reach a particular service level, and further add buffer that considers when the vessel arrives at a port and how long it must wait until the port is available.

To compute the value of \(t^{\alpha }_{ij}\), consider, for example, the case of the normal distribution where we want to guarantee a confidence level of \(\alpha \) that we arrive on time. Assume we have a parameter \(z^\alpha \) that provides the number of standard deviations associated with a service level of \(\alpha \). We can then set \(t^{\alpha }_{i j}\) to be the mean travel time between i and j plus \(z^\alpha \) times the standard deviation. Consider now the case of a non-normal distribution such as the three-parameter log-logistic distribution. Given the scale parameter \(\sigma \), shape parameter \(\xi \) and location parameter \(\mu \), we want to find the value of \(t^{\alpha }_{i j}\) providing the minimum required travel time between i and j enabling a service level \(\alpha \). We can compute this from the inverse CDF as follows:

$$\begin{aligned} F^{-1}(\alpha ; \sigma , \xi , \mu ) = \left( \frac{1}{\alpha } - 1\right) ^{-1/\sigma } \left( \xi + \mu \left( \frac{1}{\alpha } - 1\right) ^{1/\sigma } \right) . \end{aligned}$$

If we are interested in comparing the results with a deterministic model, as we do in our experiments, we can simply set \(t^{\alpha }_{i j}\) to a fixed value \(t_{ij}\) representing the travel time at the design speed with no added buffer.

The visit to the initial port is specified to be in the initial week by Constraints (8). Constraints (9), (10), and (11) are used to handle the flow of demands between their supply and destination points as well as between transhipment points. These are modeled in a similar way to Plum et al. (2014), but adapted to require that all demand is served. The capacity of the vessel is enforced by Constraints (12) on each arc, but only if a vessel is sailing on the arc. Should an arc not be used in the vessel path, the flow capacity is set to zero. Constraint (13) connects the last port to the first port, ensuring that the service’s route is complete. Lastly, Constraints (14), (15), (16), and (17) define the variables appropriately.

4.2 Phase 2: optimized speed model

While the Phase 1 model covers a number of basic properties of liner shipping service design, in practice, planners can adjust the speed of the vessels to reduce sailing costs or increase the probability of meeting tight deadlines. Hence, we adjust the fourth assumption to the following:

  1. 4.

    Vessels may sail between their minimum and maximum speed, and the cost of doing so will be reflected in the objective function.

We implement variable vessel speeds with several new sets of variables and parameters. Since the distance between all ports is known in advance, the model can simply decide the sailing duration for each leg of the service and the speed is known (duration/distance). The duration is used in a piecewise linearization to determine the approximate bunker costs. Three new sets of variables are required:

\(\gamma _{i j}\) :

The cost of sailing between i and j for arc \((i,j) \in A\)

\(\rho _{ij}\) :

The duration for sailing between ports i and j for arc \((i,j) \in A\)

\(\beta ^{\alpha }_{i j}\) :

The amount of buffer added into the schedule between ports i and j for arc \((i,j) \in A\) to enforce a service level \(\alpha \)

We also need to add further parameters:

\(\delta \) :

The speed of a vessel

\(\delta ^*\) :

The design speed of a vessel

\(c^B\) :

Cost per ton of bunker fuel

\(\phi ^{g}_{ij}\) :

Slope of secant g of the bunker consumption cost function approximation for arc \((i,j) \in A\)

\(\omega ^{g}_{ij}\) :

y-intercept of secant g of the bunker consumption cost function approximation for arc \((i,j) \in A\)

\(t_{i j}\) :

The sailing time at the vessel’s design speed between i and j for arc \((i,j) \in A\)

\(t^{ Min }_{ij}, t^{ Max }_{ij}\) :

The minimum or maximum sailing time between i and j for arc \((i,j) \in A\)

Since the fuel consumption function of vessels is roughly cubic (Brouer et al. 2013a), we use a piecewise linearization of the function in our Phase 2 model. One approximation for the non-linear bunker consumption function (Brouer et al. 2013a) is given by

$$\begin{aligned} B(\delta ) = \left( \frac{\delta }{\delta ^*}\right) ^3 B(\delta ^*), \end{aligned}$$

where \(\delta \) is the vessel’s speed, \(\delta ^*\) is the vessel’s design speed and \(B(\delta ^*)\) is the bunker consumption in tons of fuel per hour at the design speed. We use the secant approximation presented in Reinhardt et al. (2016) to linearize this function and note that, due to the convexity of the function, no binary variables are necessary. We now show their approximation, adjusting the notation to fit our model. First, we modify the bunker consumption function to accept a travel duration between two ports with

$$\begin{aligned} {\hat{B}}(\rho _{ij}) = \left( \frac{t_{i j}}{\rho _{ij}}\right) ^3 B(\delta ^*) c^B, \end{aligned}$$

where \(\rho _{ij}\) is the travel duration, \(t_{i j}\) is the sailing time at the vessel’s design speed as previously defined, and \(c^B\) is the cost per ton of bunker fuel. This function can be approximated with a given number of secants, \(\theta \). Each secant \(g\) is defined with the function

$$\begin{aligned} {\hat{c}}_{ij}(\rho _{ij}) = \phi ^{g}_{ij} \rho _{ij} + \omega ^{g}_{ij}, \end{aligned}$$

where \(\phi ^{g}_{ij}\) is the slope of the secant and \(\omega ^{g}_{ij}\) is the y-intercept. Then, we can add the following linear constraints to our model for computing the sailing cost:

$$\begin{aligned} \gamma _{i j} \ge \phi ^{g}_{ij} \rho _{ij} + \omega ^{g}_{ij} x_{ij} \qquad \forall (i,j) \in A, 0 \le g < \theta . \end{aligned}$$
(18)

Since the variables \(x_{ij}\) indicate whether an arc is being used or not, we ensure that the sailing costs on the arc are only constrained when the arc is being used. Furthermore, we replace the objective function (1) with the following:

$$\begin{aligned} \min \; c^vw_{p+1} + \sum _{(i,j) \in A} \gamma _{ij} . \end{aligned}$$
(19)

To handle the arrival time service levels with varying speeds, we modify Constraints (7) to include the decision variable \(\rho _{ij}\):

$$\begin{aligned} \tau ^e_i + \rho _{ij} + \beta ^{\alpha }_{i j} \le \tau ^a_j + M(1 - x_{i j}) \qquad \forall (i,j) \in A. \end{aligned}$$
(20)

In other words, the travel time from Phase 1 is replaced with the variable specifying the travel duration on the arc, if the arc is used. We then require constraints ensuring that the minimum duration according to the chosen service level \(\beta ^{\alpha }_{i j}\) is enforced:

$$\begin{aligned} \rho _{ij} + \beta ^{\alpha }_{i j} \ge t^{\alpha }_{i j} x_{i j} \qquad \forall (i,j) \in A. \end{aligned}$$
(21)

For a deterministic model, the term \(\beta ^{\alpha }_{i j}\) can be set to zero. We then constrain the minimum and maximum duration of the voyage using the parameters \(t^{ Min }_{i j}\) and \(t^{ Max }_{i j}\) with the following constraint:

$$\begin{aligned} t^{ Min }_{ij} x_{i j} \le \rho _{i j} \le t^{ Max }_{ij} x_{i j} \qquad \forall (i,j) \in A. \end{aligned}$$
(22)

These constraints ensure that vessels do not sail faster or slower than is allowed should the arc be chosen. Finally, we impose bounds on the travel time, travel costs, and buffer variables:

$$\begin{aligned} \rho _{i j} \ge 0, \gamma _{i j} \ge 0, \beta ^{\alpha }_{i j} \ge 0 \qquad \forall (i,j) \in A. \end{aligned}$$
(23)

4.3 Phase 3: optimized speed with maximum transit times model

For our Phase 3 model, we require that demands are not carried for longer than their maximum transit time. Requiring that all demand be served in combination with transit times limitations can lead to infeasibility, especially when a high level of on-time arrival is desired. A further assumption of our Phase 3 model is that the demands at a port are the same each week. This is, of course, not the case in practice, but it is sufficient for tactical level planning. In Phase 1 and 2, we wanted to see the impact of service levels and speed optimization on serving the same demands, so we relaxed this transit time requirement. Here, to enforce the maximum transit times, we will relax the fifth assumption of Phase 1, namely that all demands must be carried. We now have the following assumptions in addition to the Phase 2 assumptions (minus assumption 5 from Phase 1):

  1. 10.

    All demands have a maximum transit time. This is a common assumption in practice.

  2. 11.

    Demands can be rejected if their maximum transit times cannot be met.

  3. 12.

    The objective is to maximize the profit, i.e. the revenue from carrying cargo minus the cost of sailing and cost of vessels.

These changes require two new variables:

\(y_k\) :

This equals 1 if demand k is transported or 0 if it is not transported for \(k \in K\)

\(\delta _k\) :

This equals 0 when the service start time of the destination is greater than the end service time of the cargo source for demand k for \(k \in K\). However, due to the cyclical structure of liner shipping routes, it is possible that the start service time of the destination is actually less than the end service time of the source if the path of the cargo crosses the (arbitrary) “end” of the service. When this occurs, this variable will be 1.

We also need to add further parameters:

\(r_k\) :

The revenue of delivering a demand k

\(l_k\) :

The maximum transit time of a demand k

For our new profit maximizing objective, we add the revenue of delivering a demand, \(r_k\), to the objective function, and subtract the vessel and sailing costs from it:

$$\begin{aligned} \max \; \sum _{k \in K} r_k y_k - c^vw_{p+1} - \sum _{(i,j) \in A} \gamma _{ij}. \end{aligned}$$
(24)

We next replace Constraints (9) and (10), which control the start and end of the flow of demand k, with the following:

$$\begin{aligned} \sum _{j \in P{\setminus } \{o_{k}\}} f_{k o_{k} j} = a_{k} y_k \qquad&\forall k \in K \end{aligned}$$
(25)
$$\begin{aligned} \sum _{j \in P{\setminus } \{d_{k}\}} f_{k j d_{k}} = a_{k} y_k \qquad&\forall k \in K. \end{aligned}$$
(26)

Constraints (25) and (26) set the amount of containers to be carried for a particular demand to 0 when \(y_k\) is 0, ensuring that the demand is either taken in its entirety or not at all.

Given the maximum transit time of a demand k, \(l_k\), we use the following constraints to restrict the transit time:

$$\begin{aligned} \tau ^s_{d_{k}} \ge \tau ^e_{o_{k}} - M \delta _k \quad \forall k \in K \end{aligned}$$
(27)
$$\begin{aligned} \tau ^s_{o_{k}} \ge \tau ^e_{d_{k}} - M (1-\delta _k) \quad \forall k \in K \end{aligned}$$
(28)
$$\begin{aligned} \tau ^s_{d_{k}} - \tau ^e_{o_{k}} \le l_k + M\delta _k + M(1 - y_k) \quad \forall k \in K \end{aligned}$$
(29)
$$\begin{aligned} \tau ^s_{d_{k}} - \tau ^e_{o_{k}} + 168w_{p+1} \le l_k + M(1 - \delta _k) + M(1 - y_k) \quad \forall k \in K \end{aligned}$$
(30)

Constraints (27) and (28) set the value of \(\delta _k\) depending on the schedule of the vessel. When \(\delta _k = 0\) (the “normal” case), the destination of demand k is scheduled later than the origin. However, when \(\delta _k = 1\), the destination comes after the “end” of the service, meaning the scheduled time of the origin is actually later than the destination in the model. Constraints (29) and (30) set the transit time limitation depending on the value of \(\delta _k\). We then add one more set of constraints to the model to connect the flow of each demand to its corresponding 0/1 variable:

$$\begin{aligned} f_{k i j} \le a_k y_k \qquad \forall k \in K, (i,j) \in A. \end{aligned}$$
(31)

Finally, we add bounds constraints for the new variables:

$$\begin{aligned}&y_k \in \{0,1\} \qquad \forall k \in K\end{aligned}$$
(32)
$$\begin{aligned}&\delta _k \in \{0,1\} \qquad \forall k \in K. \end{aligned}$$
(33)

5 Computational experiments

We will first describe how we create our instances and experimental design in Sect. 5.1. For our Phase 1 and 2 models, we simulate operations of the created schedules to evaluate their performance with regard to cost and service quality. We describe our simulation in Sect. 5.2. Then, we present our results of tactical planning for the three models in Sect. 5.3. Finally in Sect. 5.4, we present sample schedules generated by our different models.

5.1 Instances

For our experiments, we want to compare the results from deterministic and stochastic variants (with different service levels) of each model across a variety of instances. This will help us understand the impact of different service levels, the ability to optimize speed in the planning phase, and the impact of the maximum transit times. We also want to understand how the underlying features of the created services, such as the locations of the ports being considered, impact the results.

The instances are constructed using real demand data and vessel information from the LINERLIB (Brouer et al. 2013a), which we combine with empirical travel time distributions constructed from COSCO liner shipping services (as discussed in Sect. 3). We build 44 instances based on 22 existing COSCO services as follows. For each COSCO service, we make a “standard” instance and a “tight” instance using the service’s port calls. The standard instance matches the time windows from the COSCO data, while the tight instance modifies the time windows to provide a schedule with time windows as close together as possible. That is, all buffer between ports i and j in the service’s port sequence is removed such that a vessel would have to sail at maximum speed to be on time. However, we are only able to remove buffer time up to a certain point, because the sum of all travel and port times has to be divisible by the number of hours in a week. We therefore remove all buffers between all port calls except for the return trip of the vessel to the origin port. For each instance, we extract relevant demands from the LINERLIB, including the amount of containers and the maximum transit time. For Phase 3, we also create a “relaxed” version that allows the cargo to be delivered up to 1.5 times later than the original transit time. This creates a total of 88 instances for Phase 3.

Since the LINERLIB data has been designed for the liner shipping network design problem, i.e., for problems that may contain several services, it is not perfectly suited towards single service design. This is because a significant amount of cargo is transported through hubs rather than along direct routes. To ensure our instances have a realistic amount of cargo, we aggregate ports into 25 clusters (similar to the aggregation performed in Mulder and Dekker 2014). We then assume each of those clusters has some feeder services that will carry cargo to and from ports on the service we are designing. In some cases, especially with cargo originating from Asia, this can result in too much demand for any vessel to carry. We then randomly reduce the size of the demands. We subtract the amount of time required to carry the cargo to the hub from the transit time limit, along with three days for transshipment as done in Guericke and Tierney (2015).

An overview of our instancesFootnote 3 is given in Table 2. The service name corresponds to the COSCO service name. Note that our services in some cases do not exactly correspond with the original services since we remove duplicate port calls. In addition to the number of ports and port-to-port demands, we compute the minimum number of vessels necessary to sail on the service using the original schedule and provide the number of vessels the carrier assigned to each service. The vessel type dictates the design speed, the minimum and maximum speed, as well as the (fixed) bunker costs in tons per day at design speed (which we get from LINERLIB). For vessels of the Post Panamax and Super Panamax classes, these values are as follows: design speed 16.5/17.0 knots, minimum speed 12 knots, maximum speed 23/22 knots, bunker costs 82.2/126.9 tons/day. We also assume a fuel price of \(\$ 400\) per ton.

Table 2 Instance properties for the instances tested in this work. We note that on psw5, the vessels from the carrier are slightly faster than the vessel we use from the LINERLIB, hence one less vessel is required
Full size table

We solve all instances with Gurobi version 7.0.2 (Gurobi Optimization 2015) on eight Intel Xeon E5506 CPUs at 2.13 GHz with a maximum runtime of 24 h. For each instance, we solve all of the models in Sect. 4. We experiment with modeling the underlying travel time data as a normal distribution and as an ll3p distribution we identified to be a better fit. We experiment with both to see if modeling travel time data with a normal distribution, which is easy to use and fit, offers a similar quality performance as the more accurate distribution. For both distributions, we experiment with service levels of 70 and 90%, and, for the ll3p distribution, also for a service level of 95% because of its long tail. We also test a deterministic version with no added buffer. This yields 8 runs for each instance and for each model. The output of each run is an optimized schedule that contains the ordering of ports of a service (a service design), the associated number of vessels that minimize the particular objective, the optimized objective value, and the scheduled arrival and departure times at ports. In Phase 2 and Phase 3, the optimized speed level between each pair of ports is also reported. We note that Gurobi is able to solve most of our models in relatively little CPU time, although some are not solved after 24 h. A detailed look at the runtime is provided in the “Runtime” section of the Appendix.

5.2 Simulation

For each service that is created by Phase 1 and 2 models, we simulate the resulting schedule to evaluate the impact of the varying service levels on “actual” costs and reliability, imitating operations of individual service runs. The purpose of the simulation is to analyze the impact of the stochastic travel time information and the possibility of adapting speeds to fulfill service levels in liner shipping network design. From a tactical perspective, the optimization models can create liner shipping services considering uncertainty through chance constraints as presented in Sect. 4. From an operational perspective, the simulation now tries to realize the optimal plans from the tactical level. We imitate that by drawing random travel times as an input for the realization of a service. We let the simulation react with speed adaptation according to the same degrees of freedom and cost parameters as our mathematical models, which causes differences to the planned speeds and to the planned variable sailing costs. Then, we can directly compare the planned costs (from optimization) with the “actual” realized costs (from simulation) for the different optimization models.

To create this simulation, for each arc of a service, we sample the travel time between ports using the ll3p distribution that has been fit to the particular OD pair as discussed in Sect. 3. If the sampled travel time for an arc would cause a delay at the destination port, the simulation increases the speed of the vessel (and reduces the travel time) to make up for the delay, inducing higher sailing costs. If the sampled travel time is less than what is required to arrive at the destination port on time, the simulation decreases the speed (and increases the travel time) to reduce fuel consumption and save money. Following the degrees of freedom of our optimization model in Phase 2, the simulated speed and travel times are limited by the minimum and maximum speeds as defined by the vessel type from the LINERLIB. As a consequence, in case of speed ups, the simulated vessel may not be able to make up for all of the delay at the destination port. The remaining lateness is then propagated to the next arc until the service terminates. We propagate lateness in the simulation because, as mentioned earlier, it is hard to anticipate which recourse action would be taken at each port where lateness might occur. By letting it accumulate in the simulation, we can easily evaluate the quality of the tactical planning and get an idea of the worst case performance of the service.

More formally, the simulation creates individual services runs from an optimized schedule (including order of ports, scheduled departure and arrival times at ports, and optimized speeds [only Phase 2]) as provided by Phase 1 and Phase 2 optimization models. The discrete-event simulation process is as follows:

  1. 1.

    For each arc between ports i and j, a travel time \(t^{ rand }_{ij}\) is sampled from the appropriate travel time distribution. For the ll3p distribution, if \(t^{ rand }_{ij} > 10\mu _{ij}\), where \(\mu _{ij}\) is the empirical mean travel time from i to j, then \(t^{ rand }_{ij}\) is set to \(10\mu _{ij}\). We truncate the ll3p-generated travel times because the fitted ll3p distributions often yield a very long tail, inducing unrealistically long sampled travel times. Even if such a long travel time may occur in practice, e.g., due to a storm or a port strike, we would not be able to deal with these by means of a more reliable schedule or an adaption of speeds on a tactical planning level. In these cases, ports would need to be skipped and other significant changes would need to be made, which we do not want to consider here to allow for a fair comparison between tactical planning and operations.

  2. 2.

    The delay at port j when sailing from i to j is computed as \(e_{ij} := -( t^s_{j} - t^{ rand }_{ij} - t^e_{i} ) \), assuming that departure is at \(t^e_{i}\).

  3. 3.

    To determine the arc-specific speed \(\delta _{ij}\) that a vessel would need to sail to arrive at port j on time, the simulation computes the sailing duration as follows:

    $$\begin{aligned} \rho _{i j} = t^s_{j} - (t^e_{i} + e_{ij}). \end{aligned}$$

    Here, we assume that today’s sailing time between two ports i and j is random, but known when leaving port i so we can react with an optimized speed level. Implementing the idea of minimum and maximum sailing times from Constraints (22), the sailing duration is restricted by minimum and maximum sailing times:

    $$\begin{aligned} t^{ Min }_{ij} \le \rho _{i j} \le t^{ Max }_{ij}. \end{aligned}$$

    Finally, the arc-specific speed can be derived from the distance between the ports \(\Delta _{ij}\), resulting in

    $$\begin{aligned} \delta _{ij} = \Delta _{ij} / \rho _{i j}. \end{aligned}$$
  4. 4.

    In case of a large positive delay, the resulting speed up may still not be enough to achieve an on-time arrival, and the remaining delay will then be propagated to the next arc.

Let us look at a numerical example for a schedule with \(t^s_{j} = 1471.0\), \(t^e_{i} = 918.0\) and scheduled travel time of 549.71. The sample travel time from ll3p distribution is \(t^{ rand }_{ij} = 558.786.\) Next, \(e_{ij} = -( 1471.0 - 558.786 - 918.0 ) = 5.786\). Last, \(\rho _{i j} = 1471.0 - ( 918.0 + 5.786 ) = 547.214\), i.e. \(\delta _{ij} = 9345.0 / 547.214 = 17.08.\) The simulation is coded in Java 8 and run on a 64-bit Windows 10 machine. We run 100,000 simulations per schedule.

5.3 Results

First, we present the results of computational experiments for Phase 1 and Phase 2 models including the results of the simulation. We then provide the results from experiments with the Phase 3 model.

5.3.1 Phase 1 and 2 results

Figure 3 presents the simulation results for Phases 1 and 2. Detailed results concerning variable and fixed costs are provided in the “Detailed Phase 1 and 2 simulation results” section of the Appendix. Figure 3a compares the average optimal number of vessels for the different instances and phases. For the standard instances, the number of vessels required for ll3p with 95% service level is almost double the number in the deterministic results (17.64 vs. 9.73). For the tight instances, the vessels required for ll3p with 95% service level are slightly more than double the number in the deterministic results (17.86 vs. 8.68). The average number of vessels is slightly larger for the tight instances than for the standard instances except when service levels are considered. This indicates the deterministic solutions do not have many natural buffers in the solutions.

Fig. 3
figure 3

Visualization of simulation results. a Number of vessels from optimization in Phases 1 and 2, b analysis of hours late for different travel time distributions, c total simulated costs

Full size image

Figure 3b displays the results of the simulations with the different travel time distributions with regard to average hours of lateness at ports. It is obvious that planning in a deterministic way leads to a significant amount of lateness on average, especially for the tight instances (up to 43 h in Phase 1 and up to 32 h in Phase 2). Interestingly, optimizing for speed levels (Phase 2) produces schedules that help reduce the average amount of lateness. However, the best option to reduce lateness is the inclusion of buffers. With norm 0.7 or ll3p 0.7 optimized schedules, lateness can be reduced significantly. Considering the long tail of the ll3p distribution, planning with a buffer based on ll3p 0.9 makes lateness almost disappear, of course at the cost of a large number of required vessels. Here, the value of the more realistic distribution, especially its long tail, comes into play for all instances and phases.

Finally, Fig. 3c visualizes the total simulated costs, which include variable costs arising from realizing schedules by simulation and fixed vessel costs provided by optimization. This metric yields the operational costs and should match the total costs of tactical planning in an idealized setting. The total costs increase by 49% for the standard and 61% for the tight instances. For almost all instances and phases, a higher service quality comes at a higher total cost, mainly due to the larger number of required vessels. For Phase 2, the variable sailing costs decrease for all instance types, and the number of vessels remains close to the values found in the Phase 1 optimization results. The average planned tactial speed level drops from 16.5 or 17 knots in Phase 1 to as low as 12.46 knots with the ll3p 0.95 service level. Interestingly, for standard instances in Phase 1, including buffers based on ll3p 0.7 can reduce total simulated costs a bit compared with the deterministic schedule. Enforcing a high service level based on ll3p 0.95 increases total costs greatly, though.

5.3.2 Phase 3 results

The main difference between Phase 3 and Phase 2 is the inclusion of revenue generation and transit time limitations for container demands. For our experiments, we focus on how much demand is carried under different service guarantees with these new limitations. Table 3 shows the percentage of total available demand carried for various ll3p service levels, along with the average increase in port-to-port travel time over the deterministic Phase 3 model solution. We provide results for two different settings of maximum transit times. The “LL” results use the maximum transit time for container demands as listed in the LINERLIB, whereas “LL 1.5” uses the LINERLIB maximum transit times multiplied by 1.5. As in Phases 1 and 2, we evaluate each service with a standard (S) and a tight (T) instance. We provide these longer durations because the ones in the LINERLIB are tailored to Maersk Line’s network, which is somewhat different than COSCO’s network. The longer durations also show how much more demand can be carried when the restrictions are relaxed.

Table 3 The percentage of total cargo carried in the Phase 3 model and increase in port-to-port transit times over the deterministic solution for several service levels using the ll3p distribution
Full size table

Our results show that when using the transit times in the LINERLIB, even a service guarantee of 0.7 results in less than half of the containers of the deterministic solution being carried on 12 services. The increase in transit times between ports to achieve service levels is why cargo is not being carried, as in many cases the transit time is over 50% higher for a service level of 0.7. Raising the maximum transit times by 50% allows significantly more containers to be transported, resulting in only one service where both the S and T variants at the 0.7 service level carry less than half of the containers of the deterministic version. We note that in the case of awe2 at service level 0.9, the average transit times slightly decrease over the deterministic solution due to the selection of a different route.

The message for carriers from these results is clear: implementing a punctuality guarantee requires them to either charge higher freight rates to shippers or to convince shippers to accept higher maximum transit times. However, this work provides a mechanism for quantitatively assessing how much extra revenue or transit time would be necessary to run a profitable service. For example, on the abx service in the standard case, the carrier only needs to convince their customers to accept 11% longer transit times (on average around the service) for a 70% service guarantee. Our model is particularly useful in this respect in comparison to models that do not optimize the vessel route, as such models will not yield any insights when adjusting transit time limitations or cargo revenues.

5.4 Sample service plans

Depending on the optimization model of the particular phase, the resulting schedules may differ significantly, even when total costs are similar. We present some of the created schedules to understand the impact of the different assumptions on them.

Figures 4a–d compare the optimal schedules for the different phases of service awe3 (standard). This service connects ports in North America with ports in East Asia. In Fig. 4, the dashed line reflects the result of the corresponding deterministic optimization, and the solid blue line shows a given service level. The sequence number for each port is shown in a box with a color matching either the deterministic or 0.7/0.9/0.95 service level solution. For Phase 1 (see Fig. 4a), the optimal deterministic port order is HKG–YTN–KHH–SHA–PUS–SAV–CHS–ILM–PCN–ZLO–HKG, requiring a total of 11 vessels and sailing costs of $2.871 million per rotation. Including buffers based on ll3p 0.9 completely changes the order of the ports in the optimal schedule, increasing the number of vessels to 16 and slightly reducing sailing costs to $2.837 million per rotation. Simulation of these schedules reveals a significant reduction of the speed ups required to ensure punctuality (from 40 to 4%). Interestingly, although a high service level means investing in a large number of vessels, due to slow steaming, the simulated sailing cost is so small that the simulated total costs can be reduced a bit ($7.264 million for deterministic vs. $7.072 million for ll3p 0.9).

Fig. 4
figure 4

Visualizations of the deterministic and 0.9 ll3p service level solutions for service awe3. a Phase 1 (Det/0.7), b Phase 1 (Det/0.9), c Phase 2, d Phase 3 (LL 1.5)

Full size image

The results of optimization of this instance for Phase 2 can be seen in Fig. 4c. Both schedules are different from their Phase 1 counterparts in the order of port visits, and the schedules operate in opposite directions. The number of vessels remains constant compared with Phase 1, but the optimized and realized speeds vary. For the deterministic solution, we have a planned average speed of 13.8 knots, and for the ll3p 0.9 based solution a value of 12.41 knots. When optimizing speed levels, required speed ups can be reduced from 24 to 3%, reducing planned and simulated variable sailing costs. However, due to the larger number of vessels, total simulated costs increase significantly from 65.14 to 77.35, which is accompanied by an average reduction of lateness from 2.7 to 0.2 ports per trip.

The Phase 3 solutions show the drop-off in cargo on the individual legs of the solution for the 0.9 service level. Both the fronthaul and backhaul see significant reductions in containers carried, with service level 0.9 taking 2.6\(\times \) less cargo on the fronthaul and 7.8\(\times \) less on the backhaul. While many carriers would likely be willing to accept reductions in utilization on the backhaul in exchange for high punctuality guarantees (90% on-time would lead the industry by a significant margin), reductions in fronthaul utilization are especially bad for a carrier’s profits.

6 Conclusions

We solved the liner shipping service design problem with arrival time service levels. We showed that a three parameter log-logistic distribution fits the journeys of liner ships better than other distributions, such as the uniform or normal distribution, that were previously used in the literature. Our mathematical models of the service design problem use chance constraints to ensure that vessels arrive on time from a tactical planning perspective. Simulation of schedule operations allows for the comparison of planned total costs with “actual” total costs. Despite modelling a realistic version of service design, the model is nonetheless computationally tractable with a state-of-the-art mixed-integer programming solver. Our results show that services can be designed with on-time guarantees and that the route a vessel takes heavily influences the service level required. Furthermore, our model allows carriers to quantitatively assess what level of service they wish to offer and can support them during negotiations with shippers over prices and container transit time limitations.

This model provides a basis for several directions of future work. First, more detailed disruption recovery actions could be considered not only in the simulation of the model solution, but also in the model itself. Actions such as skipping ports or not fully loading/unloading containers when severely delayed could be included, however these would likely make the model significantly harder to solve. Furthermore, faster solution techniques could be considered such as branch & price or heuristic approaches. These would make the model more useful for operational decision support when negotiating berthing windows with terminals. Finally, time windows could be made optional, i.e., instead of a planner specifying time windows, the model could determine optimal time windows that the planner could then attempt to negotiate with a terminal.