Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Multi-environmental cooperative parallel metaheuristics for solving dynamic optimization problems

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

In dynamic optimization problems, changes occur over time. These changes could be related to the optimization objective, the problem instance, or involve problem constraints. In most cases, they are seen as an ordered sequence of sub-problems or environments that must be solved during a certain time interval. The usual approaches tend to solve each sub-problem when a change happens, dealing always with one single environment at each time instant. In this paper, we propose a multi-environmental cooperative model for parallel meta-heuristics to tackle dynamic optimization problems. It consists in dealing with different environments at the same time, using different algorithms that exchange information coming from these environments. A parallel multi-swarm approach is presented for solving the Dynamic Vehicle Routing Problem. The effectiveness of the proposed approach is tested on a well-known set of benchmarks, and compared with other meta-heuristics from the literature. Experimental results show that our multi-environmental approach outperforms conventional meta-heuristics on this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Algorithm 2
Fig. 2
Algorithm 3
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. http://paradiseo.gforge.inria.fr.

  2. https://www.grid5000.fr.

References

  1. Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley-Interscience, New York

    Book  MATH  Google Scholar 

  2. Blackwell T, Branke J (2004) Multi-swarm optimization in dynamic environments. In: Applications of evolutionary computing, Lecture notes in computer science. Springer, Berlin, pp 489–500

    Chapter  Google Scholar 

  3. Blackwell T (2007) Particle swarm optimization in dynamic environments. In: Evolutionary computation in dynamic and uncertain environments. Springer, Berlin, pp 29–49

    Chapter  Google Scholar 

  4. Branke J (2002) Evolutionary optimization in dynamic environments. Kluwer Academic, Dordrecht

    Book  MATH  Google Scholar 

  5. Cohen P, Kohavi R (1995) Empirical methods for artificial intelligence. MIT Press, Cambridge

    MATH  Google Scholar 

  6. Dantzig G, Ramser J (1959) The truck dispatching problem. Manage Sci 6(1):80–91

    Article  MathSciNet  MATH  Google Scholar 

  7. Ghiani G, Guerriero F, Laporte G, Musmanno R (2003) Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. Eur J Oper Res 151:1–11

    Article  MATH  Google Scholar 

  8. Grefenstette JJ (1992) Genetic algorithms for changing environments. In: Parallel problem solving from nature, pp 139–146

    Google Scholar 

  9. Haghani A, Jung S (2005) A dynamic vehicle routing problem with time-dependent travel times. Comput Oper Res 32(11):2959–2986

    Article  MATH  Google Scholar 

  10. Hanshar F, Ombuki-Berman B (2007) Dynamic vehicle routing using genetic algorithms. Appl Intell 27:89–99

    Article  MATH  Google Scholar 

  11. Khouadjia M, Alba E, Jourdan L, Talbi EG (2010) Multi-swarm optimization for dynamic combinatorial problems: a case study on dynamic vehicle routing problem. In: Swarm intelligence, Lecture notes in computer science, vol 6234. Springer, Berlin, pp 227–238

    Chapter  Google Scholar 

  12. Kilby P, Prosser P, Shaw P (1998) Dynamic VRPs: a study of scenarios. APES-06-1998, University of Strathclyde, U.K.

  13. Li C, Yang S (2008) Fast multi-swarm optimization for dynamic optimization problems. In: Proceedings of the 2008 fourth international conference on natural computation, vol 7. IEEE Comp Soc, Los Alamitos, pp 624–628

    Chapter  Google Scholar 

  14. Lin S (1965) Computer solutions of the traveling salesman problem. Bell Syst Comp J 44:2245–2269

    MATH  Google Scholar 

  15. Montemanni R, Gambardella L, Rizzoli A, Donati A (2005) A new algorithm for a dynamic vehicle routing problem based on ant colony system. J Comb Optim 10:327–343

    Article  MathSciNet  MATH  Google Scholar 

  16. Mori N, Imanishi S, Kita H, Nishikawa Y (1997) Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In: 7th international conference on genetic algorithms, pp 299–306

    Google Scholar 

  17. Oppacher F, Wineberg M (1999) The shifting balance genetic algorithm: improving the GA in a dynamic environment. In: Proceedings of the genetic and evolutionary computation conference, vol 1, pp 504–510

    Google Scholar 

  18. Osman I (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann Oper Res 41(4):421–451

    Article  MathSciNet  MATH  Google Scholar 

  19. Psaraftis H (1995) Dynamic vehicle routing: status and prospects. Ann Oper Res 61:143–164

    Article  MATH  Google Scholar 

  20. Sun L, Hu X, Wang Z, Huang M (2007) A knowledge-based model representation and on-line solution method for dynamic vehicle routing problem. In: Proceedings of the 7th international conference on computational science (ICCS’07), Part IV. Springer, Berlin, pp 218–226

    Google Scholar 

  21. Talbi E (2006) Parallel combinatorial optimization. Wiley, New York

    Book  Google Scholar 

  22. Talbi E (2009) Metaheuristics: from design to implementation. Wiley, New York

    MATH  Google Scholar 

  23. Wang JQ, Tong XN, Li ZM (2007) An improved evolutionary algorithm for dynamic vehicle routing problem with time windows. In: Proceedings of the 7th international conference on computational science (ICCS’07: ), Part IV. Springer, Berlin, pp 1147–1154

    Google Scholar 

Download references

Acknowledgements

Authors acknowledge funds from the Associated Teams Program MOMDI of the French National Institute for Research in Computer Science and Control (INRIA), the Spanish Ministry of Sciences and Innovation European FEDER under contracts TIN2008-06491-C04-01 (M* project) and TIN2011-28194 (roadME project), and CICE, Junta de Andalucía under contract P07-TIC-03044 (DIRICOM project). The experiments were carried out using the Grid’5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER, and several universities as well as other funding bodies. Briseida Sarasola acknowledges grant AP2009-1680 from the Spanish government.

Author information

Authors and Affiliations

  1. INRIA Lille Nord-Europe, Lille, France

    Mostepha R. Khouadjia, El-Ghazali Talbi & Laetitia Jourdan

  2. University of Lille 1, CNRS UMR, CNRS 8022, Lille, France

    El-Ghazali Talbi

  3. E.T.S.I. Informática, Universidad de Málaga, Málaga, Spain

    Briseida Sarasola & Enrique Alba

Authors
  1. Mostepha R. Khouadjia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. El-Ghazali Talbi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Laetitia Jourdan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Briseida Sarasola
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Enrique Alba
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to El-Ghazali Talbi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Khouadjia, M.R., Talbi, EG., Jourdan, L. et al. Multi-environmental cooperative parallel metaheuristics for solving dynamic optimization problems. J Supercomput 63, 836–853 (2013). https://doi.org/10.1007/s11227-012-0774-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-012-0774-x

Keywords