Heuristics for dynamic and stochastic routing in industrial shipping
Introduction
Maritime transportation is an important component of international trade, and more than seven billion tons of goods are carried by ship annually [37]. The costs related to ships can be very high, with daily time-charter rates and fuel costs that can amount to tens of thousands of USDs. Proper planning of routes and schedules is crucial for shipping companies to achieve a good fleet utilization and reduce costs. The interest in research on ship routing and scheduling has therefore quickly increased in the last decades as can be seen from the literature reviews by Ronen [30], [31] and Christiansen et al. [7], [8].
This paper considers industrial shipping, in which the ship operator owns or controls both the cargo to be transported and the ships performing the transportation. The focus of the operator is therefore to minimize the total transportation costs while ensuring that all cargoes are transported. The planning of ship routes and schedules in industrial shipping, as well as in the other transportation modes, is to an increasing degree performed with the assistance of optimization-based decision support systems, as illustrated by Fagerholt [10], Fagerholt and Lindstad [11] and Kang et al. [21]. In practice, this often involves using heuristic solution methods to solve deterministic optimization problems based only on known information. This is done on a continuous basis as new relevant information, such as the occurrence of a new cargo, arrives, or at given time intervals. Most algorithms for ship routing and scheduling thus solve static and deterministic versions of the problem.
In land-based transportation, the previous work on dynamic and stochastic routing has indicated that the inclusion of stochastic information within a dynamic planning process is valuable [2], [16], [17]. The hypothesis tested in this paper is that the potential savings observed in the previous studies on land-based transportation will carry over to the maritime setting studied here. That is, that the results of Bent and Van Hentenryck [2] and Hvattum et al. [16], [17] will be reproduced, despite now considering a different routing problem. The problem studied here differs from those studied previously by having a pick-up-and-delivery structure (as opposed to only picking up and returning to a depot), a heterogenous fleet (as opposed to all vehicles being identical), the option to hire external capacity to deliver some cargoes (as opposed to minimizing the number of cargoes not transported), and using a different topology (traveling on a sphere instead of a plane).
To test this hypothesis, a discrete event simulation is used to reproduce a planning environment in which new cargo requests arrive over time. Whenever a replanning action is scheduled, heuristics are run to produce solutions consistent with currently available information. Three different heuristics are then considered. In the first heuristic, called the myopic dynamic heuristic (MDH), a deterministic subproblem is solved using an adaptation of the tabu search presented by Korsvik et al. [22]. This method does not utilize any stochastic information, but corresponds to actual practice for many shipping companies. The second heuristic is based on the multiple scenario approach with consensus (MSAC) of Bent and Van Hentenryck [2] and relies on generating a set of scenarios that consist of the currently known cargoes along with a sampled realization of future cargoes. Each of these scenarios is solved using the tabu search, and one of the solutions produced is selected based on a consensus function: the chosen solution is the one that is the most similar to other solutions. The third heuristic is an adaption of the branch-and-regret heuristic (BRH) of Hvattum et al. [17]. Again, scenarios are generated and solved using tabu search. Rather than selecting one of the resulting solutions, however, an iterative procedure is followed in which parts of the solution are gradually fixed in each of the scenarios until all scenarios have converged to the same solution. We test the three heuristics on a number of realistic, but randomly generated test instances.
The remainder of the paper is organized as follows. A literature review is presented in Section 2. Section 3 gives a description of the industrial ship routing and scheduling problem, including a mathematical formulation of the static and deterministic version of the problem. In Section 4 we present the three heuristics, the simulation procedure, and a tabu search that is used in all three heuristics. A computational study is presented in Section 5, while concluding remarks are given in Section 6.
Section snippets
Review of the literature
This section presents an overview of related work which is divided into three parts. We first survey work on dynamic routing problems, with a particular focus on problems that have a pick-up and delivery structure similar to that of the industrial ship routing and scheduling problem. Second, we discuss the previous work on stochastic and dynamic routing problems. Third, we review the literature on maritime routing problems explicitly incorporating stochasticity.
As explained by Psaraftis [29], a
Problem description
In the static and deterministic industrial ship routing and scheduling problem, the objective is to minimize the total variable costs for transporting a set of cargoes. A cargo consists of a specified quantity of a given product that must be picked up at its port of loading, transported, and then delivered to its port of discharge. There are specified time windows during which the loading of the cargoes must start, and there may also be time windows for discharging. The operator controls a
Solution methods
This section describes solution methods for the dynamic and stochastic version of the industrial ship routing and scheduling problem of Section 3. To evaluate solution methods, the operations of the shipping company are simulated over a long time horizon. Details of this simulation can be found in Section 4.1. During the simulation, decision points arise where the company is allowed to replan the ship routes and schedules. Three different methods to perform this replanning are considered: the
Computational study
Computational experiments were carried out in two parts. First, we have calibrated the solution methods on a small set of instances as explained in Section 5.1. Second, we have run the methods on a set of realistic instances with varying characteristics as explained in Section 5.2. Each instance was simulated over a one-year horizon, using the same realized demands irrespective of the solution method used.
Separate sets of instances were used for the calibration and main tests, respectively. In
Concluding remarks
The contribution of this paper consists in studying, for the first time, the dynamic and stochastic aspects of tactical routing in a maritime setting. Three heuristics were implemented and tested: the myopic dynamic heuristic (MDH), the multiple scenario approach with consensus (MSAC), and the branch-and-regret heuristic (BRH). Although the basic ideas of the solution methods applied are known in the literature, adaptations were required to use the methods in a maritime transportation context.
Acknowledgments
This research was carried out with financial support from the DESIMAL and MARRISK projects, partly funded by the Research Council of Norway, from the NILS Mobility Project, EEA grant UCM-EEA-ABEL-02-2009, from the Government of Spain, grant TIN2009-07901, and from the Canadian Natural Sciences and Engineering Research Council. This support is gratefully acknowledged. We thank two anonymous referees for their valuable comments.
References (38)
- et al.
Dynamic shortest path in stochastic dynamic networks: ship routing problem
European Journal of Operational Research
(2003) - et al.
Dynamic pickup and delivery problems
European Journal of Operational Research
(2010) - et al.
Logistics for world-wide crude oil transportation using discrete event simulation and optimal control
Computers and Chemical Engineering
(2004) - et al.
Maritime transportation
A computer-based decision support system for vessel fleet scheduling—experience and future research
Decision Support Systems
(2004)- et al.
Stochastic vehicle routing
European Journal of Operational Research
(1996) - et al.
Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries
Transportation Research Part C
(2006) - et al.
Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies
European Journal of Operational Research
(2003) - et al.
Adaptive ship routing through stochastic ocean currents: general formulations and empirical results
Transportation Research Part A
(1998) - et al.
Waiting strategies for the dynamic pickup and delivery problem with time windows
Transportation Research Part B
(2004)
Double horizon based heuristics for the dynamic pickup and delivery problem with time windows
Transportation Research Part B
Cargo ships routing and scheduling: survey of models and problems
European Journal of Operational Research
Ship scheduling: the last decade
European Journal of Operational Research
Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports
Computers and Operations Research
A stochastic and dynamic model for the single-vehicle pick-up and delivery problem
European Journal of Operational Research
Scenario-based planning for partially dynamic vehicle routing with stochastic customers
Operations Research
A new generation of vehicle routing research: robust algorithms, addressing uncertainty
Operations Research
Dynamic vehicle routing for robotic systems
Proceedings of the IEEE
Ship routing and scheduling: status and perspectives
Transportation Science
Cited by (33)
A branch-and-regret algorithm for the same-day delivery problem
2023, Transportation Research Part E: Logistics and Transportation ReviewDynamic vehicle routing with random requests: A literature review
2023, International Journal of Production EconomicsDynamic scheduling of patients in emergency departments
2023, European Journal of Operational ResearchA green multi-facilities open location-routing problem with planar facility locations and uncertain customer
2021, Journal of Cleaner ProductionThe Robust Bulk Ship Routing Problem with Batched Cargo Selection
2021, Transportation Research Part B: MethodologicalOn modeling stochastic dynamic vehicle routing problems
2020, EURO Journal on Transportation and Logistics