A guide to vehicle routing heuristics
- PDF / 151,493 Bytes
- 11 Pages / 595 x 794 pts Page_size
- 50 Downloads / 240 Views
#2002 Operational Research Society Ltd. All rights reserved. 0160-5682/02 $15.00 www.palgrave-journals.com/jors
A guide to vehicle routing heuristics J-F Cordeau,1 M Gendreau,2 G Laporte,1* J-Y Potvin2 and F Semet3 1´ Ecole des Hautes E´tudes Commerciales, Montre´al, Canada; 2Universite´ de Montre´al, Montre´al, Canada; and 3Universite´ de Valenciennes et du Hainaut Cambresis, Valenciennes, France
Several of the most important classical and modern heuristics for the vehicle routing problem are summarized and compared using four criteria: accuracy, speed, simplicity and flexibility. Computational results are reported. Journal of the Operational Research Society (2002) 53, 512–522. DOI: 10.1057=palgrave=jors=2601319 Keywords: vehicle routing problem; heuristics
Introduction The Vehicle Routing Problem (VRP), introduced by Dantzig and Ramser1 in 1959, holds a central place in distribution management and has become one of the most widely studied problems in combinatorial optimization. The Classical VRP can be formally defined as follows. Let G ¼ ðV ; AÞ be a graph where V ¼ fv0 ; v1 ; . . . ; vn g is a vertex set, and A ¼ fðvi ; vj Þ : vi ; vj 2 V ; i 6¼ jg is an arc set. Vertex v0 represents a depot, while the remaining vertices correspond to customers. With A are associated a cost matrix ðcij Þ and a travel time matrix ðtij Þ. If these matrices are symmetrical, as is commonly the case, then it is standard to define the VRP on an undirected graph G ¼ ðV ; EÞ, where E ¼ fðvi ; vj Þ : vi ; vj 2 V ; i < jg is an edge set. Each customer has a non-negative demand qi and a service time ti . A fleet of m identical vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of designing a set of at most m delivery or collection routes such that (1) each route starts and ends at the depot, (2) each customer is visited exactly once by exactly one vehicle, (3) the total demand of each route does not exceed Q, (4) the total duration of each route (including travel and service times) does not exceed a preset limit D, and (5) the total routing cost is minimized. A common variant is where a time window ½ai ; bi is imposed on the visit of each customer. Several other extensions have also been studied; the vehicle fleet may be heterogeneous,2 vehicles may perform both collections and deliveries on the same route,3 some vehicles may be unable to visit certain sites,4 some customers may require several visits over a given time period,5 there may exist more than one depot,5 deliveries may be split among *Correspondence: G Laporte, Centre de recherche sur les transports (C.R.T.), Campus de I’Universite´ de Montre´al, C.P. 6128, Succursale Centre-ville, Montre´al H3C 3J7, Canada.
several vehicles,6 etc. For overview articles on the VRP, see Golden and Assad,7 Fisher,8 Desrosiers et al,9 Crainic and Laporte,10 Toth and Vigo,11 Laporte and Semet,12 Gendreau et al13 and Cordeau et al.14 The VRP is a hard combinatorial optimization problem and only relati
Data Loading...
