Optimization Online


Interval-based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem

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

Abstract: We introduce an effective and efficient iterative algorithm for solving the Continuous-Time Service Network Design Problem. The algorithm achieves its efficiency by carefully and dynamically refining partially time-expanded network models so that only a small number of small integer programs, defined over these networks, need to be solved. An extensive computational study shows that the algorithm performs well in practice, often using time-expanded network models with size much less than 1% (in terms of number of variables and constraints) of a full time-expanded network model. The algorithm is inspired by and has many similarities to the dynamic discretization discovery algorithm introduced in Boland et al. (2017) [The Continuous-Time Service Network Design Problem. Operations Research], but generates smaller partially time-expanded models, produces high-quality solutions more quickly, and converges faster.

Keywords: service network design; time-expanded network; iterative refinement, dynamic discretization discovery

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

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


Download: [PDF]

Entry Submitted: 10/24/2018
Entry Accepted: 10/24/2018
Entry Last Modified: 01/30/2019

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