Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery

Frank Hennig, Bjørn Nygreen and Marco E. Lübbecke

Naval Research Logistics (NRL), 2012, vol. 59, issue 3‐4, 298-310

Abstract: The split pickup split delivery crude oil tanker routing and scheduling problem is a difficult combinatorial optimization problem, both theoretically and practically. However, because of the large expenses in crude oil shipping it is attractive to make use of optimization that exploits as many degrees of freedom as possible to save transportation cost. We propose a nested column generation algorithm for this particular split pickup split delivery problem which bears several complexities such as a heterogeneous fleet, multiple commodities, many‐to‐many relations for pickup and delivery of each commodity, sequence dependent vehicle capacities, and cargo quantity dependent pickup and delivery times. Our approach builds on a branch‐and‐price algorithm in which the column generation subproblems are solved by branch‐and‐price themselves. We describe our implementation in the branch‐cut‐and‐price framework SCIP and give computational results for realistic test instances. The high quality schedules we obtain for these instances improve on those in previous studies. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1002/nav.21489

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:wly:navres:v:59:y:2012:i:3-4:p:298-310

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().