A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem
This paper presents a hybrid grasshopper optimization algorithm using a novel decoder and local search to solve instances of the open vehicle routing problem with capacity and distance constraints. The algorithm’s decoder first defines the number of vehicles to be used and then it partitions the cli...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-04-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/4/96 |
| _version_ | 1797570450155372544 |
|---|---|
| author | Valeria Soto-Mendoza Irma García-Calvillo Efraín Ruiz-y-Ruiz Jaime Pérez-Terrazas |
| author_facet | Valeria Soto-Mendoza Irma García-Calvillo Efraín Ruiz-y-Ruiz Jaime Pérez-Terrazas |
| author_sort | Valeria Soto-Mendoza |
| collection | DOAJ |
| description | This paper presents a hybrid grasshopper optimization algorithm using a novel decoder and local search to solve instances of the open vehicle routing problem with capacity and distance constraints. The algorithm’s decoder first defines the number of vehicles to be used and then it partitions the clients, assigning them to the available routes. The algorithm performs a local search in three neighborhoods after decoding. When a new best solution is found, every route is locally optimized by solving a traveling salesman problem, considering the depot and clients in the route. Three sets containing a total of 30 benchmark problems from the literature were used to test the algorithm. The experiments considered two cases of the problem. In the first, the primary objective is to minimize the total number of vehicles and then the total distance to be traveled. In the second case, the total distance traveled by the vehicles is minimized. The obtained results showed the algorithm’s proficient performance. For the first case, the algorithm was able to improve or match the best-known solutions for 21 of the 30 benchmark problems. For the second case, the best-known solutions for 18 of the 30 benchmark problems were found or improved by the algorithm. Finally, a case study from a real-life problem is included. |
| first_indexed | 2024-03-10T20:25:44Z |
| format | Article |
| id | doaj.art-010b60fb991944f199cd47b107f61351 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T20:25:44Z |
| publishDate | 2020-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-010b60fb991944f199cd47b107f613512023-11-19T21:48:16ZengMDPI AGAlgorithms1999-48932020-04-011349610.3390/a13040096A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing ProblemValeria Soto-Mendoza0Irma García-Calvillo1Efraín Ruiz-y-Ruiz2Jaime Pérez-Terrazas3Centro de Investigación en Matemáticas Aplicadas, Universidad Autónoma de Coahuila Edificio “S” Camporredondo, Saltillo, Coahuila 25280, MexicoCentro de Investigación en Matemáticas Aplicadas, Universidad Autónoma de Coahuila Edificio “S” Camporredondo, Saltillo, Coahuila 25280, MexicoDivisión de Estudios de Posgrado e Investigación, Tecnológico Nacional de México/Instituto Tecnológico de Saltillo. Blvd. Venustiano Carranza 2400, Saltillo, Coahuila 25280, MexicoDivisión de Estudios de Posgrado e Investigación, Tecnológico Nacional de México/Instituto Tecnológico de Saltillo. Blvd. Venustiano Carranza 2400, Saltillo, Coahuila 25280, MexicoThis paper presents a hybrid grasshopper optimization algorithm using a novel decoder and local search to solve instances of the open vehicle routing problem with capacity and distance constraints. The algorithm’s decoder first defines the number of vehicles to be used and then it partitions the clients, assigning them to the available routes. The algorithm performs a local search in three neighborhoods after decoding. When a new best solution is found, every route is locally optimized by solving a traveling salesman problem, considering the depot and clients in the route. Three sets containing a total of 30 benchmark problems from the literature were used to test the algorithm. The experiments considered two cases of the problem. In the first, the primary objective is to minimize the total number of vehicles and then the total distance to be traveled. In the second case, the total distance traveled by the vehicles is minimized. The obtained results showed the algorithm’s proficient performance. For the first case, the algorithm was able to improve or match the best-known solutions for 21 of the 30 benchmark problems. For the second case, the best-known solutions for 18 of the 30 benchmark problems were found or improved by the algorithm. Finally, a case study from a real-life problem is included.https://www.mdpi.com/1999-4893/13/4/96optimizationcombinatorial optimizationopen vehicle routing problemgrasshopper optimization algorithm |
| spellingShingle | Valeria Soto-Mendoza Irma García-Calvillo Efraín Ruiz-y-Ruiz Jaime Pérez-Terrazas A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem Algorithms optimization combinatorial optimization open vehicle routing problem grasshopper optimization algorithm |
| title | A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem |
| title_full | A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem |
| title_fullStr | A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem |
| title_full_unstemmed | A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem |
| title_short | A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem |
| title_sort | hybrid grasshopper optimization algorithm applied to the open vehicle routing problem |
| topic | optimization combinatorial optimization open vehicle routing problem grasshopper optimization algorithm |
| url | https://www.mdpi.com/1999-4893/13/4/96 |
| work_keys_str_mv | AT valeriasotomendoza ahybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT irmagarciacalvillo ahybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT efrainruizyruiz ahybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT jaimeperezterrazas ahybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT valeriasotomendoza hybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT irmagarciacalvillo hybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT efrainruizyruiz hybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem AT jaimeperezterrazas hybridgrasshopperoptimizationalgorithmappliedtotheopenvehicleroutingproblem |