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

Luke Marshall (), Natashia Boland (), Martin Savelsbergh () and Mike Hewitt ()
Additional contact information
Luke Marshall: Microsoft Research, Redmond, Washington 98052;
Natashia Boland: Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Martin Savelsbergh: Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Mike Hewitt: Department of Information Systems and Supply Chain Management, Quinlan School of Business, Loyola University Chicago, Chicago, Illinois 60611

Transportation Science, 2021, vol. 55, issue 1, 29-51

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. [Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.], but generates smaller partially time-expanded models, produces high-quality solutions more quickly, and converges more quickly.

Keywords: service network design; time-expanded network; iterative refinement; dynamic discretization discovery (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.0994 (application/pdf)

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:inm:ortrsc:v:55:y:2021:i:1:p:29-51

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().