Routing and Scheduling on a Shoreline with Release Times

Harilaos N. Psaraftis, Marius M. Solomon, Thomas L. Magnanti and Tai-Up Kim
Additional contact information
Harilaos N. Psaraftis: Department of Ocean Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Marius M. Solomon: Management Science Department, Northeastern University, Boston, Massachusetts 02115
Thomas L. Magnanti: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Tai-Up Kim: Kion Technology Inc., Seoul, Republic of Korea

Management Science, 1990, vol. 36, issue 2, 212-223

Abstract: In this paper we examine computational complexity issues and develop algorithms for a class of "shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective, these problems arise in several transportation environments. For instance, in the routing and scheduling of cargo ships, the routing structure is "easy" because the ports to be visited are usually located along a shoreline. However, because release times of cargoes at ports generally complicate the routing structure, the combined routing and scheduling problem is nontrivial. For the straight-line case (a restriction of the shoreline case), our analysis shows that the problem of minimizing the maximum completion time can be solved exactly in quadratic time by dynamic programming. For the shoreline case we develop and analyze heuristic algorithms. We derive data-dependent worst-case performance ratios for these heuristics that are bounded by constant. We also discuss how these algorithms perform on practical data.

Keywords: routing problems; dynamic programming; analysis of heuristics (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.36.2.212 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:36:y:1990:i:2:p:212-223

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().