Minimizing the total weighted delivery time in container transportation scheduling

Kangbok Lee, Byung Cheon Choi, Joseph Y.T. Leung, Michael L. Pinedo, Dirk Briskorn

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We consider the problem of transporting containers from one port to another using a fleet of ships. Each ship has a capacity constraint that limits the total number of containers it can carry; each ship calls on a specific set of ports that is referred to as its route and each ship follows a fixed route with a fixed departure time at each port. Each container has a release date, that is, the date when it becomes available for shipping at its origination port; it cannot be loaded onto a ship before its release date. Also, each container has an importance factor referred to as its weight. The delivery time of a container is defined as the time when the container is delivered by a ship at its destination port. We consider the problem of minimizing the total weighted delivery times over all containers. We consider three scenarios with regard to the routes of the ships, namely, (i) identical routes, (ii) nested routes, and (iii) arbitrary routes. We determine the computational complexity of the problems and provide heuristics with their worst-case analyses.

Original languageEnglish (US)
Pages (from-to)266-277
Number of pages12
JournalNaval Research Logistics
Volume59
Issue number3-4
DOIs
StatePublished - Apr 1 2012

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Keywords

  • computational complexity
  • container scheduling
  • polynomially solvable
  • strongly NP-hard
  • total weighted delivery time

Fingerprint Dive into the research topics of 'Minimizing the total weighted delivery time in container transportation scheduling'. Together they form a unique fingerprint.

Cite this