Approximating the chance-constrained capacitated vehicle routing problem with robust optimization

Karina Thiebaut () and Artur Pessoa ()
Additional contact information
Karina Thiebaut: Universidade Federal Fluminense
Artur Pessoa: Universidade Federal Fluminense

4OR, 2023, vol. 21, issue 3, No 8, 513-531

Abstract: Abstract The Capacitated Vehicle Routing Problem (CVRP) is a classical combinatorial optimization problem that aims to serve a set of customers, using a set of identical vehicles, satisfying the vehicle capacities, and minimizing the total traveling distance. Among the possible approaches to extend the CVRP for handling uncertain demands, we highlight the robust optimization with budgeted uncertainty, and chance-constrained optimization. Another simpler and often omitted option is to apply the deterministic CVRP model over augmented demands in such a way to reduce the capacity violation probability. In this paper, we propose a suitable way to adjust the input data of both the deterministic CVRP and the robust CVRP with budgeted uncertainty so that the corresponding output approximates the chance-constrained CVRP for the case of independently normally distributed demands. In order to test our approach, we present quite extensive experiments showing that it leads to very small deviations with respect to the optimal chance-constrained solutions, and that the robust model brings significant benefits with respect to the deterministic one. In order to optimally solve the proposed chance-constrained benchmark instances, we also introduce a new technique to tighten a family of known inequalities for this problem.

Keywords: Vehicle routing; Uncertain demands; Chance-constraints; Robust optimization; Capacity cuts; 90C17; 90C11; 90C59 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00523-3 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:aqjoor:v:21:y:2023:i:3:d:10.1007_s10288-022-00523-3

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-022-00523-3

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().