All Title Author
Keywords Abstract

A Novel Three-Phase Approach for Solving Multi-Depot Vehicle Routing Problem with Stochastic Demand

DOI: 10.5923/j.algorithms.20120104.01

Keywords: Multi-Depot Vehicle Routing Problem, Sum of Subset, Greedy Method

Full-Text   Cite this paper   Add to My Lib


The Multi-Depot Vehicle Routing Problem (MDVRP), an 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 with demand and then return to the same depot. Main goal of this thesis is to solve MDVRPSD in three phases. Firstly we’ve used nearest neighbour classification method for grouping the customers, then Sum of Subset method have been used for routing. Finally the routes are optimized using greedy method. The routes obtained using these methods are better for the vehicles considering demands of the customers. As an input we consider here some customers position, the depots position. Also the demand is initialized randomly. Here we solve the problem for 4 depots to 10 depots. The input customer ranges from 20 to 50. Then by using the three-phases the problem is solved for the input combinations. Actually the main target to solve this problem is to reduce the number of vehicles needed to serve the customers. We have to serve the customers of a definite route by a vehicle. So if the routes are minimized then number of needed vehicles is also minimized. The time is also an important issue. So the time is also measured for solving the whole problem with three-phases. So at the last part of the paper the performance is measured according to time for solving the problem and the number of vehicle needed for each of the problem.


comments powered by Disqus