More Web Proxy on the site http://driver.im/

article

An adaptive evolutionary approach for real-time vehicle routing and dispatching

Authors:

Mohamed Barkaoui,

Michel GendreauAuthors Info & Claims

Computers and Operations Research, Volume 40, Issue 7

Pages 1766 - 1776

https://doi.org/10.1016/j.cor.2013.01.022

Published: 01 July 2013 Publication History

Abstract

The quality of the convergence process in genetic algorithms depends on the specific choice of strategies and combinations of operators. In this paper, we address this problem and introduce an adaptive evolutionary approach that uses a genetic algorithm in an adaptive process. An application of this approach to the dynamic vehicle routing problem with time windows is presented. We compare the adaptive version of a hybrid genetic algorithm with the non-adaptive one with respect to the robustness and the quality of the generated solutions. The results obtained show the ability of our operator combination adaptation approach to produce solutions that are superior to hand-tuning and other adaptive methods with respect to performance sensitivity and robustness.

References

[1]

Eiben, A.E., Hinterding, R. and Michalewicz, Z., Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation. v3 i2. 124-141.

Digital Library

[2]

Eiben, A.E. and Smith, J.E., Introduction to evolutionary computing. 2003. Springer, Berlin Heidelberg.

[3]

Ho, CW, Lee KH, Leung KS. A genetic algorithm based on mutation and crossover with adaptive probabilities. In: Proceedings of the 1999 congress, evolutionary computation, 1. Washington, DC, USA. p. 768-775.

[4]

Julstrom BA. What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. In: L.J. Eshelman, editor, Proceedings of the sixth international conference on genetic algorithms and their applications. Pittsburgh, PA; 1995, p. 81-87.

Digital Library

[5]

Julstrom BA. Adaptive operator probabilities in a genetic algorithm that applies three operators. In: Proceedings of the 1997 ACM symposium on applied computing (SAC '97). San Jose, California, USA. p. 233-238.

Digital Library

[6]

Tuson A, Ross P. Cost based operator rate adaptation: an investigation. In: Proceedings of the 4th international conference on parallel problem solving from nature (PPSN IV). Springer Verlag; 1996. p. 461-469.

Digital Library

[7]

Hong I, Kahng AB, Moon BR. Exploiting synergies of multiple crossovers: initial studies. In: Proceedings of the second IEEE conference on evolutionary computation. Piscataway, NJ: IEEE Press; 1995. p. 245-250.

[8]

Spears WM. Adapting crossover in evolutionary algorithms. In: Proceedings of the 4th annuual conference on evolutionary programming. Cambridge, MA, USA; 1995. p. 367-384.

[9]

Yoon, H.S. and Moon., B.R., An empirical study on the synergy of multiple crossover operators. IEEE Transactions on Evolutionary Computation. v6 i2. 212-223.

Digital Library

[10]

Derigs U, Kabath M, Zils M. Adaptive genetic algorithms: a new approach for solving nonstandard vehicle routing problems efficiently. In: Kischka P, Lorenz H-W, Derigs U, Domschke W, Kleinschmidt P, Möhring R, editors. Operations Research Proceedings; 1997, p. 539-544.

[11]

Tuson, A. and Ross, P., Adapting operator settings in genetic algorithms. Evolutionary Computation. v6 i2. 84-161.

Digital Library

[12]

Landgraaf, W.A., Eiben, A.E. and Nannen, V., Parameter calibration using meta-algorithms. IEEE Congress on Evolutionary Computation. 71-78.

[13]

Cortez P, Rocha M, Neves J. A meta-genetic algorithm for time series forecasting. In: Torgo L, editor. Proceedings of workshop on artificial intelligence techniques for financial time series analysis (AIFTSA-01), 10th Portuguese conference on artificial intelligence (EPIA'01). Oporto, Portugal; 2001. p. 21-31.

[14]

Grefenstette, J., Optimization of control parameters for genetic algorithms. IEEE Transaction on on Systems, Man and Cybernetics. v16 i1. 122-128.

Digital Library

[15]

Lee M, Takagi H. Integrating design stage of fuzzy systems using genetic algorithms. In: Proceedings of the second IEEE international conference on fuzzy systems. vol. 1; 1993. p. 612-617.

[16]

Nannen V, Eiben AE. Relevance estimation and value calibration of evolutionary algorithm parameters. In: Proceedings of the international joint conference on artificial intelligence (IJCAI); 2007, p. 975-980.

Digital Library

[17]

Samsonovich, AV, Jong KAD. Pricing the 'Free Lunch' of meta-evolution. In: Beyer H-G, O'Reilly U-M, editors. GECCO 2005. Proceedings of the 2005 conference on genetic and evolutionary computation. New York, NY, USA. p. 1355-1362.

Digital Library

[18]

Shahookar, K. and Mazumder., P., VLSI cell placement techniques. ACM Computing Surveys. v23 i2. 143-220.

Digital Library

[19]

Clune J, Goings S, Punch B, Goodman E. Investigations in Meta-GAs: panaceas or pipe dreams? Proceedings of the genetic and evolutionary computation conference (GECCO). Washington, D.C, USA; 2005, p. 235-241.

Digital Library

[20]

Wang G, Dexter T, Goodman E, Punch W. Optimization of a GA and within the GA for a 2-dimensional layout problem. In: Proceedings of the first international conference on evolutionary computation and its applications. Presidium, Russian Academy of Sciences; 1996. p. 18-29

[21]

Wang, G., Goodman, E. and Punch, W., On the optimization of a class of blackbox optimization algorithms. Technical report, GARAGe/Case Center. 1997. Michigan State University, USA.

[22]

Smith, J.E., Co-evolving memetic algorithms: a review and progress report. IEEE Transactions in Systems, Man and Cybernetics, Part B. v37 i1. 6-17.

Digital Library

[23]

Takashima E, Murata Y, Shibata N, Ito M. Self adaptive island GA. In: Proceedings of the 2003 congress on evolutionary computation (CEC 2003). p. 1072-1079.

[24]

Fialho A, Da Costa L, Schoenauer M, Sebag M. Extreme value based adaptive operator selection. In: Proceedings of the 10th international conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer-Verlag; 2008, p. 175-184.

[25]

Fialho A, Da Costa L, Schoenauer M, Sebag M. Dynamic multi-armed bandits and extreme value-based rewards for adaptive operator selection. In: Procceeding of learning and intelligent optimization (LION-3). Springer-Verlag; 2009.

Digital Library

[26]

Thierens, D., Adaptive strategies for operator allocation. 2007. Studies in Computational Intelligence (SCI), 2007.Springer-Verlag, Berlin Heidelberg.

[27]

Murata, T, Ishibuchi H. Positive and negative combination effects of crossover and mutation operators in sequencing problems. In: Proceedings of the IEEE international conference on evolutionary computation. Nagoya, Japan; 1996. p. 170-175.

[28]

Herrera, F. and Lozano, M., Adaptive genetic operators based on coevolution with fuzzy behaviors. IEEE Transactions on Evolutionary Computation. v5 i2. 149-165.

Digital Library

[29]

Oltean, M., Evolving evolutionary algorithms using linear genetic programming. 2005. Evolutionary Computation, 2005.MIT Press, MA, USA.

Digital Library

[30]

DeJong KA. Parameter Setting in EAs: A 30 Year Perspective. Parameter Setting in Evolutionary Algorithms. Heidelberg; 2007. p. 1-18.

[31]

Gendreau, M., Guertin, F., Potvin, J.-Y. and Taillard, í¿.D., Parallel tabu search for real-time vehicle routing and dispatching. Transportation Science. v33 i4. 381-390.

Digital Library

[32]

Berger, J. and Barkaoui., M., A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research. v31 iIssue 12. 2037-2053.

[33]

Gendreau, M Potvin J-Y. editors. Transportation Science, volume 4. INFORMS. Special issue on real-time Weet management; 2004.

Digital Library

[34]

Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R., Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research. v151 i1. 1-11.

[35]

Ichoua, S., Gendreau, M. and Potvin, J.-Y., Planned route optimization for real-time vehicle routing. In: Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., Minis, I. (Eds.), Dynamic Fleet Management, Volume 38 of Operations Research/Computer Science Interfaces, Springer, US. pp. 1-18.

[36]

Larsen A, Madsen OBG, Solomon MM. Recent developments in dynamic vehicle routing systems. In: Golden BL, Raghavan S, Wasil EA, editors. The vehicle routing problem: latest advances and new challenges. Springer; 2008. p. 199-218.

[37]

Pillac V, Gendreau M, Guéret C, Medaglia AL. A review of dynamic vehicle routing problems. European Journal of Operational Research 2013;225(1):1-11.

[38]

. In: Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., Minis, I. (Eds.), Dynamic fleet management, volume 38 of operations research computer science interfaces series, Springer, US.

[39]

Pillac V, Gendreau M, Guéret C, Medaglia A. A review of dynamic vehicle routing problems. Technical Report CIRRELT-2011-62, Centre interuniversitaire de recherche sur les réseaux d'enterprise, la logistique et le transport (CIRRELT). Montreal, Canada; 2011.

[40]

Schaffer DJ, Caruana RA, Eshelmna LJ, Das R. A study of control parameters affecting online performance of genetic algorithms for function optimization. In: Proceedings of the third international conference on genetic algorithms. San Mateo, CA; 1989. p. 51-60.

Digital Library

[41]

Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning. 1989. Addison-Wesley, New York, USA.

Digital Library

[42]

DeJong KA. Analysis of the behavior of a class of genetic adaptive systems. PhD thesis, Dept. Computer and Communication Sciences: Univ. of Michigan, MI, USA; 1975.

[43]

Liu, F.-H. and Shen, S.-Y., A route-neighborhood-based metaheuristic for vehicle routing problem with time windows. European Journal of Operational Research. v118. 485-504.

[44]

Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research. v35 i2. 254-265.

[45]

Berger J, Barkaoui M. An improved hybrid genetic algorithm for the vehicle routing problem with time windows. In: Proceeding of the international ICSC symposium on computational intelligence, part of the international ICSC congress on intelligent systems and applications. University of Wollongong, Wollongong: Australia; 2000.

[46]

Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems. 1998. Springer-Verlag, New York, USA.

[47]

Harvey WD, Ginsberg ML. Limited discrepancy search. In: Proceedings of the 14th international joint conference on artificial intelligence. Montreal, Canada; 1995.

Digital Library

[48]

Osman, I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research. v41. 421-451.

Digital Library

[49]

Wall, M, . 1995. MIT, Boston, USA.

Cited By

Elshaer RAwad H(2022)A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variantsComputers and Industrial Engineering10.1016/j.cie.2019.106242140:COnline publication date: 21-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2019.106242
da Silva Júnior OLeal JReimann M(2021)A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windowsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-020-05350-425:4(2935-2948)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s00500-020-05350-4
Bossek JGrimme CTrautmann HCoello Coello C(2020)Dynamic bi-objective routing of multiple vehiclesProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390146(166-174)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390146
Show More Cited By

An adaptive evolutionary approach for real-time vehicle routing and dispatching
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Dynamic vehicle routing using genetic algorithms

Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic ...
A dynamic vehicle routing problem based on real-time traffic information

We treat the dynamic vehicle routing problem with time windows (DVRPTW) in the context of real-time traffic information. We integrate traffic information obtained in real time to change the speed profile according to the accidents on the road network (...
Adaptive probabilities of crossover and mutation in genetic algorithm for solving stochastic vehicle routing problem

The vehicle routing problem vehicle routing problem, VRP in remainder of this paper is a combinatorial optimisation problem and operational research. It belongs to the category of transportation problems, as the travelling salesman problem travelling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 40, Issue 7

July, 2013

263 pages

ISSN:0305-0548

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2013.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 July 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Elshaer RAwad H(2022)A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variantsComputers and Industrial Engineering10.1016/j.cie.2019.106242140:COnline publication date: 21-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2019.106242
da Silva Júnior OLeal JReimann M(2021)A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windowsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-020-05350-425:4(2935-2948)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s00500-020-05350-4
Bossek JGrimme CTrautmann HCoello Coello C(2020)Dynamic bi-objective routing of multiple vehiclesProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390146(166-174)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390146
Bossek JGrimme CRudolph GTrautmann H(2020)Towards Decision Support in Dynamic Bi-Objective Vehicle Routing2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185778(1-8)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185778
Aleti AMoser I(2016)A Systematic Literature Review of Adaptive Parameter Control Methods for Evolutionary AlgorithmsACM Computing Surveys10.1145/299635549:3(1-35)Online publication date: 21-Oct-2016
https://dl.acm.org/doi/10.1145/2996355
Braekers KRamaekers KVan Nieuwenhuyse I(2016)The vehicle routing problemComputers and Industrial Engineering10.1016/j.cie.2015.12.00799:C(300-313)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.cie.2015.12.007
Psaraftis HWen MKontovas C(2016)Dynamic vehicle routing problemsNetworks10.1002/net.2162867:1(3-31)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1002/net.21628
Xu DXiao R(2015)An improved genetic clustering algorithm for the multi-depot vehicle routing problemInternational Journal of Wireless and Mobile Computing10.1504/IJWMC.2015.0716659:1(1-7)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1504/IJWMC.2015.071665
Taha Yassen EAyob MAhmad Nazri MSabar N(2015)Meta-harmony search algorithm for the vehicle routing problem with time windowsInformation Sciences: an International Journal10.1016/j.ins.2015.07.009325:C(140-158)Online publication date: 20-Dec-2015
https://dl.acm.org/doi/10.1016/j.ins.2015.07.009
Barkaoui MBerger JBoukhtouta A(2015)Customer satisfaction in dynamic vehicle routing problem with time windowsApplied Soft Computing10.1016/j.asoc.2015.06.03535:C(423-432)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.asoc.2015.06.035

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents