The multi-commodity network flow problem with soft transit time constraints
Application to liner shipping
METADATA ONLY
Loading...
Author / Producer
Date
2020-09
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The multi-commodity network flow problem (MCNF) consists in routing a set of commodities through a capacitated network at minimum cost and is relevant for routing containers in liner shipping networks. As commodity transit times are often a critical factor, the literature has introduced hard limits on commodity transit times. In practical contexts, however, these hard limits may fail to provide sufficient flexibility since routes with even tiny delays would be discarded. Motivated by a major liner shipping operator, we study an MCNF generalization where transit time restrictions are modeled as soft constraints, in which delays are discouraged using penalty functions of transit time. Similarly, early commodity arrivals can receive a discount in cost. We derive properties that distinguish this model from other MCNF variants and adapt a column generation procedure to efficiently solve it. Extensive numerical experiments conducted on realistic liner shipping instances reveal that the explicit consideration of penalty functions can lead to significant cost reductions compared to hard transit time deadlines. Moreover, the penalties can be used to steer the flow towards slower or faster configurations, resulting in a potential increase in operational costs, which generates a trade-off that we quantify under varying penalty functions.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
Publisher
IVT, ETH Zurich
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Networks; Multi-commodity flow; Column generation; Commodity transit time; Linear shipping application
Organisational unit
09611 - Corman, Francesco / Corman, Francesco
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG