Selected Genetic Algorithms for Vehicle Routing Problem Solving
The traveling salesman problem (TSP) consists of finding the shortest way between cities, which passes through all cities and returns to the starting point, given the distance between cities. The Vehicle Routing Problem (VRP) is the issue of defining the assumptions and limitations in mapping routes...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-12-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/10/24/3147 |
| _version_ | 1797505211431911424 |
|---|---|
| author | Joanna Ochelska-Mierzejewska Aneta Poniszewska-Marańda Witold Marańda |
| author_facet | Joanna Ochelska-Mierzejewska Aneta Poniszewska-Marańda Witold Marańda |
| author_sort | Joanna Ochelska-Mierzejewska |
| collection | DOAJ |
| description | The traveling salesman problem (TSP) consists of finding the shortest way between cities, which passes through all cities and returns to the starting point, given the distance between cities. The Vehicle Routing Problem (VRP) is the issue of defining the assumptions and limitations in mapping routes for vehicles performing certain operational activities. It is a major problem in logistics transportation. In specific areas of business, where transportation can be perceived as added value to the product, it is estimated that its optimization can lower costs up to 25% in total. The economic benefits for more open markets are a key point for VRP. This paper discusses the metaheuristics usage for solving the vehicle routing problem with special attention toward Genetic Algorithms (GAs). Metaheuristic algorithms are selected to solve the vehicle routing problem, where GA is implemented as our primary metaheuristic algorithm. GA belongs to the evolutionary algorithm (EA) family, which works on a “survival of the fittest” mechanism. This paper presents the idea of implementing different genetic operators, modified for usage with the VRP, and performs experiments to determine the best combination of genetic operators for solving the VRP and to find optimal solutions for large-scale real-life examples of the VRP. |
| first_indexed | 2024-03-10T04:15:23Z |
| format | Article |
| id | doaj.art-c11b29bcd0de4699b55dd04d8e56e089 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T04:15:23Z |
| publishDate | 2021-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-c11b29bcd0de4699b55dd04d8e56e0892023-11-23T08:02:46ZengMDPI AGElectronics2079-92922021-12-011024314710.3390/electronics10243147Selected Genetic Algorithms for Vehicle Routing Problem SolvingJoanna Ochelska-Mierzejewska0Aneta Poniszewska-Marańda1Witold Marańda2Institute of Information Technology, Lodz University of Technology, 93-590 Lodz, PolandInstitute of Information Technology, Lodz University of Technology, 93-590 Lodz, PolandDepartment of Microelectronics and Computer Science, Lodz University of Technology, 93-005 Lodz, PolandThe traveling salesman problem (TSP) consists of finding the shortest way between cities, which passes through all cities and returns to the starting point, given the distance between cities. The Vehicle Routing Problem (VRP) is the issue of defining the assumptions and limitations in mapping routes for vehicles performing certain operational activities. It is a major problem in logistics transportation. In specific areas of business, where transportation can be perceived as added value to the product, it is estimated that its optimization can lower costs up to 25% in total. The economic benefits for more open markets are a key point for VRP. This paper discusses the metaheuristics usage for solving the vehicle routing problem with special attention toward Genetic Algorithms (GAs). Metaheuristic algorithms are selected to solve the vehicle routing problem, where GA is implemented as our primary metaheuristic algorithm. GA belongs to the evolutionary algorithm (EA) family, which works on a “survival of the fittest” mechanism. This paper presents the idea of implementing different genetic operators, modified for usage with the VRP, and performs experiments to determine the best combination of genetic operators for solving the VRP and to find optimal solutions for large-scale real-life examples of the VRP.https://www.mdpi.com/2079-9292/10/24/3147vehicle routing problemtraveling salesman problemmetaheuristicgenetic algorithmsoptimization |
| spellingShingle | Joanna Ochelska-Mierzejewska Aneta Poniszewska-Marańda Witold Marańda Selected Genetic Algorithms for Vehicle Routing Problem Solving Electronics vehicle routing problem traveling salesman problem metaheuristic genetic algorithms optimization |
| title | Selected Genetic Algorithms for Vehicle Routing Problem Solving |
| title_full | Selected Genetic Algorithms for Vehicle Routing Problem Solving |
| title_fullStr | Selected Genetic Algorithms for Vehicle Routing Problem Solving |
| title_full_unstemmed | Selected Genetic Algorithms for Vehicle Routing Problem Solving |
| title_short | Selected Genetic Algorithms for Vehicle Routing Problem Solving |
| title_sort | selected genetic algorithms for vehicle routing problem solving |
| topic | vehicle routing problem traveling salesman problem metaheuristic genetic algorithms optimization |
| url | https://www.mdpi.com/2079-9292/10/24/3147 |
| work_keys_str_mv | AT joannaochelskamierzejewska selectedgeneticalgorithmsforvehicleroutingproblemsolving AT anetaponiszewskamaranda selectedgeneticalgorithmsforvehicleroutingproblemsolving AT witoldmaranda selectedgeneticalgorithmsforvehicleroutingproblemsolving |