Methods of Capacitated Vehicle Routing Problem based on Constraints

Abstract

The Vehicle Routing Problem (VRP) is a combinatorial optimization and integer programming problem which asks “What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?” In our paper to describe the Methods of Capacitated Vehicle Routing Problem we implement using c code the Clarke and Wright’s savings algorithm to solve our problem where the constraints are to find a solution which minimizes the total transportation costs, demand and capacity of a vehicle. Furthermore, the solution must satisfy the restrictions that every customer is visited exactly once, where the demanded quantities are delivered, and the total demand on every route must be within the vehicle’s capacity. The transportation costs are specified as the cost of driving from any city to any other city. The costs are identical in the two directions between two given points. We use this above methodology in solving both Single and Multi depot vehicle routing problem and compare their results.