An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem
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 reductionDownloads
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 DOI: https://doi.org/10.1287/mnsc.6.1.80
N. Christofides, S. Eilon, “An algorithm for the vehicle dispatching problem”, Operational Research, Vol. 20, No. 3, pp. 309-318, 1969 DOI: https://doi.org/10.1057/jors.1969.75
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 DOI: https://doi.org/10.1016/0377-2217(94)00332-7
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 DOI: https://doi.org/10.1016/0377-2217(91)90338-V
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 DOI: https://doi.org/10.1287/opre.12.4.568
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 DOI: https://doi.org/10.1016/j.asoc.2009.07.003
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 DOI: https://doi.org/10.1057/jors.2010.29
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 DOI: https://doi.org/10.3844/ajassp.2011.107.112
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 DOI: https://doi.org/10.1007/s10107-008-0263-4
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 DOI: https://doi.org/10.1287/opre.40.2.309
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 DOI: https://doi.org/10.1287/opre.18.6.1138
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
Downloads
How to Cite
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
