Selected Genetic Algorithms for Vehicle Routing Problem Solving

Electronics

Witold Marańda¹  Joanna Ochelska-Mierzejewska²  Aneta Poniszewska-Marańda² 

[1] Department of Microelectronics and Computer Science, Lodz University of Technology, 93-005 Lodz, Poland;Institute of Information Technology, Lodz University of Technology, 93-590 Lodz, Poland;

关键词: vehicle routing problem;    traveling salesman problem;    metaheuristic;    genetic algorithms;    optimization;   

DOI  :  10.3390/electronics10243147

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown