Embedded Files
Given the compelling similarity between the problems of MDVRP and task planning, we analyze the performance of the developed algorithm using well-studied benchmark examples of MDVRP.
On a selection of benchmark examples [1, 2], a custom genetic algorithm and the distributed metaheuristic-based on CBM were run 50 times for each test. The developed algorithm was compared to the GA because of the similarity of the approaches since they use the same set of genetic operators. The main differences are that GA is a centralized algorithm and does not use the local search procedure. The metaheuristic algorithm was run in four parallel processes. The complete simulation results are shown in the table below.
In the graphs below, GA solutions are marked black and the distributed metaheuristic results blue. Best known solutions (BKS) of each problem are represented as green crosses on the graph.
[1] J.-F. Cordeau, M. Gendreau, G. Laporte, A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks 30 (2) (1997) 105–119. doi: https://doi.org/10.1002/(SICI)1097-0037(199709)30:2%3C105::AID-NET5%3E3.0.CO;2-G
[2] Cordeau multiple depot vrp instances, https://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/, accessed: 2020-11-12.
Comparison to some distributed approaches from the literature
Comparison to some distributed approaches from the literature
[41] A. Soeanu, S. Ray, M. Debbabi, J. Berger, A. Boukhtouta, A. Ghanmi, A decentralized heuristic for multi-depot split-delivery vehicle routing problem, in: 2011 IEEE International Conference on Automation and Logistics (ICAL), 2011, pp. 70–75. doi:10.1109/ICAL.2011.6024686.
[42] A. Soeanu, S. Ray, M. Debbabi, J. Berger, A. Boukhtouta, A learning based evolutionary algorithm for distributed multi-depot VRP., in: KES, 2012, pp. 49–58.
[43] S. Zhang, C. K. Lee, An improved artificial bee colony algorithm for the capacitated vehicle routing problem, in: 2015 IEEE International Conference on Systems, Man, and Cybernetics, IEEE, 2015, pp. 2124–2128.
[44] M. Saleh, A. Soeanu, S. Ray, M. Debbabi, J. Berger, A. Boukhtouta, Mechanism design for decentralized vehicle routing problem, in: Proceedings of the 27th Annual ACM Symposium on Applied Computing, SAC ’12, Association for Computing Machinery, New York, NY, USA, 2012, p. 749–754. URL: https://doi.org/10.1145/2245276.2245419.
Page updated
Google Sites
Report abuse