In this paper, a bi-objective Vehicle Routing Problem (bi-RVRP) with uncertainty in both demands and travel times is studied by means of robust optimization. Uncertain demands per customer are modeled by a discrete set of scenarios representing the deviations from an expected demand, while uncertain travel times are independent from customer demands. Then, traffic records are considered to get discrete scenarios to each arc of the transportation network. Here, the bi-RVRP aims at minimizing the worst total cost of traversed arcs and minimizing the maximum total unmet demand over all scenarios. As far as we know, this is the first study for the bi-RVRP which finds practical applications in urban transportation, e.g., serving small retail stores. To solve the problem, different variations of solution approaches, coupled with a local search procedure are proposed: the Multiobjective Evolutionary Algorithm (MOEA) and the Non-dominated Sorting Genetic Algorithm (NSGAII). Different metrics are used to measure the algorithmic performance, the convergence, as well as the diversity of solutions for the different methods.
Accepté le :
DOI : 10.1051/ro/2016048
Mots-clés : Vehicle routing, robust optimization, min-max criterion, multiobjective metaheuristics
@article{RO_2016__50_4-5_689_0,
author = {Solano-Charris, Elyn L. and Prins, Christian and Santos, Andr\'ea Cynthia},
title = {Solving the bi-objective {Robust} {Vehicle} {Routing} {Problem} with uncertain costs and demands},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {689--714},
publisher = {EDP-Sciences},
volume = {50},
number = {4-5},
year = {2016},
doi = {10.1051/ro/2016048},
zbl = {1353.90006},
mrnumber = {3570525},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2016048/}
}
TY - JOUR AU - Solano-Charris, Elyn L. AU - Prins, Christian AU - Santos, Andréa Cynthia TI - Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 689 EP - 714 VL - 50 IS - 4-5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016048/ DO - 10.1051/ro/2016048 LA - en ID - RO_2016__50_4-5_689_0 ER -
%0 Journal Article %A Solano-Charris, Elyn L. %A Prins, Christian %A Santos, Andréa Cynthia %T Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 689-714 %V 50 %N 4-5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016048/ %R 10.1051/ro/2016048 %G en %F RO_2016__50_4-5_689_0
Solano-Charris, Elyn L.; Prins, Christian; Santos, Andréa Cynthia. Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 689-714. doi : 10.1051/ro/2016048. http://www.numdam.org/articles/10.1051/ro/2016048/
, , , , and , The robust vehicle routing problem with time windows. Comput. Oper. Res. 40 (2013) 856–866. | DOI | MR | Zbl
and , Robust convex optimization. Math. Oper. Res. 23 (1998) 769–805. | DOI | MR | Zbl
and , Robust discrete optimization and network flows. Math. Program. Ser. B 98 (2003) 49–71. | DOI | MR | Zbl
, and , Open vehicle routing problem with demand uncertainty and its robust strategies. Expert Systems with Applications 41 (2014) 3569–3575. | DOI
A.A. Coco, E.L. Solano-Charris, A.C. Santos, C. Prins and T. Noronha, Robust optimization criteria: state-of-the-art and new issues. Technical Report UTT-LOSI-14001, ISSN 2266-5064. Université de Technologie de Troyes (2014).
, Applying adaptive algorithms to epistactic domains. Proc. of the International Joint Conference on Artificial Intelligence 1 (1985) 162–164.
and , Introducing robustness in multi-objective optimization. Evol. Comput. J. 14 (2006) 463–494. | DOI
, , and , A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6 (2002) 182–197. | DOI
D.E Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley (1989). | Zbl
C.E. Gounaris, P.P. Repoussis, C.D. Tarantilis, W. Wiesemann and C.A. Floudas, An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transportation Science. Preprint (2014). | DOI
, and , The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61 (2013) 677–693. | DOI | MR | Zbl
, and , A robust scenario approach for the vehicle routing problem with uncertain travel times. Transportation Sci. 48 (2013) 373–390. | DOI
, and , An evolutionary algorithm for the vehicle routing problem with route balancing. Eur. J. Oper. Res. 195 (2009) 761–769. | DOI | Zbl
, and , An evolutionary algorithm for the vehicle routing problem with route balancing. Eur. J. Oper. Res. 195 (2009) 761–769. | DOI | Zbl
P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Kluwer Academic Publishers, Norwell, MA (1997). | MR | Zbl
, and , A genetic algorithm for a bi-objective capacitated arc routing problem. Comput. Oper. Res. 33 (2006) 3473–3493. | DOI | Zbl
, and , Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J. OR Society 63 (2012) 1294–1306.
, and , Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Comput. Industrial Eng. (2012) 62 306–317. | DOI
T. Murata, H. Nozawa, H. Ishibuchi and M. Gen, Modification of local search directions for non-dominated solutions in cellular multiobjective genetic algorithms for pattern classification problems. In Evolutionary Multi-Criterion Optimization. Vol. 2632 of Lect. Notes Comput. Sci. Springer Berlin Heidelberg (2003) 593–607. | Zbl
M. Noorizadegan, L. Galli and B. Chen, On the heterogeneous vehicle routing problem under demand uncertainty. In 21st International Symposium on Mathematical Programming (2012) 1–25.
F. Ordóñez, Robust Vehicle Routing. Chap. 8 (2010) 153–178.
, On the lexicographic minimax approach to location problems. Eur. J. Oper. Res. 100 (1997) 566–585. | DOI | Zbl
, and , Modeling and solving the bi-objective minimum diameter-cost spanning tree problem. J. Global Optim. 60 (2013) 1–22. | MR | Zbl
J.R. Schott, Fault tolerant design using single and multicriteria genetic algorithm optimization. Master’s thesis, Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics (1995).
A. Shapiro, S. Dentcheva and A. Ruszczyński, Lectures on stochastic programming: Modeling and Theory, vol. 9. Philadelphia, USA (2008). | MR | Zbl
E.L. Solano-Charris, C. Prins and A.C. Santos, Heuristic approaches for the robust vehicle routing problem. In Combinatorial Optimization. Lect. Notes Comput. Sci. Springer International Publishing (2014) 384–395 | MR
, and , Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Appl. Soft Comput. 32 (2015) 518–531. | DOI
, Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research 35 (1987) 254–265. | DOI | MR | Zbl
, and , A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40 (2008) 509–523. | DOI
N.E. Toklu, R. Montemanni and L.M. Gambardella, An ant colony system for the capacitated vehicle routing problem with uncertain travel costs. In IEEE Symposium on Swarm Intelligence (SIS) (2013) 32–39.
N.E. Toklu, R. Montemanni and L.M. Gambardella, A robust multiple ant colony system for the capacitated vehicle routing problem. In IEEE International Conference on Systems, Man, and Cybernetics (SMC) (2013) 1871–1876.
R.J.B. Wets, Stochastic programming models: Wait-and-see versus here-and-now. In Decision Making Under Uncertainty. Vol. 128 of The IMA Vol. Math. Appl. Springer, New York (2002) 1–15. | MR | Zbl
, , , and , Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7 (2003) 117–132. | DOI
Cité par Sources :
