Tabu search in maritime transportation

Tabu search in maritime transportation

International trade depends heavily on maritime transportation and more than 7 million tons of goods are carried by ships every year. A ship involves a major capital investment, and its daily operating costs often amounts to several thousand dollars. On the other hand, the revenues that can be made by lifting cargoes can be substantial. Therefore, proper routing and scheduling of the ship fleets is crucial, as a modest improvement in fleet utilization can result in large profit improvements.

Korsvik et al. (2010a) studies an important routing and scheduling problem faced by many tramp shipping companies transporting bulk products. A shipping company operating in the tramp market usually has a set of mandatory contract cargoes it is committed to carry, while trying to derive additional revenue by accepting optional spot cargoes. Each cargo (both contract and spot) consists of a given quantity of product that must be picked up at its loading port, transported and then delivered to its discharge port. There are given time windows during which the loading of the cargoes must start, and there may also be time windows for discharging. To transport the cargoes available in the following planning horizon the shipping company controls a fixed heterogeneous fleet of ships, where the ships may have different capacities, speed and cost structures.

Korsvik et al. (2010) propose a tabu search heuristic for solving the tramp ship routing and scheduling problem. Such problems are often tightly constrained and an important feature of the approach is the possibility of exploring solutions that are infeasible regarding time windows and ship capacity during the search. The search neighborhood is simple and consists of moving one cargo from one ship route to another, possibly also to or from a list of rejected cargoes (cargoes that are not yet in the solution). For each move, a large number of cargo insertions into a ship route is evaluated. To speed up the algorithm, they therefore apply neighborhood reduction, where the cargo’s pickup node’s position in the ship route is fixed before determining the position of the corresponding delivery node. To diversify the search, any non-improving solution is penalized based on the number of times an attribute has been added to the solution during the search, where and represent the cargo and ship, respectively. Korsvik et al. (2010) show that their tabu search heuristic provides very competitive results for real problems.

Korsvik and Fagerholt (2010) study an important real life extension of the above tramp ship routing and scheduling problem. Here, the quantities of the cargoes are not fixed but flexible within an interval, e.g. 10 000 tons 15%. Therefore, interwoven with the routing and scheduling decisions, the planner must also decide optimal cargo quantities. A tabu search heuristic embedding a separate method for determining optimal cargo quantities for given ship routes is proposed. In contrast to (Korsvik et al., 2010), this tabu search heuristic does not allow infeasible solutions during the search. Therefore, they extend the search neighborhood by also including a swap operator, which swaps two cargoes between two different ship routes, i.e. the attributes and is replaced by and . They also use a periodic diversification, which proved to be efficient. For every iteration, they select the attribute that has been part of the solution for the largest number of consecutive iterations, and replace it with the best non-tabu attribute , where . The attribute is then tabu for a given number of iterations. Computational tests show that the proposed tabu search heuristic provides good solutions for real life problems. The tests also show that utilizing flexible cargo quantities in the planning can be of great value as the shipping companies can use the flexibility to transport additional spot cargoes.

Versions of both the methods by Korsvik et al. (2010) and Korsvik and Fagerholt (2010) have been implemented in TurboRouter, which is a decision support system for ship routing and scheduling developed by MARINTEK in cooperation with the Norwegian University of Science and Technology (see for instance (Fagerholt, 2004) and (Fagerholt and Lindstad, 2007)).

References:

J. E. Korsvik and K. Fagerholt (2010) “A tabu search heuristic for ship routing and scheduling with flexible cargo quantities”. Journal of Heuristics 16(2), 117-137.

J. E. Korsvik, K. Fagerholt and G. Laporte (2010) “A tabu search heuristic for ship routing and scheduling”. Journal of the Operational Research Society 61, 594-603.

K. Fagerholt and H. Lindstad (2007) “TurboRouter: An interactive optimisation-based decision support system for ship routing and scheduling”. Maritime Economics and Logistics 9, 214-233.

K. Fagerholt (2004) ”A computer-based decision support system for vessel fleet scheduling – Experience and future research”. Decision Support Systems 37(1), 35-47.