Vehicle routing problem

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?"It generalises the travelling salesman problem (TSP).It first appeared in a paper by George Dantzig and John Ramser in 1959,[1] in which the first algorithmic approach was written and was applied to petrol deliveries.The objective of the VRP is to minimize the total route cost.Therefore, commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimized.Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type.To do this our original graph is transformed into one where the vertices are the customers and depot, and the arcs are the roads between them.For each pair of vertices i and j, there exists an arc (i,j) of the complete graph whose cost is written asis the sum of the travel times of the arcs on the shortest path from i to j on the original road graph.To deal with these situations a priority variable for each customer can be introduced or associated penalties for the partial or lack of service for each customer given [2] The objective function of a VRP can be very different depending on the particular application of the result but a few of the more common objectives are:[2] Several variations and specializations of the vehicle routing problem exist: Several software vendors have built software products to solve various VRP problems.corresponds to the minimum number of vehicles needed to serve setConstraints 5 are the capacity cut constraints, which impose that the routes must be connected and that the demand on each route must not exceed the vehicle capacity.⁠(minimum number of vehicles needed to serve set[2] GCECs and CCCs have an exponential number of constraints so it is practically impossible to solve the linear relaxation.A possible way to solve this is to consider a limited subset of these constraints and add the rest if needed.Efficient exact separation methods for such constraints (based on mixed integer programming) have been developed.[10] A different method again is to use a family of constraints which have a polynomial cardinality which are known as the MTZ constraints, they were first proposed for the TSP [11] and subsequently extended by Christofides, Mingozzi and Toth.is an additional continuous variable which represents the load left in the vehicle after visiting customerThese have been used extensively to model the basic VRP (CVRP) and the VRPB.Hence we cannot use this for more complex models where the cost and or feasibility is dependent on the order of the customers or the vehicles used.[2] There are many methods to solve vehicle routing problems manually.For example, optimum routing is a big efficiency issue for forklifts in large warehouses.[13][14] Due to the difficulty of solving to optimality large-scale instances of vehicle routing problems, a significant research effort has been dedicated to metaheuristics such as Genetic algorithms, Tabu search, Simulated annealing and Adaptive Large Neighborhood Search (ALNS).Some of the most recent and efficient metaheuristics for vehicle routing problems reach solutions within 0.5% or 1% of the optimum for problem instances counting hundreds or thousands of delivery points.[15] These methods are also more robust in the sense that they can be more easily adapted to deal with a variety of side constraints.