Skip to main content

Advertisement

SpringerLink
Log in

Optimizing agents with genetic programming: an evaluation of hyper-heuristics in dynamic real-time logistics

  • Published:
Genetic Programming and Evolvable Machines Aims and scope Submit manuscript

Abstract

Dynamic pickup and delivery problems (PDPs) require online algorithms for managing a fleet of vehicles. Generally, vehicles can be managed either centrally or decentrally. A common way to coordinate agents decentrally is to use the contract-net protocol (CNET) that uses auctions to allocate tasks among agents. To participate in an auction, agents require a method that estimates the value of a task. Typically, this method involves an optimization algorithm, e.g. to calculate the cost to insert a customer. Recently, hyper-heuristics have been proposed for automated design of heuristics. Two properties of automatically designed heuristics are particularly promising: (1) a generated heuristic computes quickly, it is expected therefore that hyper-heuristics perform especially well for urgent problems, and (2) by using simulation-based evaluation, hyper-heuristics can create a ‘rule of thumb’ that anticipates situations in the future. In the present paper we empirically evaluate whether hyper-heuristics, more specifically genetic programming (GP), can be used to improve agents decentrally coordinated via CNET. We compare several GP settings and compare the resulting heuristic with existing centralized and decentralized algorithms based on the OptaPlanner optimization library. The tests are conducted in real-time on a dynamic PDP dataset with varying levels of dynamism, urgency, and scale. The results indicate that the evolved heuristic always outperforms the optimization algorithm in the decentralized multi-agent system (MAS) and often outperforms the centralized optimization algorithm. Our paper demonstrates that designing MASs using genetic programming is an effective way to obtain competitive performance compared to traditional operational research approaches. These results strengthen the relevance of decentralized agent based approaches in dynamic logistics.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Listing 1
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. S.N. Parragh, K.F. Doerner, R.F. Hartl, A survey on pickup and delivery problems. Part II: transportation between pickup and delivery locations. Journal für Betriebswirtschaft. 58(2), 81–117 (2008)

  2. G. Berbeglia, J.-F. Cordeau, G. Laporte, Dynamic pickup and delivery problems. Eur. J. Oper. Res. 202(1), 8–15 (2010). doi:10.1016/j.ejor.2009.04.024

    Article  MATH  Google Scholar 

  3. R.R.S. van Lon, E. Ferrante, A.E. Turgut, T. Wenseleers, G. Vanden Berghe, T. Holvoet, Measures of dynamism and urgency in logistics. Eur. J. Oper. Res. 253(3), 614–624 (2016). doi:10.1016/j.ejor.2016.03.021

    Article  MathSciNet  MATH  Google Scholar 

  4. R.R.S. van Lon, T. Holvoet, Towards systematic evaluation of multi-agent systems in large scale and dynamic logistics, in PRIMA 2015: Principles and Practice of Multi-Agent Systems: 18th International Conference, Bertinoro, Italy, October 26–30, 2015, Proceedings, ed. by Q. Chen, P. Torroni, S. Villata, J. Hsu, A. Omicini (Springer, Cham, 2015), pp. 248–264. ISBN 978-3-319-25524-8. doi:10.1007/978-3-319-25524-8_16

  5. K. Fischer, J.P. Müller, M. Pischel, A model for cooperative transportation scheduling, in Proceedings of the 1st International Conference on Multiagent Systems (ICMAS’95), San Francisco (1995), pp. 109–116

  6. A. Glaschenko, A. Ivaschenko, G. Rzevski, P. Skobelev. Multi-agent real time scheduling system for taxi companies, in Proceedings of 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2009), pp. 29–36

  7. D. Weyns, N. Boucké, T. Holvoet, Gradient field-based task assignment in an AGV transportation system, in Proceedings of 5th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2006), pp. 842–849. ISBN 1-59593-303-4. doi:10.1145/1160633.1160785

  8. R.R.S. van Lon, T. Holvoet, When do agents outperform centralized algorithms? A systematic empirical evaluation in logistics. Auton. Agent. Multi-Ag. (2016 Under review), also published as technical report [39]

  9. G. De Smet et al. OptaPlanner User Guide. Red Hat and the community. http://www.optaplanner.org. OptaPlanner is an open source constraint satisfaction solver in Java

  10. C. Cruz, J.R. González, D.A. Pelta, Optimization in dynamic environments: a survey on problems, methods and measures. Soft Comput. 15(7), 1427–1448 (2011). doi:10.1007/s00500-010-0681-0

    Article  Google Scholar 

  11. S. Yang, Y. Jiang, T.T. Nguyen, Metaheuristics for dynamic combinatorial optimization problems. IMA J. Manag. Math. 24(4), 451 (2012). doi:10.1093/imaman/dps021

    Article  MathSciNet  MATH  Google Scholar 

  12. T.T. Nguyen, S. Yang, J. Branke, Evolutionary dynamic optimization: a survey of the state of the art. Swarm Evol. Comput. 6, 1–24 (2012). doi:10.1016/j.swevo.2012.05.001

    Article  Google Scholar 

  13. E.K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, R. Qu, Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64(12), 1695–1724 (2013). doi:10.1057/jors.2013.71

    Article  Google Scholar 

  14. E.K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, J.R. Woodward, A Classification of Hyper-heuristic Approaches (Springer, Boston, 2010), pp. 449–468. ISBN 978-1-4419-1665-5. doi:10.1007/978-1-4419-1665-5_15

  15. A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing (Natural Computing Series), corrected edn. (Springer, Berlin, 2007). ISBN 3540401849. doi:10.1007/978-3-662-05094-1

  16. J. Branke, S. Nguyen, C.W. Pickardt, M. Zhang, Automated design of production scheduling heuristics: a review. IEEE Trans. Evol. Comput. 20(1), 110–124 (2016). doi:10.1109/TEVC.2015.2429314

    Article  Google Scholar 

  17. R.E. Keller, R. Poli, Cost–Benefit Investigation of a Genetic-Programming Hyperheuristic (Springer, Berlin, 2008), pp. 13–24. ISBN 978-3-540-79305-2. doi:10.1007/978-3-540-79305-2_2

  18. E.K. Burke, M.R. Hyde, G. Kendall, Evolving Bin Packing Heuristics with Genetic Programming (Springer, Berlin, 2006), pp. 860–869. ISBN 978-3-540-38991-0. doi:10.1007/11844297_87

  19. A. Beham, M. Kofler, S. Wagner, M. Affenzeller, Agent-based simulation of dispatching rules in dynamic pickup and delivery problems, in: 2009 2nd International Symposium on Logistics and Industrial Informatics (2009), pp. 1–6. doi:10.1109/LINDI.2009.5258763

  20. R.R.S. van Lon, T. Holvoet, G. Vanden Berghe, T. Wenseleers, J. Branke. Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems, in GECCO Companion ’12 Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference Companion, Philadelphia, USA (2012), pp. 331–336. ISBN 9781450311786. doi:10.1145/2330784.2330832

  21. S. Vonolfen, A. Beham, M. Kommenda, M. Affenzeller, Structural Synthesis of Dispatching Rules for Dynamic Dial-a-Ride Problems (Springer, Berlin, 2013), pp. 276–283. ISBN: 978-3-642-53856-8. doi:10.1007/978-3-642-53856-8_35

  22. J. Merlevede, R.R.S. van Lon, T. Holvoet, Neuroevolution of a multi-agent system for the dynamic pickup and delivery problem, in International Joint Workshop on Optimisation in Multi-Agent Systems and Distributed Constraint Reasoning (OptMAS, co-located with AAMAS) (2014)

  23. R.R.S. van Lon, T. Holvoet, RinSim: a simulator for collective adaptive systems in transportation and logistics. In Proceedings of the 6th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2012), Lyon, France (2012), pp. 231–232. doi:10.1109/SASO.2012.41

  24. D. Weyns, N. Boucké, T. Holvoet, B. Demarsin, DynCNET: a protocol for dynamic task assignment in multiagent systems, in First International Conference on Self-Adaptive and Self-Organizing Systems, SASO 2007 (2007), pp. 281–284. doi:10.1109/SASO.2007.20

  25. R.G. Smith, The contract net protocol: high-level communication and control in a distributed problem solver. IEEE Trans. Comput. 29(12), 1104–1113 (1980). doi:10.1109/TC.1980.1675516

    Article  Google Scholar 

  26. J.R. Koza, Genetic Programming II: Automatic Discovery of Reusable Subprograms (MIT Press, Cambridge, 1994)

  27. G. Balan, S. Paus, Z. Skolicki, R. Kicinger, E. Popovici, K. Sullivan, J. Harrison, J. Bassett, R. Hubley, A. Desai, A. Chircop, J. Compton, W. Haddon, S. Donnelly, B. Jamil, J. Zelibor, E. Kangas, F. Abidi, H. Mooers, J. O’Beirne, K.A. Talukder, S. McKay, S. Luke, L. Panait, J. McDermott, ECJ 20: a java-based evolutionary computation and genetic programming research system (2011). https://cs.gmu.edu/~eclab/projects/ecj/

  28. L. Cohen, JPPF, the open source grid computing solution. http://jppf.org/

  29. D.H. Wolpert, W.G. Macready, No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997). doi:10.1109/4235.585893

    Article  Google Scholar 

  30. R.R.S. van Lon, T. Holvoet, Evolved multi-agent systems and thorough evaluation are necessary for scalable logistics, in 2013 IEEE Workshop on Computational Intelligence In Production And Logistics Systems (CIPLS) (2013), pp. 48–53. doi:10.1109/CIPLS.2013.6595199

  31. R.R.S. van Lon, Optimizing agents with genetic programming: An evaluation of hyper-heuristics in dynamic real-time logistics—code (2017). https://github.com/rinde/vanLon17-GPEM-code/tree/v1.0.0. doi:10.5281/zenodo.260130

  32. R.R.S. van Lon, Optimizing agents with genetic programming: an evaluation of hyper-heuristics in dynamic real-time logistics—datasets and results (2017). doi:10.5281/zenodo.259774

  33. R.R.S. van Lon, RinSim v4.3.0 (2016). https://github.com/rinde/RinSim/tree/v4.3.0. doi:10.5281/zenodo.192106

  34. R.R.S. van Lon, RinLog v3.2.0 (2016). https://github.com/rinde/RinLog/tree/v3.2.0. doi:10.5281/zenodo.192111

  35. R.R.S. van Lon, RinECJ v4.3.0 (2017). https://github.com/rinde/RinECJ/tree/v0.3.0. doi:10.5281/zenodo.259718

  36. R.R.S. van Lon, evo4mas v0.3.0 (2017). https://github.com/rinde/evo4mas/tree/v0.3.0. doi:10.5281/zenodo.248966

  37. R.R.S. van Lon, PDPTW dataset dataset: v1.1.0, 2016. https://github.com/rinde/pdptw-dataset-generator/tree/v1.1.0. doi:10.5281/zenodo.59259

  38. M. Waibel, L. Keller, D. Floreano, Genetic team composition and level of selection in the evolution of cooperation. IEEE Trans. Evol. Comput. 13(3), 648–660 (2009). doi:10.1109/TEVC.2008.2011741

    Article  Google Scholar 

  39. R.R.S. van Lon, T. Holvoet, in When do agents outperform centralized algorithms? A systematic empirical evaluation in logistics. CW Reports (Department of Computer Science, KU Leuven, 2016)

Download references

Acknowledgements

This research is partially funded by the Research Fund KU Leuven.

Author information

Authors and Affiliations

  1. imec-DistriNet, Department of Computer Science, KU Leuven, Celestijnenlaan 200A, 3001, Heverlee, Belgium

    Rinde R. S. van Lon & Tom Holvoet

  2. Warwick Business School, University of Warwick, Coventry, CV4 7AL, UK

    Juergen Branke

Authors
  1. Rinde R. S. van Lon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juergen Branke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tom Holvoet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rinde R. S. van Lon.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

van Lon, R.R.S., Branke, J. & Holvoet, T. Optimizing agents with genetic programming: an evaluation of hyper-heuristics in dynamic real-time logistics. Genet Program Evolvable Mach 19, 93–120 (2018). https://doi.org/10.1007/s10710-017-9300-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10710-017-9300-5

Keywords

Search

Navigation