The Continuous-Time Service Network Design Problem

• 成果类型: Article
• 署名作者: Boland, Natashia; Hewitt, Mike; Marshall, Luke; Savelsbergh, Martin
• 署名单位: University System of Georgia; Georgia Institute of Technology; Loyola University Chicago
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1624
• 发表日期: 2017
• 页码: 1303-1321
• 关键词: cycle-based neighborhoods; dynamic flows; branch; price

摘要

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 not only is of theoretical interest but also performs well in practice.