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

Ricardo A. Gatica, Pablo A. Miranda

Resultado de la investigación: Article

21 Citas (Scopus)

Resumen

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.

Idioma originalEnglish
Páginas (desde-hasta)465-485
Número de páginas21
PublicaciónNetworks and Spatial Economics
Volumen11
N.º3
DOI
EstadoPublished - 1 sep 2011

Huella dactilar

Ships
Scheduling
Operating costs
Navigation
Freight transportation
Fuel consumption

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence

Citar esto

@article{86161e84f887447487985869e2fa3eeb,
title = "Special Issue on Latin-American Research: A Time Based Discretization Approach for Ship Routing and Scheduling with Variable Speed",
abstract = "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.",
keywords = "Navigation speed control, Ship routing and scheduling, Time windows discretization, Tramp fleet management",
author = "Gatica, {Ricardo A.} and Miranda, {Pablo A.}",
year = "2011",
month = "9",
day = "1",
doi = "10.1007/s11067-010-9132-9",
language = "English",
volume = "11",
pages = "465--485",
journal = "Networks and Spatial Economics",
issn = "1566-113X",
publisher = "Kluwer Academic Publishers",
number = "3",

}

TY - JOUR

T1 - Special Issue on Latin-American Research

T2 - A Time Based Discretization Approach for Ship Routing and Scheduling with Variable Speed

AU - Gatica, Ricardo A.

AU - Miranda, Pablo A.

PY - 2011/9/1

Y1 - 2011/9/1

N2 - 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.

AB - 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.

KW - Navigation speed control

KW - Ship routing and scheduling

KW - Time windows discretization

KW - Tramp fleet management

UR - http://www.scopus.com/inward/record.url?scp=80053922870&partnerID=8YFLogxK

U2 - 10.1007/s11067-010-9132-9

DO - 10.1007/s11067-010-9132-9

M3 - Article

AN - SCOPUS:80053922870

VL - 11

SP - 465

EP - 485

JO - Networks and Spatial Economics

JF - Networks and Spatial Economics

SN - 1566-113X

IS - 3

ER -