A Simultaneous Magnanti-Wong Method to Accelerate Benders Decomposition for the Metropolitan Container Transportation Problem

• 成果类型: Article; Early Access
• 署名作者: Perrykkad, Andrew; Ernst, Andreas T.; Krishnamoorthy, Mohan
• 署名单位: Monash University; University of Queensland
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2032
• 发表日期: 2022
• 关键词: delivery problem; drayage problem; time windows; MODEL; truck; algorithms; pickup

摘要

In most Australian cities, container ports are located close to the city, with transportation to and from the port facilitated by trucks. Recently, with a view to reducing container-truck induced city congestion and pollution, state and federal governments have begun championing a modal switch to short-haul rail for these transportation tasks. In this paper, we describe a metropolitan container transportation problem arising from this context that seeks to effectively leverage both modes of transport from a least-cost perspective. We propose a mathematical programming formulation and develop a new modified Benders decomposition method for the problem. We show that the simultaneous Magnanti-Wong method finds Pareto-optimal cuts by solving an augmented version of the subproblem that exploits subproblem dual-degeneracy without destroying its underlying structure. Computational results demonstrate the effectiveness of this routine over the performance of commercial solver implementations of the mathematical programming formulation.