Heuristics for dynamic and stochastic routing in industrial shipping

https://doi.org/10.1016/j.cor.2012.06.011Get rights and content

Abstract

Maritime transportation plays a central role in international trade, being responsible for the majority of long-distance shipments in terms of volume. One of the key aspects in the planning of maritime transportation systems is the routing of ships. While static and deterministic vehicle routing problems have been extensively studied in the last decades and can now be solved effectively with metaheuristics, many industrial applications are both dynamic and stochastic. In this spirit, this paper addresses a dynamic and stochastic maritime transportation problem arising in industrial shipping. Three heuristics adapted to this problem are considered and their performance in minimizing transportation costs is assessed. Extensive computational experiments show that the use of stochastic information within the proposed solution methods yields average cost savings of 2.5% on a set of realistic test instances.

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)

  • S. Mitrović-Minić et al.

    Double horizon based heuristics for the dynamic pickup and delivery problem with time windows

    Transportation Research Part B

    (2004)
  • D. Ronen

    Cargo ships routing and scheduling: survey of models and problems

    European Journal of Operational Research

    (1983)
  • D. Ronen

    Ship scheduling: the last decade

    European Journal of Operational Research

    (1993)
  • M. Schilde et al.

    Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports

    Computers and Operations Research

    (2011)
  • M.R. Swihart et al.

    A stochastic and dynamic model for the single-vehicle pick-up and delivery problem

    European Journal of Operational Research

    (1999)
  • R.W. Bent et al.

    Scenario-based planning for partially dynamic vehicle routing with stochastic customers

    Operations Research

    (2004)
  • D.J. Bertsimas et al.

    A new generation of vehicle routing research: robust algorithms, addressing uncertainty

    Operations Research

    (1996)
  • F. Bullo et al.

    Dynamic vehicle routing for robotic systems

    Proceedings of the IEEE

    (2011)
  • M. Christiansen et al.

    Ship routing and scheduling: status and perspectives

    Transportation Science

    (2004)
  • Cited by (33)

    • A branch-and-regret algorithm for the same-day delivery problem

      2023, Transportation Research Part E: Logistics and Transportation Review
    • Dynamic vehicle routing with random requests: A literature review

      2023, International Journal of Production Economics
    • Dynamic scheduling of patients in emergency departments

      2023, European Journal of Operational Research
    • The Robust Bulk Ship Routing Problem with Batched Cargo Selection

      2021, Transportation Research Part B: Methodological
    • On modeling stochastic dynamic vehicle routing problems

      2020, EURO Journal on Transportation and Logistics
    View all citing articles on Scopus
    View full text