The price of discretizing time: a study in service network design

Natashia Boland, Mike Hewitt, Luke Marshall () and Martin Savelsbergh
Additional contact information
Natashia Boland: Georgia Institute of Technology
Mike Hewitt: Loyola University Chicago
Luke Marshall: Georgia Institute of Technology
Martin Savelsbergh: Georgia Institute of Technology

EURO Journal on Transportation and Logistics, 2019, vol. 8, issue 2, No 5, 195-216

Abstract: Abstract Researchers and practitioners have long recognized that many transportation problems can be naturally and conveniently modeled using time-expanded networks. In such models, nodes represent locations at distinct points in time and arcs represent possible actions, e.g., moving from one location to another at a particular point of time, or staying in the same location for a period of time. To use a time-expanded network, time must be discretized, i.e., the planning horizon is partitioned into discrete time intervals. The length of these intervals, therefore, must be chosen, and the parameters involving time, e.g., travel duration and due times, need to be mapped to these discrete intervals. Short intervals yield a high-quality approximation to the continuous-time problem, but typically induce a computationally intractable model; whereas long intervals can yield a computationally tractable, but low-quality model. The loss of quality is due to the approximation introduced by the mapping of parameters involving time. To guide researchers and practitioners in their use of time-expanded networks, we explore the choice of time discretization and its impact, by means of an extensive computational study on the service network design problem. The empirical results show that in some cases the loss of quality, i.e., the relative gap between the discretized and continuous-time optimal values, can be greater than 20%. We also investigate metrics that characterize and help identify instances that are likely to be sensitive to discretization and could incur a large loss of solution quality.

Keywords: Service network design; Time-space network; Time expanded network; Approximation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-018-0119-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:eurjtl:v:8:y:2019:i:2:d:10.1007_s13676-018-0119-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-018-0119-x

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().