Publication Type:

Journal Article

Source:

World Applied Programming, Volume 1, Issue 3, p.118-131 (2011)

URL:

https://www.semanticscholar.org/paper/Solution-To-Multi-Depot-Vehicle-Routing-Problem-Surekha-Sumathi/d1c47ef76513773c0932292d5d417ba1ac46adc4

Keywords:

Genetic algorithm, Grouping, Multi-Depot Vehicle Routing Problem, routing, Scheduling

Abstract:

The Multi-Depot Vehicle Routing Problem (MDVRP), a n extension of classical VRP, is a NP-hard problem for simultaneously determining the routes for several vehicles from multiple depots to a set of customers and then return to the same depo t. The objective of the problem is to find routes f or vehicles to service all the customers at a minimal cost in terms of number of routes and total travel distance, without violating the capacity and travel time constraints of the vehicles. The solution to the MDVRP, in this paper, is obtained through Genetic A lgorithm (GA). The customers are grouped based on distance to their nearest depots and then routed wi h Clarke and Wright saving method. Further the routes are scheduled and optimized using GA. A set of five different Cordeau’s benchmark instances (p01, p02, p03, p04, p06) from the online resource of University of Malaga, Spain were experimented using MATLAB R2008b software. The results were eval uated in terms of depot’s route length, optimal route, optimal distance, computational time, averag distance, and number of vehicles. Comparison of the experimental results with state-of-the-art tech niques shows that the performance of GA is feasible and effective for solving the multi-depot vehicle r outing problem. Key word: Multi-Depot Vehicle Routing Problem, Grouping, Rout ing, Scheduling, Genetic Algorithm.

Cite this Research Publication

P. Surekha and Sumathi, S., “Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms”, World Applied Programming, vol. 1, no. 3, pp. 118-131, 2011.