Special Issue on Latin-American Research: A Time Based Discretization Approach for Ship Routing and Scheduling with Variable Speed

摘要

In this paper we develop a network based model for the routing and scheduling of a heterogeneous tramp fleet. The objective of the problem is to serve a known set of single trip cargo contracts, observing time window constraints at both origin and destination of cargoes, while minimizing total operating cost. A distinctive aspect of the methodology is that time windows for picking and delivering cargoes are discretized. This approach allows for a broad variety of features and practical constraints to be implicitly included in the model. In particular, we consider problems where navigation speed can be used to control fuel consumption, which is a main operating cost in ocean shipping. We performed a computational study on three set of fifteen problem instances each, involving 30, 40 and 50 cargoes per instance, respectively. Each problem instance was solved with two fleet sizes, three levels of discretization, and with constant and variable speed. The numerical results show that our model presents a much better trade-off between solution quality and computing time than a similar constant speed continuous model. For example, discretizing the time windows in as few as 3 points, we obtained solutions that in average were no more than 0,8% worse than the best solution found by the continuous model. Computing time, on the other side, decreased in at least two orders of magnitude. The results also confirm that significant benefits might be obtained by incorporating the navigation speed as a controllable variable in the model.