Solving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demands
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 689-714.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016048
Classification : 90-08, 90B06, 90B50, 90C29
Mots clés : Vehicle routing, robust optimization, min-max criterion, multiobjective metaheuristics
Solano-Charris, Elyn L. 1 ; Prins, Christian 2 ; Santos, Andréa Cynthia 2

1 Escuela de Ciencias Económicas y Administrativas, Universidad de La Sabana, Km. 7, Autopista Norte, Chía (Cundinamarca), Colombia.
2 ICD-LOSI, UMR CNRS 6281, Université de Technologie de Troyes, 12 rue Marie Curie, CS 42060, 10004 Troyes cedex, France.
@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, Tome 50 (2016) no. 4-5, pp. 689-714. doi : 10.1051/ro/2016048. http://www.numdam.org/articles/10.1051/ro/2016048/

A. Agra, M. Christiansen, R. Figueiredo, L.M. Hvattum, M. Poss and C. Requejo, The robust vehicle routing problem with time windows. Comput. Oper. Res. 40 (2013) 856–866. | DOI | MR | Zbl

A. Ben-Tal and A. Nemirovski, Robust convex optimization. Math. Oper. Res. 23 (1998) 769–805. | DOI | MR | Zbl

D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. Ser. B 98 (2003) 49–71. | DOI | MR | Zbl

E. Cao, M. Lai and H. Yang, 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).

L. Davis, Applying adaptive algorithms to epistactic domains. Proc. of the International Joint Conference on Artificial Intelligence 1 (1985) 162–164.

K. Deb and H. Gupta, Introducing robustness in multi-objective optimization. Evol. Comput. J. 14 (2006) 463–494. | DOI

K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, 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

C.E. Gounaris, W. Wiesemann and C.A. Floudas, The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61 (2013) 677–693. | DOI | MR | Zbl

J. Han, C. Lee and S. Park, A robust scenario approach for the vehicle routing problem with uncertain travel times. Transportation Sci. 48 (2013) 373–390. | DOI

N. Jozefowiez, F. Semet and E.-G. Talbi, An evolutionary algorithm for the vehicle routing problem with route balancing. Eur. J. Oper. Res. 195 (2009) 761–769. | DOI | Zbl

N. Jozefowiez, F. Semet and E.-G. Talbi, 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

P. Lacomme, C. Prins and M. Sevaux, A genetic algorithm for a bi-objective capacitated arc routing problem. Comput. Oper. Res. 33 (2006) 3473–3493. | DOI | Zbl

C. Lee, K. Lee and S. Park, Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J. OR Society 63 (2012) 1294–1306.

B.F. Moghaddam, R. Ruiz and S.J. Sadjadi, 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.

W. Orgryczak, On the lexicographic minimax approach to location problems. Eur. J. Oper. Res. 100 (1997) 566–585. | DOI | Zbl

A.C. Santos, D.R. Lima and D.J. Aloise, 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

E.L. Solano-Charris, C. Prins and A.C. Santos, Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Appl. Soft Comput. 32 (2015) 518–531. | DOI

M.M. Solomon, Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research 35 (1987) 254–265. | DOI | MR | Zbl

I. Sungur, F. Ordóñez and M. Dessouky, 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

E. Zitzler, L. Thiele, M. Laumanns, C.M. Fonseca and V.G. Da Fonseca, Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7 (2003) 117–132. | DOI

Cité par Sources :