Solving the Multi-Depot Vehicle Routing Problem Using a Hybrid Genetic Algorithm

This study investigates the Multi-Depot Vehicle Routing Problem (MDVRP) with travel distance constraint (no refueling allowed). This problem is a critical challenge in the transportation industry, particularly in locomotive routing within railway networks. The research provides a comprehensive review of solution techniques, models the problem, and applies two approaches to solve it.The first approach consists of two stages: initially, a suitable allocation method assigns each customer to a depot. In the second stage, an innovative hybrid genetic algorithm determines the optimal route for each vehicle from the depot to the customers and back to the depot, ensuring that all problem constraints are satisfied. The second approach integrates allocation and routing processes simultaneously. At each step, routing results influence subsequent allocation decisions. Based on this perspective, a heuristic algorithm is proposed to solve the problem. Finally, the validity of the model is evaluated through a comparison of the results obtained from these two methods with those of previous studies.