Service type assignment and container routing with transit time constraints and empty container repositioning for liner shipping service networks

M. Hakan Akyüz, Chung-Yee Lee

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)

Abstract

A decision tool is developed for a liner shipping company to deploy its fleet considering vessel speeds and to find routes for cargos with repositioning of empty containers and transit time constraints. This problem is referred as the simultaneous Service type Assignment and container Routing Problem (SARP) in the sequel. A path-flow based mixed-integer linear programming formulation is suggested for the SARP. A Branch and Bound (BB) algorithm is used to solve the SARP exactly. A Column Generation (CG) procedure, embedded within the BB framework, is devised to solve the linear programming relaxation of the SARP. The CG subproblems arises as Shortest Path Problems (SPP). Yet incorporating transit time requirements yields constrained SPP which is NP-hard and solved by a label correcting algorithm. Computational experiments are performed on randomly generated test instances mimicking real life. The BB algorithm yields promising solutions for the SARP. The SARP with and without transit time constraints is compared with each other. Our results suggest a potential to increase profit margins of liner shipping companies by considering transit time requirements of cargos.

Original languageEnglish
Pages (from-to)46-71
Number of pages26
JournalTransportation Research. Part B: Methodological
Volume88
DOIs
Publication statusPublished - 1 Jun 2016
Externally publishedYes

Keywords

  • Container routing
  • Empty container repositioning
  • Fleet deployment
  • Liner shipping
  • Sailing speed
  • Transit times

Fingerprint Dive into the research topics of 'Service type assignment and container routing with transit time constraints and empty container repositioning for liner shipping service networks'. Together they form a unique fingerprint.

Cite this