Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem
One of the best heuristic algorithms for solving the capacitated vehicle routing problem is a hybrid genetic search. A critical component of the search is a splitting procedure, where a solution encoded as a giant tour of nodes is optimally split into vehicle routes using dynamic programming. Howeve...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/3/165 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850204899015393280 |
|---|---|
| author | Lars Magnus Hvattum |
| author_facet | Lars Magnus Hvattum |
| author_sort | Lars Magnus Hvattum |
| collection | DOAJ |
| description | One of the best heuristic algorithms for solving the capacitated vehicle routing problem is a hybrid genetic search. A critical component of the search is a splitting procedure, where a solution encoded as a giant tour of nodes is optimally split into vehicle routes using dynamic programming. However, the current state-of-the-art implementation of the splitting procedure assumes that the start of the giant tour is fixed as a part of the encoded solution. This paper examines whether the fixed starting point is a significant drawback. Results indicate that simple adjustments of the starting point for the splitting procedure can improve the performance of the genetic search, as measured by the average primal gaps of the final solutions obtained, by 3.9%. |
| format | Article |
| id | doaj-art-dcc979ef47d8413c9defb429bae04740 |
| institution | OA Journals |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-dcc979ef47d8413c9defb429bae047402025-08-20T02:11:12ZengMDPI AGAlgorithms1999-48932025-03-0118316510.3390/a18030165Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing ProblemLars Magnus Hvattum0Faculty of Logistics, Molde University College, 6402 Molde, NorwayOne of the best heuristic algorithms for solving the capacitated vehicle routing problem is a hybrid genetic search. A critical component of the search is a splitting procedure, where a solution encoded as a giant tour of nodes is optimally split into vehicle routes using dynamic programming. However, the current state-of-the-art implementation of the splitting procedure assumes that the start of the giant tour is fixed as a part of the encoded solution. This paper examines whether the fixed starting point is a significant drawback. Results indicate that simple adjustments of the starting point for the splitting procedure can improve the performance of the genetic search, as measured by the average primal gaps of the final solutions obtained, by 3.9%.https://www.mdpi.com/1999-4893/18/3/165vehicle routing problemgenetic algorithmopen sourcegenetic operator |
| spellingShingle | Lars Magnus Hvattum Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem Algorithms vehicle routing problem genetic algorithm open source genetic operator |
| title | Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem |
| title_full | Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem |
| title_fullStr | Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem |
| title_full_unstemmed | Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem |
| title_short | Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem |
| title_sort | where to split in hybrid genetic search for the capacitated vehicle routing problem |
| topic | vehicle routing problem genetic algorithm open source genetic operator |
| url | https://www.mdpi.com/1999-4893/18/3/165 |
| work_keys_str_mv | AT larsmagnushvattum wheretosplitinhybridgeneticsearchforthecapacitatedvehicleroutingproblem |