Skip to content

Latest commit

 

History

History
40 lines (25 loc) · 3.1 KB

README.md

File metadata and controls

40 lines (25 loc) · 3.1 KB
Raw

ACO VRP FRAMEWORK

This repository contains implementations of the following meta-heuristics for VRP problems:

  • VRPTW_ACS for Dynamic Vehicle Routing Problems (DVRPTW) [1]
  • ALNS for Multi-pickup and Delivery Problem with Time Windows (MPDPTW) [2]
  • TABU_SA for Pickup and Delivery Problem with Time Windows (PDPTW) [3]
  • LNS for Pickup and Delivery Problem with Time Windows (PDPTW) [4]
  • ALNS for Dynamic Pickup and Delivery Problem with Time Windows (PDPTW) [5]
  • TABU_SA for Dynamic Pickup and Delivery Problem with Time Windows (PDPTW) [5]
  • MMAS for the Travelling Salesman Problem [6, 7]
  • MMAS_MEM for the Dynamic Travelling Salesman Problem with Moving Vehicle [8]
  • MMAS with LS for the Dynamic Travelling Salesman Problem with Moving Vehicle [9]
  • MMAS with US for the Dynamic Travelling Salesman Problem [10]

As extra, it also has some integrations with:

  • RINSIM: Framework to simulate VRP problems

References:

[1] R. Necula, M. Breaban and M. Raschip, "Tackling Dynamic Vehicle Routing Problem with Time Windows by means of ant colony system," 2017 IEEE Congress on Evolutionary Computation (CEC), San Sebastian, 2017, pp. 2480-2487, doi: 10.1109/CEC.2017.7969606.

[2] Naccache, S., Côté, J., & Coelho, L. C. (2018). The multi-pickup and delivery problem with time windows. European Journal of Operational Research, 269(1), 353–362. https://doi.org/10.1016/j.ejor.2018.01.035

[3] H. Li and A. Lim, "A metaheuristic for the pickup and delivery problem with time windows," Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence. ICTAI 2001, Dallas, TX, USA, 2001, pp. 160-167, doi: 10.1109/ICTAI.2001.974461.

[4] Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135

[5] Own implementation

[6] Max-Min Ant System T. Stützle and H. H. Hoos, MAX-MIN Ant System. Future Generation Computer Systems. 16(8):889--914,2000.

[7] T. Stützle and H. H. Hoos, Improving the Ant System: A detailed report on the MAX-MIN Ant System. Technical report AIDA-96-12, FG Intellektik, FB Informatik, TU Darmstadt, 1996.

[8] J. Pedro Schmitt, F. Baldo and R. Stubs Parpinelli, "A MAX-MIN Ant System with Short-Term Memory Applied to the Dynamic and Asymmetric Traveling Salesman Problem," 2018 7th Brazilian Conference on Intelligent Systems (BRACIS), Sao Paulo, 2018, pp. 1-6, doi: 10.1109/BRACIS.2018.00009.

[9] Schmitt J.P., Parpinelli R.S., Baldo F. (2019) Analysis of Max-Min Ant System with Local Search Applied to the Asymmetric and Dynamic Travelling Salesman Problem with Moving Vehicle. In: Kotsireas I., Pardalos P., Parsopoulos K., Souravlias D., Tsokas A. (eds) Analysis of Experimental Algorithms. SEA 2019. Lecture Notes in Computer Science, vol 11544. Springer, Cham. https://doi.org/10.1007/978-3-030-34029-2_14

[10] Mavrovouniotis, M., Muller, F. M., & Yang, S. (2017). Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems. IEEE Transactions on Cybernetics, 47(7), 1743–1756. https://doi.org/10.1109/tcyb.2016.2556742