• search hit 4 of 54
Back to Result List

A Parallel Hybrid Genetic Search for the Capacitated VRP with Pickup and Delivery

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Timo Stadtler, Spyro Nita, Jan DünnweberORCiDGND
URN:urn:nbn:de:bvb:898-opus4-69854
URL / DOI:https://opus4.kobv.de/opus4-oth-regensburg/frontdoor/deliver/index/docId/6985/file/duennweber_kentucky_2023.pdf
DOI:https://doi.org/10.35096/othr/pub-6985
Parent Title (English):34th International Workshop, LCPC 2021, Newark, DE, USA, October 13–14, 2021
Document Type:conference proceeding (article)
Language:English
Year of first Publication:2023
Publishing Institution:Ostbayerische Technische Hochschule Regensburg
Release Date:2024/01/12
Tag:high-performance; parallel computing; route planning
Institutes:Fakultät Informatik und Mathematik
Regensburg Center for Artificial Intelligence - RCAI
Fakultät Informatik und Mathematik / Labor Parallele und Verteilte Systeme
Begutachtungsstatus:peer-reviewed
research focus:Digitalisierung
Licence (German):Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG