An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem

L. Caccetta, M. Alameen, M. Abdul-Niby

Abstract


This paper proposes an effective hybrid approach that combines domain reduction with the Clarke and Wright algorithm to solve the capacitated vehicle routing problem. The hybrid approach is applied to solve 10 benchmark capacitated vehicle routing problem instances. The dimension of the instances was between 21 to 200 customers. The results show that domain reduction can improve the classical Clarke and Wright algorithm by about 18%. The hybrid approach improves the large instances significantly in comparison with the smaller size instances. This paper will not show the time taken to solve each instance, as the Clarke and Wright algorithm and the hybrid approach took almost the same CPU time.


Keywords


Clarke and Wright; capacitated vehicle routing problem; domain reduction

Full Text:

PDF

References


C. Groër, Parallel and serial algorithms for vehicle routing problems, PhD Thesis, University of Maryland, ProQuest, 2008

G. B. Dantzig, J. H. Ramser, “The truck dispatching problem”, Management Science, Vol. 6, No. 1, pp. 80-91, 1959

N. Christofides, S. Eilon, “An algorithm for the vehicle dispatching problem”, Operational Research, Vol. 20, No. 3, pp. 309-318, 1969

N. R. Achuthan, L. Caccetta, S. P. Hill, “A new subtour elimination constraint for the vehicle routing problem”, European Journal of Operational Research, Vol. 91, No. 3, pp. 573-586, 1996

N. R. Achuthan, L. Caccetta, “Integer linear programming formulation for a vehicle routing problem”, European Journal of Operational Research, Vol. 52, No. 1, pp. 86-89, 1991

G. Clarke, J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, Vol. 12, No. 4, pp. 568-581, 1964

A. A. Juan, J. Faulin, R. Ruiz, B. Barrios, S. Caballé, “The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem”, Applied Soft Computing, Vol. 10, No. 1, pp. 215-224, 2010

A. A. Juan, J. Faulin, J. Jorba, D. Riera, D. Masip, B. Barrios, “On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics”, Journal of the Operational Research Society, Vol. 62, No. 6, pp. 1085-1097, 2011

T. Pichpibul, R. Kawtummachai, “New enhancement for Clarke-Wright savings algorithm to optimize the capacitated vehicle routing problem”, European Journal of Scientific Research, Vol. 78, No. 1, pp. 119-134, 2012

K. Kanthavel, P. Prasad, “Optimization of capacitated vehicle routing problem by nested particle swarm optimization”, American Journal of Applied Sciences, Vol. 8, No. 2, pp. 107-112, 2011

L. Xiaodong, “A summarization of algorithms for vehicle routing problem with time windows”, European Journal of Scientific Research, Vol. 73, No. 3, pp. 296-309, 2012

A. Caprara, M. Locatelli, “Global optimization problems and domain reduction strategies”, Mathematical Programming, Vol. 125, No. 1, pp. 123-137, 2010

M. Groetschel, C. L. Monma, M. Stoer, “Computational results with a cutting plane algorithm for designing communication networks with low connectivity constraints”, Operations Research, Vol. 40, No. 2, pp. 309-330, 1992

S. Eilon, C. D. T. Watson-Gandy, N. Christofides, Distribution management: mathematical modelling and practical analysis, Griffin, London, 1971

M. Held, R. M. Karp, “The traveling salesman problem and minimum spanning trees”, Operations Research, Vol. 18, No. 6, pp. 1138-1162, 1970

N. Christofides, A. Mingozzi, P. Toth, “The vehicle routing problem”, in Combinatorial Optimization. Wiley, Chichester, pp 315-338,1979

Branch Cut and Price Resource Web, Vehicle Routing Data Sets USA, http://www.coin-or.org/SYMPHONY/branchandcut/VRP/data




eISSN: 1792-8036     pISSN: 2241-4487