Evolutionary Algorithms for Vehicle Routing ProblemsHa Trung
The Vehicle Routing Problem (VRP) is used to design an optimal route for a fleet of vehicles to service a set of customers, given a set of constraints. VRP is introduced by Dantzig and Ramser in 1959 and is of the NP-hard type. The VRP is used in supply chain management in the physical delivery of goods and services.
Variations to the VRP are formulated based on the nature of the transported goods, the quality of service required and the characteristics of the customers and the vehicles. Variations are: Capacitated VRP (CVRP); VRP with time windows (VRPTW); Fleet size and mix VRP (FSMVRP); Open VRP (OVRP); Multi-depot VRP (MDVRP); Periodic VRP (PVRP); VRP with backhauls (VRPB); Pickup and delivery problem (PDP); Dynamic VRP (DVRP or On-line VRP); VRP with stochastic demands (VRPSD or SRP), etc.
In our study, we considered approaches for solving CVRP and DVRP. We developed a program with simulation, using a genetic algorithm and a developed a heuristic to solve CVRP and DVRP.