TY - CHAP A1 - Stadtler, Timo A1 - Nita, Spyro A1 - Dünnweber, Jan T1 - A Parallel Hybrid Genetic Search for the Capacitated VRP with Pickup and Delivery T2 - 34th International Workshop, LCPC 2021, Newark, DE, USA, October 13–14, 2021 N2 - In the realm of parallel computing, optimization plays a pivotal role in achieving efficient and scalable solutions. In this work, we present the parallelization of a hybrid genetic search for solving the Capacitated Vehicle Routing Problem with Pickup and Delivery (CVRPPD).It leverages the synergy between genetic algorithms and parallel computing to address the complex optimization problem. This hybrid algorithm combines a customized version of local search with a genetic algorithm to compute an effective solution. Our implementation makes use of the Message Passing Interface (MPI) for data distribution and parallel execution. In addition, we run multi-threaded processes on NVIDIA graphical processors using the CUDA technology, which further increases the computation speed and consequently minimizes the runtime. Parallelization also allows the best-improvement strategy to be used instead of the rst-improvement strategy while maintaining the same runtime. We store the resulting routes in a bus route database which we created as the basis of an extensive library of optimal routes for our specifc use case of optimizing bus routes in a rural area. The experimental results on real road data show that the parallel implementation of the Hybrid Genetic Search (HGS) achieves significant improvements in runtime over the sequential implementation above a certain problem size. We believe that our implementation of the parallel hybrid genetic search method can have a great in influence on optimization strategies in parallel computing and can also be applied to other subproblems of the VRP. KW - parallel computing KW - high-performance KW - route planning Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:898-opus4-69854 UR - https://opus4.kobv.de/opus4-oth-regensburg/frontdoor/deliver/index/docId/6985/file/duennweber_kentucky_2023.pdf ER -