Solution to a Multi Depot Vehicle Routing Problem Using K-means Algorithm, Clarke and Wright Algorithm and Ant Colony Optimization

摘要

Vehicle routing problem (VRP) is a very important combinatorial optimisation problem. The subject is simple to explain however tough to attain an optimum solution because of high processing quality. Single-Depot Vehicle routing problem aren't appropriate for sensible things. Vehicle Routing problem with more than one depot are called Multi-Depot VRPS. The Multi-Depot Vehicle Routing Problem (MDVRP) is an extension of classical VRP, may be an NP-hard problem and at the same time determinative for the routes of many vehicles from multiple depots to a collection of customers and come back to the respective depot. The objective of the MDVRP is to serve all customers while minimizing the total travel distance under the constraint that the total demands of served customers cannot exceed the capacity of the vehicle for each route. MDVRP constitutes both location allocation of new depot and also routing of Vehicles. The Location Allocation of new Depots is determined using K-means Clustering algorithm and Routing is done using Clarke & Wright algorithm. The solutions evaluated from the above Clarke & Wright algorithm are then analyzed and compared with Meta heuristics like Ant Colony Optimization.