Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

The Service Network Scheduling Problem

Abstract : We consider the optimization problem of determining schedules for shipments on known paths within a terminal network in order to minimize vehicle transportation costs. We refer to this problem as the Service Network Scheduling Problem and present two mixed integer programming formulations of that problem. The first is based on the classical idea of a time-expanded network. The second formulation is new and is based on sets of shipment consolidations. We show both analytically and computationally that the consolidation-based formulation can be the superior of the two, but that its enumerative nature renders it ineffective for instances with large numbers of shipments. Thus, we present a column generation-based algorithm for solving the consolidation-based formulation that relies on solving relaxations that are integer programs. We demonstrate the superior performance of this algorithm with a computational study.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Fabien Lehuédé Connect in order to contact the contributor
Submitted on : Sunday, March 6, 2022 - 2:23:42 PM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM
Long-term archiving on: : Tuesday, June 7, 2022 - 6:09:26 PM


Files produced by the author(s)


  • HAL Id : hal-03710468, version 1


Mike Hewitt, Fabien Lehuédé. The Service Network Scheduling Problem. 2022. ⟨hal-03710468v1⟩



Record views


Files downloads