Evolutionary Algorithms for Vehicle Routing Problems

Evolutionary Algorithms for Vehicle Routing Problems

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.

ea-vr1Variations 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.

ea-vr2

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.

social position advance

Share this post