Cargo Routing Optimization in Liner Shipping Networks

Containerized shipping plays a crucial role in global trade, as evidenced by the report of the United Nations Conference on Trade and Development (UNCTAD). More than 80% of the volume of international trade is currently transported by sea, with 1.95 billion tons transported in containers. There are two main container sizes: 20-foot and 40-foot containers. So, the vessels’ storage space is divided into 40-foot units, allowing for the stacking of either 40-foot or 20-foot containers. The Twenty-foot Equivalent Unit (TEU) is the unit generally used to count containers, where a 40-foot container is equivalent to 2 TEUs. Moreover, containers can be divided in three main categories. Dry containers are the most commonly used and are suitable for transporting dry commodities (e.g. textiles or electronics). Reefers are designed for transporting temperature-sensitive commodities (e.g. perishable foodstuffs or pharmaceuticals). These containers are equipped with temperature control systems to maintain specific conditions throughout the trip and so require a connection to the vessel’s electrical network. Empty containers correspond to dry or reefer containers that have been emptied of their commodities after delivery. They must be transported to ports where they will be refilled.

Containers are transported in a regular liner shipping network that can be defined as a set $ℛ$ of rotations (or services). Each rotation $r$ of $ℛ$ is defined by a sequence $s_r$ of ports ($s_r=(p_1^r,p_2^r,\mathrm{\dots },p_{|s_r|}^r)$). Note that a port can appear multiple times in a given rotation. In such a case, the rotation is said complex. For instance, Figure 1 proposes a network with four rotations among which rotation $(5,\mathrm{\hspace{0.17em}8},\mathrm{\hspace{0.17em}9},\mathrm{\hspace{0.17em}10},\mathrm{\hspace{0.17em}8},\mathrm{\hspace{0.17em}11})$ is complex. Each rotation must visit the ports on a regular schedule (usually weekly [9]). Assuming a weekly schedule, the maritime company assigns to the rotation as many vessels as the number of weeks that are needed to make a complete trip and these vessels must belong to the same vessel type. Each vessel type gathers the vessels having the same features (like the size, the draft, the number of plugs for reefers, or the fuel consumption). For example, all vessels of type $v$ can transport up to $\kappa (v)$ containers (expressed in TEU) and have $\rho (v)$ electrical plugs for reefers. We denote ${𝒱}_r$ the set of vessel types compatible with the visited ports of rotation $r$ (e.g. based on size, draft restrictions, port infrastructure, or other operational constraints).

For sake of simplicity, containers having the same features (e.g. origin, destination and nature) are gathered into commodities. Each commodity $k$ is then viewed as a number $q(k)$ of containers (expressed in TEU) to be transported from the origin port $pol(k)$ to the destination port $pod(k)$, with a revenue $rev(k)$ per TEU and a nature $nat(k)$ (reefer, dry or empty). To optimize cargo transportation, it is possible to divide a commodity into $s$ parts if necessary, each part taking a different route. The route taken by a commodity (or one of its parts) is defined by the sequence of ports and rotations through which it transits. The route can be direct when the origin and destination ports of the commodity are on the same rotation. Otherwise, the commodity will need to transit through multiple rotations. The transition from one rotation to another is an operation called transshipment, which takes place at a port common to both rotations. We denote $t{s}_{max}(k)$ the maximum number of transshipments authorized for the commodity $k$. This number generally depends on the nature of the commodity. For example, reefers are rarely transshipped in practice to ensure that temperatures are respected. We denote $ts(p)$ the cost generated by transshipping one TEU at port $p$.

The cargo routing problem in a liner shipping network can be defined as follows: given a predefined network $ℛ$ regularly serving a set $𝒫$ of ports in a determined order, the set ${𝒦}_0$ of commodities, and a set $𝒱$ of vessel types compatible with the visited ports, the problem consists in determining which maritime routes the commodities will take to be transported from their port of origin to their port of destination while optimizing a given criterion. Depending on the needs, different criteria can be exploited, ranging from maximizing the revenues generated by the transportation of commodities, to optimizing the total quantity of commodities transported, or even minimizing the distances traveled by the containers.

This problem has various crucial applications in logistics management and planning operations. It allows shipping companies to optimize their networks by identifying the best routes to transport containers more efficiently and profitably. Furthermore, by understanding long-term transport demands and container flow patterns, investments in new vessels can be more precisely planned, thus minimizing financial risks and ensuring adequate capacity to meet future demand. Another possible use is related to event simulation, such as the inability to pass through the Suez Canal, in order to find the most appropriate response, possibly by routing the commodities differently.

The cargo routing problem is addressed in the literature at different levels, with a primary focus on the tactical and operational levels [12, 23, 15]. The tactical level is related to the design of the liner shipping network [6]. Designing such a network requires defining the rotations and deciding which type of vessels will operate them, while taking into account the flow of commodities to be transported. The amount of carried commodities, the revenues or benefits they generate or the costs associated with the routes they take are important criteria to assess the quality of the designed network. The problem of cargo routing is therefore a crucial step in network design. Studying this problem can lead to create more efficient and profitable networks that are well-suited to the underlying cargo flows. Reinhardt and Pisinger [16] propose an exact branch-and-cut method to address the combined problem. Their mixed-integer program integrates the cargo routing problem with transshipments, considering factors such as the cost of transshipment and complex routes, which are routes in which the same port is visited twice. Wang and Meng [22] impose transit time restrictions on commodities, excluding any transshipment between rotations. To address this, they introduced a mixed-integer non-linear non-convex programming model. This method simultaneously designs the network and determines the cargo flow through it. Ameln et al. [3] introduce a novel flow-based formulation for network design, incorporating complex rotation structures and transshipment costs. Lee et al. [11] propose a framework that simultaneously optimizes service network design and commodity routing, incorporating total transit time into the minimization criteria.

The second level is operational in nature. Given an existing liner shipping network and the types of vessels associated with each rotation, its purpose is to decide how a given set of commodities is to be transported. It is important to note that here, the commodities are perfectly known (number of containers, weight, customers, etc.), whereas, at the tactical level, we are only talking about estimates based on target market shares. Moreover, the focus is on optimizing the cargo routing within the given network structure. Agarwal and Ergun [1] present one of the first scalable approaches to this problem. They propose a “route-first-flow-next” approach, where optimal routes for vessels and the number of vessels deployed on each route are determined in the first step, and then containers are routed through the network in the second step. The model incorporated cargo transshipment operations, but transshipment costs were not considered in the network design stage. The transshipment costs are taken into account in the work of Alvarez [2], with also a two-step approach used to solve the problem. This approach applies a matheuristic method to perturb the rotations using a taboo search scheme, solves the container flow problem using an interior point method, and generates new rotations from the dual variables obtained from the container flow solutions. This two-step approach has been successfully applied and expanded in multiple studies (e.g., [5, 4, 14, 10, 20, 13, 7]).

Most works in the literature focus on a single type of vessel per rotation, handle only dry containers and consider either the tactical level or the operational one. In this paper, we consider a more general approach by handling three types of containers, making it possible to divide commodities and taking as input a set of vessel types compatible with the visited ports of the rotation. This latter point allows for using our approach both at the network design level and the operational level. For network design, considering a set of compatible vessel types offers the option of choosing the type of vessels to be used for each rotation later. The operational level is taken into account by simply considering a singleton for the set of possible vessels of each rotation. Dividing up commodities can be useful in ensuring a better vessel filling factor, which is often used as a quality indicator of rotations by shipowners. We implement our approach thanks to two COP models and a local search method. These latter are quite flexible and, notably, can exploit various optimization criteria.

This paper is structured as follows. Section 2 introduces the necessary concepts of constraint programming. Then, in Sections 3 and 4, we present two modeling approaches in the form of COP instances. In Section 5, we describe a local search method. Finally, we conduct an experimental comparison of our two models and the local method in Section 6, before drawing our conclusions in Section 7.

An instance $P$ of the Constraint Optimization Problem (COP) [17] can be defined as a 4-tuple $(X,D,C,f)$ where $X=\{x_1,\mathrm{\dots },x_n\}$ is the set of variables, $D=\{D_{x_1},\mathrm{\dots },D_{x_n}\}$ is the set of domains, the domain $D_{x_i}$ being related to the variable $x_i$, $C=\{c_1,\mathrm{\dots },c_e\}$ represents the set of the constraints which define the interactions between the variables and describe the allowed combinations of values and $f$ specifies the criterion to be optimized. Solving a COP instance $P=(X,D,C,f)$ amounts to finding an assignment of all variables of $X$ satisfying all constraints of $C$ and optimizing the criterion given by $f$. This is an NP-hard problem.

One of the advantages of constraint programming lies in the existence of specialized constraints (the global constraints) which will make easier the modeling of problems, but also, their solving thanks to their dedicated filtering algorithms. In the following, we will exploit the following global constraints (where $\odot$ denotes a relational operator among $\le$, , $=$, $\ne$, $>$ or $\ge$ and $Y$ an ordered subset $⟨y_1,y_2,\mathrm{\dots },y_{|Y|}⟩$ of $X$):

• $\mathrm{■}$

  Element$(Y,i)=k$ which ensures that the $i$th value of $Y$ (using a 0-based indexing) is equal to $k$ ($Y$ can be here an ordered set of variables or values) [21],

• $\mathrm{■}$

  Ordered$(Y,\odot )$ that imposes $y_1\odot y_2\odot \mathrm{\cdots }\odot y_{|Y|}$.

• $\mathrm{■}$

  Sum$(Y,\mathrm{\Lambda })\odot k$ which imposes that the sum of the values of $Y$ weighted by the coefficients of $\mathrm{\Lambda }$ satisfies the condition imposed by the relation $\odot$ with respect to $k$. In the following, this constraint will be represented in the more explicit form $\sum _i{\lambda }_i.y_i\odot k$.

The cargo routing problem being one of the sub-problems constituting the liner shipping network design problem (LSNDP [6]), this first model is inspired by a part of the model presented in [8]. However, it allows going further by taking into account complex rotations. The idea of this first model (denoted ${ℳ}_1$) is to deduce the routes taken by the commodities from the rotations.

In this second model (denoted ${ℳ}_2$), we consider as input each of the possible routes for each commodity. To determine these routes, we first construct the rotation graph. This graph has a vertex for each rotation. There is an edge between two vertices if the two rotations share at least one port. The edges are then labeled by the shared ports. This graph allows us to quickly identify the ports where transshipments can take place. For each commodity $k$, we compute the set of possible routes by calculating all paths starting from the rotations containing the port $pol(k)$ and arriving at a rotation containing the port $pod(k)$ and containing at most $t{s}_{max}(k)$ transshipments.

Given a commodity $k$, a route is a sequence $(s_1^k,s_2^k,\mathrm{\dots },s_{t_k}^k)$ of port sequences such that:

• $\mathrm{■}$

  $s_{\mathrm{\ell }}^k$ is a sequence of ports $(p_1^{r_{\mathrm{\ell }}},p_2^{r_{\mathrm{\ell }}},\mathrm{\dots },p_{|s_{\mathrm{\ell }}^k|}^{r_{\mathrm{\ell }}})$ (with $|s_{\mathrm{\ell }}^k|\ge 2$) associated with the rotation $r_{\mathrm{\ell }}$ such that $p_m^{r_{\mathrm{\ell }}}$ is the port preceding the port $p_{m+1}^{r_{\mathrm{\ell }}}$ in the rotation $r_{\mathrm{\ell }}$. The first port in the sequence $s_{\mathrm{\ell }}^k$ corresponds to the port where the commodity enters rotation $r_{\mathrm{\ell }}$ while the last one is where it leaves this rotation.

• $\mathrm{■}$

  $p_1^{r_1}=pol(k)$.

• $\mathrm{■}$

  $p_{|s_{\mathrm{\ell }}^k|}^{r_{\mathrm{\ell }}}=p_1^{r_{\mathrm{\ell }+1}}$, this means that this port is used for transshipment.

• $\mathrm{■}$

  $p_{|s_{t_k}^k|}^{r_{t_k}}=pod(k)$.

Note that $t_k$ minus one is the number of transshipments of commodity $k$. We denote $routes(k)$ the set of all possible routes for transporting commodity $k$ and $route(k,i)$ the $i$-th route of $routes(k)$. We extend these notations to each part $j$ of each commodity $k$.

This second model includes the variables $q_j$, ${\alpha }_j$, $leav{e}_{j,i}^r$, $v_r$, ${\kappa }_r$ and ${\rho }_r$ from the first model, as well as the constraints presented in Figures 2 and 4. The difference between the two models lies simply in the way the routes are represented. In this second model, for each part $j$, we consider a Boolean variable ${\beta }_j^{\mathrm{\ell }}$ which equals 1 if route $route(j,\mathrm{\ell })$ is used to transport part $j$, 0 otherwise. Constraint (6) (see Figure 6) ensures that a part $j$ uses at most one route, while constraint (6) establishes the link with the variables $leav{e}_{j,i}^r$. Regarding the objective functions, we can exploit functions (5) and (5) from Figure 5 respectively for maximizing the number of carried TEUs and the revenue. Function (5) allows for maximizing the benefits where $cos{t}_{ts}(route(j,\mathrm{\ell }))$ denotes the total transshipment cost per TEU for the $\mathrm{\ell }$-th route of commodity $j$.

A real instance of the cargo routing problem can easily involve several dozen ports and several hundred of commodities for a total volume of more than 100,000 TEUs. The ability of complete solvers to solve such instances in a reasonable time can therefore quickly become limited. In this section, we present an incomplete method that is intended to be generic, in the sense that it does not depend on the criterion to be optimized. This method (called $Route$, see Algorithm 1) takes, as inputs, the set $ℛ$ of rotations and the set ${𝒦}_0$ of commodities to be transported, and will return the best solution ${𝒦}_p^b$ that it has found according to the criterion considered. A solution is represented here by a set of triplets $(k,n,r)$ representing the assignment of $n$ TEUs of commodity $k$ to route $r$. The $Route$ method begins with an initialization phase (lines 1-5) during which it computes all possible routes for each commodity $k$ in ${𝒦}_0$ (line 2) according to the same process as model ${ℳ}_2$. A first solution ${𝒦}_p^{init}$ is used to initialize the current solution ${𝒦}_p$ (lines 4 and 11). For example, it can be provided by the user or constructed from scratch using the $Assign$ method (see Algorithm 2). Then, the $Route$ method tries to improve the quality of the current solution by alternating between a phase where it moves or removes commodities (line 8) and a phase where it places the commodities on routes (line 9). This alternation is repeated $\mathrm{\#}trial$ times (lines 7-10). At the end of each iteration, the best solution ${𝒦}_p^b$ is updated if necessary (line 10). Once the allotted number of trials for a given initial solution has been completed, we restart the search from the initial solution or the best solution found to avoid the problem of local optima (line 11). Note that heuristics can be used to choose between moving or removing commodities (line 8) or restarting from the initial solution or the best solution found (line 11). We give some examples of such heuristics in Section 6.

The objective of the $Assign$ method is to assign as many commodities as possible to the available routes within the limit of the number $s_{max}$ of possible divisions of the same commodity $k$. Thus, for each commodity $k$ for which there are still containers to be placed, this method will identify the possible routes among the routes initially available for the commodity $k$. A route is possible if the rotations it uses are able to accept commodity in terms of load (for reefer, dry or empty containers) or in terms of electrical plugs (for reefer containers). The function $routes$ returns the list of possible routes for a commodity $k$ with respect to the current solution ${𝒦}_p$. To do this, it relies on the types of vessels available for each rotation. The available types are constantly evolving due to the addition, move or removal of commodities, ensuring that at each step, there is at least one possible vessel type for each rotation. The $best\mathrm{\_}route$ function returns the available route $r$ that allows transporting the most containers of commodity $k$ depending on its nature as well as this number $n$ of containers. The $Move$ method (see Algorithm 3) is based on a similar principle. The main difference is that a quantity $n$ of commodity $k$ is initially transported via route $r$ and that a part or all of this quantity will be transported via a new route $r^{\prime }$. The underlying idea is to free up space (e.g. on a potentially saturated route) to allow the routing of another commodity. Finally, the $Remove$ method (see Algorithm 4) allows the removal of some commodities from some routes. With this aim in view, we randomly select a commodity and a route from ${𝒦}^p$ and remove the related number of TEUs from this route. We repeat this process until at least $n{b}_{rem}$ TEUs have been removed.

Different heuristics can be used to decide the order in which the commodities are processed in $Assign$ and $Move$ methods. For example, for the $Assign$ method, we can start by processing the commodities that have the fewest possible routes, or sort them according to the remaining quantity to be routed. For the $Move$ method, we can prioritize commodities transported via rotations where vessels are full when leaving certain ports. Furthermore, several different criteria can be considered (line 10 of Algorithm 1) such as, for example, maximizing the number of containers transported, the revenue generated or the benefits. The approach presented here is therefore relatively general and can easily be specialized according to needs. It is parameterized by the number $n{b}_{rem}$ of commodities to remove at each call to the $Remove$ method, the number $\mathrm{\#}rst$ of restarts and the number $\mathrm{\#}trial$ of iterations per restart performed in the $Route$ method. Finally, as we will see in the next section, it can be used both to help design a network and to route commodities at the operational level.

Algorithm 1 can be considered as a case of the large neighborhood search (LNS) [18, 19]. LNS operates by partially destroying and then repairing a solution while controlling the search strategy for optimization problems. In Algorithm 1, the move/remove operations (line 8) can be seen as destroying part of the solution, while the assignment step (line 9) serves as the repairing phase. Restarts from a new solution and moving commodities help diversify the search. Intensification occurs during the assignment steps of commodities or when restarting from the best solution, which is saved or accepted throughout the search process.

In this paper, we have proposed two CP-based models for solving the cargo routing problem, as well as an incomplete method. The results we have obtained show the difficulty of optimally solving the cargo routing problem with a complete approach and so highlight the practical interest of incomplete methods such as the one we propose. This latter turns to be robust and provides relevant solutions within a very reasonable runtime whatever the criterion we consider. Our results also point out the difference in difficulty depending on the optimization criterion considered or the nature of the instances (feedering or general). On this latter point, a possible improvement for general instances would be to processes feedering and main line rotations separately.