A robust optimization approach for the road network daily maintenance routing problem with uncertain service time. (January 2016)

• Record Type: Journal Article
• Authors: Chen, Lu; Gendreau, Michel; Hà, Minh Hoàng; Langevin, André
• Is Part Of: Transportation research. Volume 85(2016)
• Page Start: 40
• Page End: 51
• Publication Date: 2016-01
• Subjects: Arc routing problem -- Robust optimization -- Uncertainty -- Chance-constrained programming -- Branch-and-cut -- Monte Carlo simulation; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2015.11.006
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: An arc routing problem with uncertain service times is studied. Robust optimization is applied to obtain routes being less sensitive to uncertainty. A branch-and-cut algorithm is developed to solve problems of real size. The behavior of the solutions is analyzed using Monte Carlo simulation. Abstract: This paper studies the robust optimization approach for the routing problem encountered in daily maintenance operations of a road network. The uncertainty of service time is considered. The robust optimization approach yields routes that minimize total cost while being less sensitive to substantial deviations of service times. A robust optimization model is developed and solved by the branch-and-cut method. In computational experiments, the behavior of the robust solutions and their performance are analyzed using Monte Carlo simulation. The robust optimization model is also compared with a classic chance-constrained programming model. The experimental analysis provides managerial insights for decision makers to determine an appropriate routing strategy.