A Grid-Based Genetic Approach to Solving the Vehicle Routing Problem with Time Windows
Source abstract
Abstract
This paper describes one grid-based genetic algorithm approach to solve the vehicle routing problem with time windows in one experimental cluster MiniGrid. Clusters used in this approach are located in two Mexican cities (Cuernavaca and Jiutepec, Morelos) securely communicating with each other since they are configured as one virtual private network, and its use as a single set of processors instead of isolated groups allows one to increase the computing power to solve complex tasks. The genetic algorithm splits the population of candidate solutions in several segments, which are simultaneously mutated in each process generated by the MiniGrid. These mutated segments are used to build a new population combining the results produced by each process. In this paper, the MiniGrid configuration scheme is described, and both the communication latency and the speedup behavior are discussed. Experimental results show one information exchange reduction through the MiniGrid clusters as well as an improved behavior of the evolutionary algorithm. A statistical analysis of these results suggests that our approach is better as a combinatorial optimization procedure as compared with other methods.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Vehicle Routing Optimization Methods · Transportation and Mobility Innovations · Advanced Manufacturing and Logistics Optimization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Research Center in Engineering and Applied Sciences, Autonomous University of Morelos State (UAEM), Avenida Universidad 1001 Colonia Chamilpa, C.P. 62209 Cuernavaca, Morelos, Mexico
Department of Systems and Computing, México National Technological/I.T. Veracruz, Calzada Miguel Ángel de Quevedo 2779, C.P. 91860 Veracruz, Mexico
Faculty of Accounting, Administration & Informatics, UAEM, Avenida Universidad 1001 Colonia Chamilpa, C.P. 62209 Cuernavaca, Morelos, Mexico
References (66)
Show source-provided references
1. Evolutionary Algorithm with Intelligent Mutation Operator that Solves the Vehicle Routing Problem of Clustered Classification with Time Windows
2. Exact Algorithms for the Vehicle Routing Problem Based on Spanning Tree and Shortest Path Relaxation10.1007/BF01589353 ↗
3. State Space Relaxation Procedures for the Computation of Bounds to Routing Problems
4. Naddef, D., and Rinaldi, G. (2001). Branch and Cut Algorithms for the Capacitated VRP, SIAM. Chapter 3.10.1137/1.9780898718515.ch3 ↗
5. A Taboo Search Heuristic for the Vehicle Routing Problem10.1287/mnsc.40.10.1276 ↗
6. Dorigo, M., Gambardella, L.M., Birattari, M., Martinoli, A., Poli, R., and Stützle, T. (2006, January 4–7). An Ant Colony System for the Open Vehicle Routing Problem. Proceedings of the ANTS 2006 Conference, LNCS 4150, Brussels, Belgium.
7. Brandão de Oliveira, H.C., Vasconcelos, G.C., and Bastos-Alvarenga, G. (2006, January 16–21). Reducing Traveled Distance in the Vehicle Routing Problem with Time Windows Using a Multi-Start Simulated Annealing. Proceedings of the 2006 International Joint Conference on Neural Networks, Vancouver, BC, Canada.10.1109/IJCNN.2006.247259 ↗
8. Genetic Algorithm Based Approach for Vehicle Routing Problem with Time Windows
9. Genetic Algorithms for the Vehicle Routing Problem with Time Windows, special issue on Bioinformatics and Genetic Algorithms
10. Cruz-Chávez, M.A., Díaz-Parra, O., Juárez-Romero, D., and Martínez-Rangel, M.G. (2008). Memetic Algorithm Based on a Constraint Satisfaction Technique for VRPTW, LNAI 5087, Springer.
11. Evolutionary Algorithm for the Vehicles Routing Problem with Time Windows Based on a Constraint Satisfaction Technique
12. 2-Path Cuts for the Vehicle Routing Problem with Time Windows10.1287/trsc.33.1.101 ↗
13. Arbelaitz, O., Rodriguez, C., and Zamakola, I. (2001, January 3–7). Low Cost Parallel Solutions for the VRPTW Optimization Problem. Proceedings of the International Conference on Parallel Processing Workshops (ICPPW’01), Washington, DC, USA.
14. Czachórski, T., Kozielski, S., and Stańczyk, U. (2011). Parallel Independent Simulated Annealing Searches to Solve the VRPTW. Man-Machine Interactions 2. Advances in Intelligent and Soft Computing, Springer.10.1007/978-3-642-23169-8 ↗
15. Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows10.1023/A:1015053600842 ↗
16. Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows10.1016/S0305-0548(03)00163-1 ↗
17. A Cooperative Parallel Meta-Heuristic for the Vehicle Routing Problem with Time Windows10.1016/j.cor.2003.11.023 ↗
18. Ropke, S., and Pisinger, D. (2005). A General Heuristic for Vehicle Routing Problems, University of Copenhagen. Technical Report.
19. Adaptive Threads Co-operation Schemes in a Parallel Heuristic Algorithm for the Vehicle Routing Problem with Time Windows
20. Co-operation in the Parallel Memetic Algorithm10.1007/s10766-014-0343-4 ↗
21. Simulated Annealing-based Parallel Multi-Objective Approach to Vehicle Routing Problem with Time Windows10.1016/j.eswa.2012.09.012 ↗
22. A cooperative population learning algorithm for vehicle routing problem with time windows10.1016/j.neucom.2014.06.033 ↗
23. Jawarneh, S., and Abdullah, S. (2015). Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. PLoS ONE, 10.10.1371/journal.pone.0130224 ↗
24. Stochastic Partially Optimized Cyclic Shift Crossover for Multi-Objective Genetic Algorithms for the Vehicle Routing Problem with Time-Windows10.1016/j.asoc.2016.09.039 ↗
25. Bychkov, I., and Batsyn, M. (2018, January 8–14). A Hybrid Approach for the Capacitated Vehicle Routing Problem with Time Windows, Optimization Problems and Their Applications. Proceedings of the 7th International Conference, OPTA 2018, Omsk, Russia.
26. A Parallel Simulated Annealing Method for the Vehicle Routing Problem with Simultaneous Pickup-delivery and Time Windows10.1016/j.cie.2015.02.005 ↗
27. Solving Large Scale Optimization Problems via Grid and Cluster Computing
28. Zunino, I., Melab, N., and Talbi, E.-G. (2007, January 4–6). A Grid-enabled Framework for Exact Optimization Algorithms. Proceedings of the 21st European Conference on Modelling and Simulation, Prague, Czech Republic.
29. Rodríguez-León, A., Cruz-Chávez, M.A., Rivera-López, R., Ávila-Melgar, E.Y., Juárez-Pérez, F., and Cruz-Rosales, M.-H. (October, January 28). A Communication Scheme for an Experimental Grid in the Resolution of VRPTW using an Evolutionary Algorithm. Proceedings of the Electronics, Robotics and Automotive Mechanics Conference, CERMA 2010, Morelos, Mexico.10.1109/CERMA.2010.8 ↗
30. Jing, T., Hiot, M., Yew, L., and Ong, S. (2003, January 8–12). A Parallel Hybrid GA for Combinatorial Optimization Using Grid Technology. Proceedings of the IEEE Congress on Evolutionary Computation, Canberra, Australia.
31. Grid Computing for Parallel Bioinspired Algorithms10.1016/j.jpdc.2005.11.006 ↗
32. Solving large-scale real-world telecommunication problems using a grid-based genetic algorithm10.1080/03052150802294581 ↗
33. Efficient Hierarchical Parallel Genetic Algorithms Using Grid Computing10.1016/j.future.2006.10.008 ↗
34. Cruz-Chávez, M.A., Hernández-Báez, I., Rodriguez-León, A., Ávila-Melgar, E.Y., Juárez-Pérez, F., and Martínez-Oropeza, A. (2009). PSAUPMP Application in Grid EELA-2, Status 5: Parallel Simulated Annealing Algorithm for the Weighted Unrelated Parallel Machines Problem, Second EELA-2 Grid School. Available online: http://applications.eu-eela.eu/app_list.php?l=20.10.1109/CERMA.2009.46 ↗
35. Cruz-Chávez, M.A., Rodríguez-León, A., Ávila-Melgar, E.Y., Juárez-Pérez, F., Zavala-Díaz, J.C., and Rivera-López, R. (2009, January 25–27). Parallel Hybrid Evolutionary Algorithm in Grid Environment for the Job Shop Scheduling Problem. Proceedings of the 2nd EELA-2 Conference, Choroni, Venezuela.
36. Escuela, G., Cardinale, Y., and González, J. (2007, January 29–31). A Java-based Distributed Genetic Algorithm Framework. Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, Patras, Greece.10.1109/ICTAI.2007.137 ↗
37. Garey, M.R., and Johnson, D.S. (2003). Computers and Intractability; A Guide to the Theory of NP-Completeness, W.H. Freeman and Company.
38. Toth, P., and Vigo, D. (2002). The Vehicle Routing Problem, SIAM.10.1137/1.9780898718515 ↗
39. The Truck Dispatching Problem10.1287/mnsc.6.1.80 ↗
40. Holland, J.H. (1998). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press.
41. Networking and Emerging Optimization Research Group (2018). Vehicle Routing Problem, Universidad de Málaga. Available online: http://neo.lcc.uma.es/vrp/.
42. Least Squares Quantization in PCM10.1109/TIT.1982.1056489 ↗
43. Papadimitriou, C.H., and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc.
44. Lau, K.K., Kumar, M.J., and Achuthan, N.R. (1997, January 20). Parallel Implementation of Branch and Bound Algorithm for Solving Vehicle Routing Problem on NOWs. Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks, Taipei, Taiwan.
45. A Parallel Algorithm for the Vehicle Routing Problem with Time Window Constraints
46. Jiang, W., Zhang, Y., and Xie, J. (April, January 30). A Particle Swarm Optimization Algorithm with Crossover for Vehicle Routing Problem with Time Windows. Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Scheduling, Nashville, TN, USA.10.1109/SCIS.2009.4927022 ↗
47. A Survey of Parallel Genetic Algorithms
48. Bote-Lorenzo, M.L., Dimitriadis, Y.A., and Gómez-Sánchez, E. (2004). Grid Characteristics and Uses: A Grid Definition. First European across Grids Conference (ACG’03), Springer.10.1007/978-3-540-24689-3_36 ↗
49. Ghosh, S. (2007). Distributed Systems: An Algorithmic Approach, Chapman & Hall/CRC.
50. Mache, J., Tyman, D., Pinter, A., and Allick, C. (2006, January 16–18). Performance Implications of Using VPN Technology for Cluster Integration and Grid Computing. Proceedings of the International Conference on Networking and Services, Slicon Valley, CA, USA.10.1109/ICNS.2006.83 ↗
51. Cordova-Serrano, M.A. (2015). Design and Implementation of Connectivity Infrastructure of the Data Center UAEM-UPEMOR Minigrid. [Master’s Thesis, Polytechnic University of Morelos State (UPEMOR)]. (In Spanish).
52. Foster, I., and Karonis, N.T. (1998, January 7–13). A Grid-Enabled MPI: Message Passing in Heterogeneous Distributed Computing Systems. Proceedings of the 1998 ACM/IEEE Conference on Supercomputing, Orlando, FL, USA.10.1109/SC.1998.10051 ↗
53. Kauhaus, C., and Fey, D. (2006, January 13–17). Building Mini-Grid Environments with Virtual Private Networks: A Pragmatic Approach. Proceedings of the International Conference on Parallel Computing in Electrical Engineering (PARELEC’06), Bialystok, Poland.
54. Tatezono, M., Maruyama, N., and Matsuoka, S. (2006, January 4–7). Making Wide-Area, Multi-Site MPI Feasible Using XenVM. Proceedings of the Workshop on Frontiers of High Performance Computing and Networking, LNCS 2006, Sorrento, Italy.10.1007/11942634_41 ↗
55. Solomon, M.M. (2018). VRPTW Benchmark Problems, Northeastern University. Available online: http://w.cba.neu.edu/~msolomon/problems.htm.
56. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: A case study on the CEC’2005 special session on real parameter optimization
57. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms10.1016/j.swevo.2011.02.002 ↗
58. Individual Comparisons by Ranking Methods10.2307/3001968 ↗
59. The use of ranks to avoid the assumption of normality implicit in the analysis of variance10.1080/01621459.1937.10503522 ↗
60. Bergmann, B., and Hommel, G. (1988). Improvements of general multiple test procedures for redundant systems of hypotheses. Multiple Hypothesenprüfung/Multiple Hypotheses Testing, Springer.10.1007/978-3-642-52307-6_8 ↗
61. scmamp: Statistical comparison of multiple algorithms in multiple problems10.32614/RJ-2016-017 ↗
62. Quintiq (2019, July 10). How Can We Prove that Quintiq’s Optimization Technology is Number One? Vehicle Routing Problem with Time Windows. Dassault Systèmes. Available online: https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark/1000-customers.
63. He, Z., Wang, L.W., Lin, W., Chen, Y., and Hu, H. (2019, July 10). Unpublished Work by CAINIAO AI. Available online: https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark/1000-customers/.
64. Cybula, P., Rogalski, M., Beling, P., Jaszkiewicz, A., and Pełka, P. (2019, July 10). Emapa, S.A. “New Methods of VRP Problem Optimization”, Unpublished Research Funded by The National Centre for Research and Development. Project Number: POIR.01.01.01.-00-0222/16. Available online: https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark/1000-customers/.
65. Parallel evolutionary algorithms can achieve super-linear performance10.1016/S0020-0190(01)00281-2 ↗
66. Statistical comparisons of classifiers over multiple data sets