Article | Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society | Modified Variable Neighborhood Search for the Vehicle Routing Problem with Accessibility Constraints

Title:
Modified Variable Neighborhood Search for the Vehicle Routing Problem with Accessibility Constraints
Author:
Mahdi Souid: UVHC/LAMIH/ROI, France Sa├»d Hanafi: UVHC/LAMIH/ROI, France Fréderic Semet: UVHC/LAMIH/ROI, France
Download:
Full text (pdf)
Year:
2004
Conference:
Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Issue:
014
Article no.:
026
No. of pages:
1
Publication type:
Abstract
Published:
2004-12-28
Series:
Link├Âping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Link├Âping University Electronic Press; Link├Âpings universitet


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.

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Mahdi Souid, Sa├»d Hanafi, Fréderic Semet
Title:
Modified Variable Neighborhood Search for the Vehicle Routing Problem with Accessibility Constraints
References:
No references available

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Mahdi Souid, Sa├»d Hanafi, Fréderic Semet
Title:
Modified Variable Neighborhood Search for the Vehicle Routing Problem with Accessibility Constraints
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment