Conference article

The classical capacitated Vehicle Routing Problem (VRP) consists in determining optimal delivery routes for a set of homogeneous vehicles to serve a set of customers. Each route is covered by one vehicle without exceeding its capacity. Moreover; each route starts and ends at the same depot. Each customer is served exactly once. In this paper; we consider the Vehicle Routing Problem with Accessibility constraints (VRPA) which is defined on a graph of which vertices are partitioned into two sub-sets V1 and V2; served by two types of vehicles; i.e. Truck and truck + trailer. The customers of V1 are accessible by both vehicles types whereas the customers of V2 are only accessible by the trucks. The VRPA is a generalization of the VRP; it possesses numerous applications in domains such as logistics; economic planning of distribution networks and their management. The classic capacitated vehicle routing problem; a special case of the VRPA where V2 is empty; has been studied extensively. The VRP is known to be NP-Hard; so VRPA is also a NP-hard problem. Generally; exact methods for NP-hard problem do not allow even moderately-sized problems to be solved. Heuristic approaches are needed to solve large scale instances of practical problems. Variable Neighborhood Search (VNS); introduced by Hansen and N. Mladenovic is a recent metaheuristic which exploits systematically the idea of neighbourhood change; both in the descent to local minima and in the escape from the valleys which contain them. For solving the VRPA by VNS we exploit the connection of this location and routing problem with close and particular cases. The neighborhood structures used can be classified in three categories according to the number of routes involved in the corresponding move : i) for a unique route we use the generalized adding/dropping procedure as proposed in GENIUS heuristic for traveling salesman problem; ii) for the two routes we use classical VRP moves such that dropping; adding; swapping; iii) for several routes we consider the move which consist to open or close a depot as done in location problem.

We propose various implementations of a Modified Variable Neighborhood Search (MVNS) method for the resolution of the VRPA; differentiated basing on the following criteria: local search method; choice of the neighbor solution; Sequence of neighborhoods. Test problems were generated in order to validate and determine the best implementation. MVNS method gives good results for VRPA. An improvement of MVNS method can be obtained by hybridization with a tabu search method.

No keywords available