A New Hybrid Algorithm to Solve the Vehicle Routing Problem in the Dynamic Environment

摘要

The Dynamic Vehicle Routing Problem (DVRP) is a natural extension of the classical Vehicle Routing Problem (VRP) which consists in designing routes for a fleet of capacitated vehicles that are to service a set of geographically dispersed points at the least cost. In DVRP, new customer demands are received along the day. Hence, they must be serviced at their locations by a set of vehicles in real time. In this research, to solve the DVRP, this later is decomposed into a series of static VRP and then a static solving algorithm which gives a quick and effectively good feasible solution in a given time is applied to each static VRP. This algorithm is a hybridization obtained by combining an Ant Colony Optimization (ACO) algorithm with a Large Neighborhood Search (LNS) algorithm. The computational experiments were applied to 22 benchmarks instances with up to 385 customers and the effectiveness of the proposed approach is validated by comparing the computational results with those earlier presented in the literature.