A robust optimization approach for the vehicle routing problem with selective backhauls. (April 2020)

• Record Type: Journal Article
• Authors: Santos, Maria João; Curcio, Eduardo; Mulati, Mauro Henrique; Amorim, Pedro; Miyazawa, Flávio Keidi
• Is Part Of: Transportation research. Volume 136(2020)
• Publication Date: 2020-04
• Subjects: Vehicle routing problem with selective backhauls -- Robust optimization -- Branch-and-cut -- Adaptive large neighborhood search; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2020.101888
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: A VRPB under uncertainty is analyzed for first time. Four different methods are compared to estimate probability of constraint violation. An efficient metaheuristic provides high quality solutions for large instances. Abstract: The Vehicle Routing Problem with Selective Backhauls (VRPSB) aims to minimize the total routing costs minus the total revenue collected at backhaul customers. We explore a VRPSB under uncertain revenues. A deterministic VRPSB is formulated as a mixed-integer programming problem and two robust counterparts are derived. A novel method to estimate the probabilistic bounds of constraint violation is designed. A robust metaheuristic is developed, requiring little time to obtain feasible solutions with average gap of 1.40%. The robust approach studied demonstrates high potential to tackle the problem, requiring similar computing effort and maintaining the same tractability as the deterministic modeling.