The Container Ship Routing Problem and Its Practical Solutions

The Container Ship Routing Problem and Its Practical Solutions
JIN Zhi-Hong, YOU Qing-Hua, WANG Jun
College of Transportation and Logistics, Dalian Maritime University, P.R.China, 116026
Abstract: The container ship routing problem (CSRP) is a special variant of the classical vehicle
routing problems (VRPs). The CSRP is different from the VRP with backhauls (VRPB). The VRPB
includes both a set of customers to whom cargoes are to be delivered from a depot, and a set of
suppliers whose cargoes need to be picked up and transported back to the depot, in which it is
traditionally assumed that on each route all deliveries have to be made before any cargo can be picked
up to avoid rearranging the loads on the vehicle. Such a limitation can be relaxed for the CSRP. The
CSRP is also different from the VRP with pickup and delivery (VRPPD). Both the coupling and
precedence constraints, for the VRPPD, between the pickup and delivery stops can be relaxed for the
CSRP, since its pickup cargoes (empty containers) in all stops (ports) must be taken back to the depot
(hub). This paper formulates CSRP as a MIP and proposes two practical algorithms for it. Numerical
experiments indicate the proposed methods are effective in reducing the total shipping cost.
Keywords: Container Transportation, Ship Routing Problem, Backhaul, Time Windows
1. Introduction
1.1 Problem statement
The classical vehicle routing problem (VRP) involves a set of delivery (or pickup) customers to be
serviced by a fleet of vehicles housed at a depot or distribution center (DC), located in the same
geographical region as the customers. The quantities to be delivered or picked up are known in advance.
The vehicle fleet is homogeneous. The objective of the problem is to decide a set of vehicle routes such
that all delivery (or pickup) points are serviced, the demands of all points assigned to each route cannot
violate the capacity of the vehicle and the total distance traveled by all the vehicles is minimized.
The VRP with backhaul (VRPB) is an extension of the VRP involving both delivery and pickup
points. The delivery points are sites that are to receive a quantity of goods from the DC; and the pickup
points are sites that send a quantity of goods back to the DC. The VRP with time windows (VRPTW) is
another extension of the VRP, in which each point must be served within a specified time window.
The VRP with backhaul and time windows (VRPBTW) is a combination of the VRPB and
VRPTW. For the traditional VRPBTW, there is a critical assumption that all delivery must be made on
each route before any pickup can be made (see Figure 1). Such an assumption arises from the fact that
vehicles are often rear-loaded, and that it is often inconvenient or impossible to rearrange the delivery
goods on board in order to accommodate new pickup loads. Another practical reason is that delivery
customers have a higher service priority than pickup customers.
The VRP with pickup and delivery (VRPPD) involves a heterogeneous vehicle fleet based at
multiple depots, which must satisfy a set of transportation requests. Each request includes a pickup
customer, a corresponding delivery customer, and a demand to be transported between them. In addition
to time window and vehicle capacity constraints, the VRPPD implies other constraints, which imposes
coupling the pickup and corresponding delivery stops on the same vehicle routes, and imposes visit
precedence between each pickup stop and its associated drop-off stop.
The container ship routing problem (CSRP) is a special variant of the classical vehicle routing
problems (VRPs). It can be described as follows. A fleet of container ships is located at a central port
(hub). They must deliver loaded containers from the hub to some small ports (feeder ports), and pickup
empty containers in feeder ports and carry them back to the hub. The time window and ship capacity
constraints are same as other VRPs. The quantities of loaded containers to be delivered in the hub and
767
the quantities of empty containers to be picked up in the feeder ports are known in advance. The
objective is to decide a set of optimal container ship routes.
The CSRP is different from the VRPB, considering that the basic assumption for VRPB that on
each route all deliveries have to be made before any cargo can be picked up is not true for the CSRP.
Unlike vehicles, container ships are not rear-loaded, and it is often possible to rearrange the loaded and
empty containers in the feeder ports. For the CSRP and its difference from the VRPB, refer to Figure 2.
The CSRP is also different from the VRPPD. Both the coupling and precedence constraints, for the
VRPPD, between the pickup and delivery stops can be relaxed for the CSRP, since its pickup cargoes
(empty containers) in all stops (feeder ports) must be taken back to the common stop (hub). Besides, in
the traditional VRPPD, a vehicle is assumed to leave unloaded from its origin depot and to come back to
its destination depot without any load also. For CSRP, the container ship with loaded containers starts its
route from the hub to feeder ports, or vice versa.
Fig. 1. The VRP with backhauls
Fig. 2. The container ship routing problem
1.2 Literature review
The VRPB and its variant have attracted the attention of a number of researchers to develop exact
and approximate procedures. Toth and Vigo [14] and Mingozzi, Giorgi, and Baldacci [4] presented LP
formulations for the VRPB and developed branch and bound algorithms. Yano et al. [15] developed a set
cover based exact algorithm for a practical VRPB application. It is well known that all VRPs belong to
the class of NP-hard combinatorial optimization problems. Therefore it is impossible to find exact
solutions of real-life problems with a reasonable computational effort. Thus most researches in the
literature have concentrated on the development of approximate algorithms. For a comprehensive survey
of the literature, we refer to Toth and Vigo[12]. Many of the latest developments have focused on
VRPBTW and occurred in the area of local search algorithms [7,9,11,13]. All of these contributions to
VRPBTW were under the assumption that all delivery must be made on each route before any pickup.
In this paper, we relax such a limitation and present a formulation for the CSRP. Then we propose
two heuristic algorithms for solving large-scale container ship routing problem instances. Finally,
numerical experiments from the benchmark problems show their efficiency.
2 Formulation of the CSRP
2.1 Notation
The CSRP can be described in detail as follows. A fleet of ships V with a given capacity is located
at hub and must serve a number of geographically dispersed feeder ports in branch lines. The feeder
ports set includes both a subset of feeder ports to whom cargoes are to be delivered from hub, and a
768
subset of feeder ports whose empty containers need to be picked up and transported back to the hub.
Each feeder port has its service time window request, during which the service must be started. Let
G = ( N , A) be a network with node and art sets:
N = {0,1,2,..., n} , A = {(i, j ) | i, j ∈ N ; i ≠ j} ,
where {1,2,..., n} represents the feeder ports set and 0 refers to the hub. The delivery demand of feeder
port i is d i , its pickup demand is pi , measured in the same unit as ship capacity Q . The service of
customer i must start within the time window [ei , li ] and service time is s i . For each arc (i, j ) ∈ A ,
travel cost cij can be represented in terms of distance d ij or travel time t ij . A feasible solution S is a
set of feasible ship routes. The CSRP is to find an optimal set of routes subject to side constraints such
as
(1) all routes start and end at the hub;
(2) each feeder port is visited exactly once by some ship within its time window; and
(3) the load (delivery and pickup amount) at any time in a route cannot exceed the ship capacity.
There are three types of decision variables used in the mathematical formulation: binary flow
k
variables X ij , k ∈ V , i, j ∈ N , i ≠ j , time variables Ti ,
i ∈ {0, N } , and load variables
Lki , i ∈ N , k ∈ V . Let X ijk equal to one if ship k travels from i to j , and equal to zero otherwise.
k
Let Ti be the time at which service at i begins. Let Li be the total load on ship k just it leaves i .
Based upon the above notation, we give the following formulation.
2.2 MIP formulation
The CSRP can be formulated as the following mixed integer programming:
Minimize
C (S ) = α ∑ t ij X ijk + β V + γ ∑WTi + σ ∑ LTi
i∈N
i , j ,k
(1)
i∈N
Subject to:
∑ ∑X
k
ij
= 1 , ∀i ∈ N
(2)
k ∈V j∈N ∪ 0
∑X
k
0j
= 1,
j∈N
∑X
∑X
k
j0
= 1 , ∀k ∈ V
(3)
j∈N
k
ij
j∈N
− ∑ X kji = 0 , ∀k ∈ V , ∀i ∈ N
(4)
j∈N
WTi = max{ei − Ti , 0}
LTi = max{Ti − li , 0}
(5)
∑ (T
j
+ s j + t ji ) X + WTi − Ti ≤ 0 , ∀i ∈ N
(7)
∑X
k
ij
( Lkj + d j − p j − Lki ) = 0 ∀k ∈ V , ∀i ∈ N
(8)
(6)
k
ji
k, j
j∈V
Lki ≤ C , ∀k ∈ V , ∀i ∈ N ∪ 0
(9)
X ∈{0,1}, ∀i, j ∈ N ∪ 0 , ∀k ∈ V
k
ij
(10)
769
Constraint (2) represents all the feeder ports can be visited only once; Constraint (3) ensures each route
starts and ends at the hub; Constraint (4) is the condition of flow balance; Constraints (5)-(7) are the
time window constraints; Constraints (8)-(9) are the load and capacity constraints. The objective (1) is to
minimize the total weighted cost, which is a weighed sum of the total travel times, the number of ships
used, total waiting time, and total tardiness time, where α , β , γ , σ are the weight factor for the four
items, respectively.
It is well known that all the VRP variants are NP-hard combinatorial optimization problems in the
strong sense. Hence, the CSRP can be solved exactly for small-sized instances, but only approximately
for large-sized instances. An efficient search procedure is designed for solving large scale of instances
of the CSRP in the follows.
3 Two Practical Heuristic Approaches
3.1 A variable neighbor search (VNS) heuristic
A hierarchical neighbor structure is designed for the CSRP, which consists of 2-opt [3], Or-opt [5],
λ -interchange [6], vehicle reduction [8] and vehicle augmentation proposed by us [2]. It is used for
search diversification purposes. When a certain number of iterations are performed by one of the above
heuristics without any improvement of the best current solution, the search moves to the next heuristics.
The search procedure is designed to be 2-opt → Or-opt → λ -interchange → vehicle
augmentation → vehicle reduction. About the variable neighbor search (VNS) heuristics, it should be
noted that
(1) For 2-opt, Or-opt, and λ -interchange, each procedure does not explore its whole neighboring
solutions, but only some subsets of customers who are the ϕ nearest neighbors from the customer
selected, in order to save computational effort and focus on the most promising exchanges.
(2) The Or-opt procedure does not include those subroutes that have been exchanged by 2-opt
procedure. Similarly, the λ -interchange procedure does not include those subroutes that have been
exchanged by either 2-opt or Or-opt.
(3) The vehicle augmentation procedure should not be activated frequently, which will impede the
convergence of the whole heuristics. It is activated only when the current best solution is not updated
within a certain number of iterations.
The vehicle reduction procedure attempts to eliminate the routes with µ customers or less.
However, when the current best solution is not updated within a certain number of iterations, its search
scope is widened to all routes.
3.2 A Tabu search metaheuristics
Tabu search (TS) is an iterative technique, which explores a set of not-tabu solutions by repeatedly
making moves to another solution located in the neighborhood of a current solution. In this paper, the
initial solutions are generated according to the sweep heuristic algorithm [1]. The neighborhood is
defined as the all feasible solutions that can be reached from the current solution using the variable
neighbor search (VNS) mentioned above. The tabu list keeps track of the last moves and their reverse
moves. The stopping criterion used is based on the maximum number of iterations after the current best
solution has been found. The solution quality and computational time are compared with both the sweep
and the VNS heuristic algorithms by a series of experiments of large-scale problems.
4 Numerical Experiments
4.1 Experimental instances
The proposed heuristic algorithms were implemented and tested on experimental instances. These
experimental instances come from Solomon benchmark problems for the VRPTW [10]. Each of the
fifty-six instances has one hundred of customers. The travel time between customers is equal to the
corresponding Euclidean distance. These problems vary in fleet size, vehicle capacity, travel time,
770
spatial distribution of customers, time window density and width, and are divided into three types: Rtype (uniformly distributed customers), C-type (clustered customers), and RC-type (a mix of R- and Ctypes). Two sets of problems are designed for each of the three types. Problem sets RC1,C1,R1 have
narrow scheduling horizon, while sets RC2,C2,R2 have wide scheduling horizon. The narrow
scheduling horizon problems have vehicles with small capacities and short route times, which results in
only a few of customers can be served by a vehicle. By contrast, the wide scheduling horizon problems
have vehicles with large capacities and long route times, so more customers may be served by a single
vehicle.
We convert these VRPTW instances into CSRP instances by taking some delivery customers to be
pickup customers. There are two types of problems generated. In type 1, all the customers are divided
into either delivery ones or pickup ones; and in type 2, all the customers are divided into delivery,
pickup, and both delivery and pickup ones. In both types, 10%, 30%, and 50% delivery customers in
original problems are designed to become pickup ones.
4.2 Numerical results
The algorithms were programmed in Microsoft Visual C++ and run on a personal computer. The
real distances between customers and the travel times were rounded to three decimal places. Each
instance was solved by ten-runs of the algorithm (with different initial solutions) and its best solution
value was obtained. Since there has not been any report about CSRP, we compare our results with those
obtained by the famous sweep algorithm [1] for VRPs. Parts of the comparison results are shown in
Tables 1 and 2.
Table 1 shows the computational results about type 1 instances, and Table 2 shows those of type 2
instances. The total weighted cost as presented in (1) and the route numbers (that is, the needed vehicles
or ships) are used to compare the proposed heuristics with sweep algorithm. Our heuristics outperform
the sweep algorithm in reducing both the cumulated number of vehicles (ships) and the total travel
distance. The tabu search heuristic performs best. For example, the total weighted costs
have
decreased 28% for type 1, and 29% for type 2, respectively. The needed vehicles (ships) have also
decreased 36% for type 1, and 37% for type 2, respectively. With regard to the computational cost, the
VNS heuristic algorithm used about same CPU time as the sweep algorithm, and the tabu search
algorithm took more than twice CPU times. These results can provide a trade-off between the
computational cost and the near-optimal solutions.
Tab. 1 Comparison results for type 1 instances
Tab. 2 Comparison results for type 2 instances
771
5 Concluding Remarks
This paper deals with the container ship routing problem (CSRP). The backhaul and time window
constraints are also considered. As far as we know, there have not been other reports about it. We
formulate the CSRP as a mixed integer programming and propose a variable neighbor search algorithm
and a tabu search algorithm for it. Numerical experiments indicate the proposed methods are effective
and competitive in reducing both the total shipping cost and the needed ship number.
Reference
[1] Gillet, B.E. and L.R. Miller (1974). “A Heuristics Algorithm for the Vehicle Dispatch Problem”,
Operation Research. 22, pp.340-349.
[2]. Jin, Z.H., S. Takano, and K. Ohno(2000). “Heuristic and Metaheuristic Algorithms for the Vehicle
Routing Problem with Time Windows”, in Proceedings of the 5th International Symposium on
Logistics, Iwate, 474-479.
[3] Lin, S(1965). Computer Solutions of the Traveling Salesman Problem. Bell System Technical
Journal 44, 2245-2269.
[4] Mingozzi, A., S. Giorgi, R. Baldacci (1996), “An Exact Method for the Vehicle Routing Problem
with Backhauls”, Transportation Science. 31, pp315-329.
[5] Or, I.(1976) Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of
Blood Banking. Ph.D. Thesis, Northwest University, Evanston, IL.
[6] Osman, I.H(1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle
Routing Problem. Annals of Operations Research 41, 421-451.
[7] Osman, I. H. and Wassan, N.A.(2002), “A reactive tabu search meta-heuristic for the vehicle routing
problem with backhaul”, Journal of Scheduling, 5, pp 263-285.
772
[8] Potvin, J.-Y. and S. Bengio(1996). The Vehicle Routing Problem with Time Windows-Part II:
Genetic Search. INFORMS Journal on Computing 8, 165-172.
[9] Salhi, S. and G. Nagy (1999), “A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle
Routing Problems with Backhauling”, Journal of The Operational Research Society 50, pp 10341042.
[10] Solomon, M.M., http://www.cba.neu.edu/~msolomon/problems.html
[11] Thagiah, S.R., J.Y. Potvin and T. Sun (1996), “ Heuristics Approaches to Vehicle Routing with
Backhauls and Time Windows”, Computers Operations Research. 23, pp 1043-1057.
[12] Toth, P. and D. Vigo (2002), “The vehicle Routing Problem”, Society for Industrial and Applied
Mathematics, SIMA, Philadelphia.
[13]. Toth, P. and D. Vigo (1999), “ A Heuristics for Symmetric and Asymmetric Vehicle Routing
Problem with Backhauls”, European Journal of Operational Research, 113, pp 528-543.
[14]. Toth, P. and D. Vigo (1997), “An Exact Algorithm for the Vehicle Routing Problem with
Backhauls”, Transportation Science. 33 (4), pp372-385.
[15]. Yano C.A., T.J. Chan, L. Richter, T. Culter, K.J. Murty, D. McGettigan (1987), “Vehicle Routing
at Quality Stores”, Interfaces. 17 (2), pp.52-63.
CMobile: 138-8962-1618 orresponding author:
JIN Zhi-Hong
College of Transportation & Logistics
Dalian Maritime University
1 Linghai Road, Dalian 116026 CHINA
Tel.& Fax: 0411-8479-6318
E-mail: [email protected]
773