nach oben

Soft Computing

Erschienen in:

12.08.2015 | Focus

Decomposition-based multi-objective evolutionary algorithm for vehicle routing problem with stochastic demands

verfasst von: Sen Bong Gee, Willson Amalraj Arokiasami, Jing Jiang, Kay Chen Tan

Erschienen in: Soft Computing | Ausgabe 9/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Vehicle routing problem with stochastic demands (VRPSD) is a famous and challenging optimization problem which is similar to many real world problems. To resemble the real world scenario, total traveling distance, total driver remuneration, the number of vehicles used and the difference between driver remuneration are considered and formulated in the multi-objective optimization perspective. This paper aims to solve multi-objective VRPSD under the constraints of available time window and vehicle capacity using decomposition-based multi-objective evolutionary algorithm (MOEA/D) with diversity-loss-based selection method incorporates with local search and multi-mode mutation heuristics. We have also compared the optimization performance of the decomposition-based approach with the domination-based approach to study the difference between these two well-known evolutionary multi-objective algorithm frameworks. The simulation results have showed that the decomposition-based approach with diversity-loss-based selection method is able to maintain diverse output solutions.

Vorheriger Artikel Weight computation of criteria in a decision-making problem by knowledge measure with intuitionistic fuzzy set and interval-valued intuitionistic fuzzy set

Nächster Artikel Simplified scoring methods for HMM-based speech recognition

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ahmed F, Deb K (2013) Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms. Soft Comput 17(7):1283–1299CrossRef

Asafuddoula M, Ray T, Sarker R (2015) A decomposition-based evolutionary algorithm for many objective optimization. Evol Comput IEEE Trans 19(3):445–460CrossRef

Bertsimas DJ (1992) A vehicle routing problem with stochastic demand. Oper Res 40(3):574–585MathSciNetCrossRefMATH

Biesinger B, Hu B, Raidl GR (2015) A variable neighborhood search for the generalized vehicle routing problem with stochastic demands. In: Evolutionary computation in combinatorial optimization. Springer, Berlin, pp 48–60

Cheong C, Tan KC, Liu D, Lin C (2010) Multi-objective and prioritized berth allocation in container ports. Ann Oper Res 180(1):63–103MathSciNetCrossRefMATH

Deb K, Pratap A, Agrawal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197CrossRef

Deb K, Mohan M, Mishra S (2005) Evaluating the \(\varepsilon \)-domination based multiobjective evolutionary algorithm for a quick computation of pareto-optimal solutions. Evol Comput J 13(4):501–525CrossRef

Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints. Evol Comput IEEE Trans 18(4):577–601CrossRef

Dror M, Trudeau P (1986) Stochastic vehicle routing with modified savings algorithm. Eur J Oper Res 23(2):228–235MathSciNetCrossRefMATH

Durillo JJ, Nebro AJ (2011) Jmetal: a java framework for multi-objective optimization. Adv Eng Softw 42(10):760–771CrossRef

Feng L, Ong Y, Lim M, Tsang I (2014) Memetic search with inter-domain learning: a realization between cvrp and carp. Evol Comput IEEE Trans 99:1–1

Gee SB, Qiu X, Tan KC (2013) A novel diversity maintenance scheme for evolutionary multi-objective optimization. In: Intelligent data engineering and automated learning—IDEAL 2013. Springer, Berlin, pp 270–277

Gee SB, Tan KC (2014) Diversity preservation with hybrid recombination for evolutionary multiobjective optimization. In: Evolutionary computation (CEC), 2014 IEEE Congress on. IEEE, pp 1172–1178

Gee SB, Tan KC, Shim VA, Pal NR (2015) Online diversity assessment in evolutionary multiobjective optimization: a geometrical perspective. IEEE Trans Evol Comput 19(4):542–559. doi:10.1109/TEVC.2014.2353672

Goh CK, Tan KC (2009) Handling noise in evolutionary neural network design. In: Evolutionary multi-objective optimization in uncertain environments. Studies in Computational Intelligence, vol 186. Springer, Berlin, Heidelberg, pp 101–21. doi:10.1007/978-3-540-95976-2_4

Gupta A, Ong YS, Zhang A, Tan P (2015) A bi-level evolutionary algorithm for multi-objective vehicle routing problems with time window constraints. In: Handa H, Ishibuchi H, Ong YS, Tan KC (eds) Proceedings of the 18th Asia Pacific symposium on intelligent and evolutionary systems—Volume 2. Proceedings in adaptation, learning and optimization, vol 2. Springer International Publishing, Berlin, pp 27–38

Hastie T, Tibshirani R, Friedman J, Hastie T, Friedman J, Tibshirani R (2009) The elements of statistical learning, vol 2. Springer, BerlinCrossRefMATH

Heng CK, Zhang AN, Tan PS, Ong YS (2015) Multi-objective heterogeneous capacitated vehicle routing problem with time windows and simultaneous pickup and delivery for urban last mile logistics. In: Proceedings of the 18th Asia Pacific symposium on intelligent and evolutionary systems, vol 1. Springer, Berlin, pp 129–140

Hoff A, Andersson H, Christiansen M, Hasle G, Løkketangen A (2010) Industrial aspects and literature survey: fleet composition and routing. Comput Oper Res 37(12):2041–2061MathSciNetCrossRefMATH

Jain H, Deb K (2014) An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part ii: handling constraints and extending to an adaptive approach. Evol Comput IEEE Trans 18(4):602–622CrossRef

Kallehauge B, Larsen J, Madsen O, Solomon M (2005) Vehicle routing problem with time windows. In: Desaulniers G, Desrosiers J, Solomon M (eds) Column generation. Springer, US, pp 67–98CrossRef

Liu H, Gu F, Zhang Q (2014) Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. Evol Comput IEEE Trans 18(3):450–455CrossRef

Li H, Zhang Q (2009) Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput 13:284–301CrossRef

Marinakis Y, Marinaki M (2014) Combinatorial neighborhood topology bumble bees mating optimization for the vehicle routing problem with stochastic demands. Soft Comput 19(2):353–373CrossRef

Marinakis Y, Marinaki M, Spanou P (2015) A memetic differential evolution algorithm for the vehicle routing problem with stochastic demands. In: Fister I, Fister Jr I (eds) Adaptation and hybridization in computational intelligence, adaptation, learning, and optimization, vol 18. Springer International Publishing, Berlin, pp 185–204

Mei Y, Li X, Yao X (2014) Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems. Evol Comput IEEE Trans 18(3):435–449CrossRef

Nguyen S, Zhang M, Johnston M, Tan KC (2014) Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming. Evol Comput IEEE Trans 18(2):193–208CrossRef

Perez D, Togelius J, Samothrakis S, Rohlfshagen P, Lucas SM (2014) Automated map generation for the physical traveling salesman problem. Evol Comput IEEE Trans 18(5):708–720CrossRef

Russo L, Francisco AP (2014) Quick hypervolume. Evol Comput IEEE Trans 18(4):481–502CrossRef

Sabar NR, Ayob M, Kendall G, Qu R (2013) Grammatical evolution hyper-heuristic for combinatorial optimization problems. Evol Comput IEEE Trans 17(6):840–861CrossRef

Sabar N, Ayob M, Kendall G, Qu R (2015) Automatic design of a hyper-heuristic framework with gene expression programming for combinatorial optimization problems. Evol Comput IEEE Trans 19(3):309–325CrossRef

Tan KC, Lee TH, Chew YH, Lee LH (2003) A multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. In: Systems, man and cybernetics, 2003. IEEE international conference on, vol 1. IEEE, pp 361–366

Tan KC, Tang H, Yi Z (2004) Global exponential stability of discrete-time neural networks for constrained quadratic optimization. Neurocomputing 56:399–406CrossRef

Tan KC, Tang H, Ge S (2005) On parameter settings of hopfield networks applied to traveling salesman problems. Circuits Syst I Regul Pap IEEE Trans 52(5):994–1002MathSciNetCrossRef

Tan KC, Chew Y, Lee LH (2006a) A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems. Eur J Oper Res 172(3):855–885MathSciNetCrossRefMATH

Tan KC, Yu Q, Ang JH (2006b) A coevolutionary algorithm for rules discovery in data mining. Int J Syst Sci 37(12):835–864MathSciNetCrossRefMATH

Tan KC, Cheong CY, Goh CK (2007) Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. Eur J Oper Res 177(2):813–839CrossRefMATH

Tan KC, Teoh EJ, Yu Q, Goh KC (2009) A hybrid evolutionary algorithm for attribute selection in data mining. Expert Syst Appl 36(4):8616–8630CrossRef

Tang H, Tan KC, Yi Z (2004) A columnar competitive model for solving combinatorial optimization problems. Neural Netw IEEE Trans 15(6):1568–1574CrossRef

Tan KC, Li Y (2002) Grey-box model identification via evolutionary computing. Control Eng Pract 10(7):673–684CrossRef

Van Veldhuizen DA, Lamont GB (1999) Multiobjective evolutionary algorithm test suites. In: Proceedings of the 1999 ACM symposium on applied computing. ACM, pp 351–357

Wang R, Purshouse RC, Fleming PJ (2013) Preference-inspired coevolutionary algorithms for many-objective optimization. Evol Comput IEEE Trans 17(4):474–494CrossRef

Wang J, Tang K, Lozano J, Yao X (2015) Estimation of distribution algorithm with stochastic local search for uncertain capacitated arc routing problems. Evolutionary Computation, IEEE Transactions on PP(99):1–1

Woodruff M, Herman J (2013) pareto.py: A \(\varepsilon \)-nondomination sorting routine. https://github.com/matthewjwoodruff/pareto.py

Yang S, Li M, Liu X, Zheng J (2013) A grid-based evolutionary algorithm for many-objective optimization. Evol Comput IEEE Trans 17(5):721–736CrossRef

Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11:712–731CrossRef

Zhou A, Jin Y, Zhang Q, Sendhoff B, Tsang E, (2006) Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. In: Evolutionary computation (2006) CEC 2006. IEEE Congress on. IEEE, pp 892–899

Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—A comparative case study. In: Parallel problem solving from nature—PPSN V. Springer, Berlin, pp 292–301

Titel: Decomposition-based multi-objective evolutionary algorithm for vehicle routing problem with stochastic demands
verfasst von: Sen Bong Gee
Willson Amalraj Arokiasami
Jing Jiang
Kay Chen Tan
Publikationsdatum: 12.08.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 9/2016
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-015-1830-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 9/2016

Chaotic cuckoo search

Weight computation of criteria in a decision-making problem by knowledge measure with intuitionistic fuzzy set and interval-valued intuitionistic fuzzy set

Model approach to grammatical evolution: theory and case study

MFlexDT: multi flexible fuzzy decision tree for data stream classification

$$H_\infty $$ H ∞ state estimation of stochastic neural networks with mixed time-varying delays

Use of line based symmetry for developing cluster validity indices