Optimization Online


The Continuous Time Service Network Design Problem

Natashia Boland(natashia.boland***at***isye.gatech.edu)
Michael Hewitt(mhewitt3***at***luc.edu)
Luke Marshall(luke.jonathon.marshall***at***gmail.com)
Martin Savelsbergh(martin.savelsbergh***at***isye.gatech.edu)

Abstract: Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time, i.e., the carrier must solve a Service Network Design problem. Most service network design models rely on discretization of time, i.e., instead of determining the exact time at which a dispatch should occur, the model determines a time interval during which a dispatch should occur. While the use of time discretization is widespread in service network design models, a fundamental question related to its use has never been answered: ``Is it possible to produce an optimal continuous time solution without explicitly modeling each point in time?'' We answer this question in the affirmative. We develop an iterative refinement algorithm using partially time-expanded networks that solves continuous time service network design problems. An extensive computational study demonstrates that the algorithm is not only of theoretical interest, but also performs well in practice.

Keywords: service network design, time-expanded network, iterative refinement

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 01/05/2015
Entry Accepted: 01/08/2015
Entry Last Modified: 01/05/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society