A Lexisearch Algorithm for the Distance-Constrained Vehicle Routing Problem

AUTHOR(S):

TITLE

A Lexisearch Algorithm for the Distance-Constrained Vehicle Routing Problem

PDF BIBTEX

ABSTRACT

The vehicle routing problem (VRP), belongs to the class of NP-hard problems, is considered as one of the most difficult problems. The problem aims to serve a number of customers with a fleet of vehicles that can be defined as to find an optimal set of tours with minimum cost to connect the depot to n customers with m vehicles, such that every customer is visited exactly once; every vehicle starts and ends its tour at the depot. Out of many variations of the problem, we consider here distance-constrained VRP (DVRP) where the total travelled distance by each vehicle in the solution is less than or equal to the maximum possible travelled distance. The problem has many applications in real-life and no any polynomial time exact algorithm is available to solve the problem, and even small sized instances may require long computation time. However, there are some situations where exact solution is required. Therefore, we look for exact solution to the problem, and accordingly, we develop a lexisearch algorithm to obtain exact solution to the problem, and present solution for the DVRP using some TSPLIB instances of various sizes.

KEYWORDS

The vehicle routing problem, distance-constrained, exact algorithm, lexisearch

REFERENCES

[1] VT. Paschos, An overview on polynomial approximation of np-hard problems, Yugoslav Journal of Operations Research, 19(1), 2009, pp. 3-40. [1] VT. Paschos, An overview on polynomial approximation of np-hard problems, Yugoslav Journal of Operations Research, 19(1), 2009, pp. 3-40.

[2] G. Laporte, The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59(3), 1992, pp. 345–358.

[3] GB. Dantzig, and JH. Ramser, The truck dispatching problem, Management Science, 6, 1959, pp. 80–91.

[4] JK. Lenstra, and AHG. Rinnooy Kan, Some simple applications of the travelling salesman problem, Operational Research Quarterly, 26(4), 1975, pp. 717-733.

[5] GL. Nemhauser, and LA. Wolsey, Discrete Mathematics and Optimization, Wiley, New York, Chichester, 1988.

[6] P. Toth, and D. Vigo, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002.

[7] R. Baldacci, A. Mingozzi, and R. Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints (invited review), European Journal of Operational Research, 218(1), 2012, pp. 1–6.

[8] R. Baldacci, and A. Mingozzi, Lower bounds and an exact method for the Capacitated Vehicle Routing Problem, Service Systems and Service Management, 2, 2006, pp. 1536–1540.

[9] ML. Fisher, Optimal solution of Vehicle Routing Problems using minimum k-trees, Operations Research, 42, 1988, pp. 626–642.

[10] R. Baldacci, P. Toth, and D. Vigo, Recent advances in vehicle routing exact algorithms, 4OR, 5(4), 2007, pp. 269–298.

[11] A. Pessoa, M. Poggi de Arago, and E. Uchoa, Robust branch-cut-and-price algorithms for vehicle routing problems, In: B. Golden, et al. (Eds.), The Vehicle Routing Problem Latest Advances and New Challenges, Operations Research/Computer Science Interfaces Series, vol. 43, Part II, 2008, pp. 297–325.

[12] J. Gondzio, P. Gonzlez-Brevis, and P. Munari, New developments in the primal dual column generation technique, European Journal of Operational Research, 224(1), 2013, pp. 41– 51.

[13] G. Laporte, and M. Desrochers, Two exact algorithms for the distance-constrained vehicle Z. H. Ahmed International Journal of Mathematical and Computational Methods http://www.iaras.org/iaras/journals/ijmcm ISSN: 2367-895X 171 Volume 1, 2016 routing problem, Networks, 14, 1984, pp. 161- 172.

[14] G. Laporte, Y. Nobert, and M. Desrochers, Optimal routing under capacity and distance restrictions, Operations Research, 33(5), 1985, pp. 1050-1073.

[15] G. Laporte, Y. Nobert, and S. Taillefer, A branch and bound algorithm for the asymmetrical distance-constrained vehicle routing problem, Mathematical Modelling, 9(12), 1987, pp. 875-868.

[16] G. Clarke, and JW. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12(4), 1964, pp. 568-581.

[17] CL. Li, D. Simchi-Levi, and M. Desrochers, On the distance constrained vehicle routing problem, Operations Research, 40(4), 1992, pp. 790-799.

[18] S. Almoustafa, S. Hanafi, and N. Mladenovic, New exact method for large asymmetric distance-constrained vehicle routing problem, European Journal of Operational Research, 226, 2013, pp. 386–394.

[19] J. Brimberg, P. Hansen, and N. Mladenovic, Attraction probabilities in variable neighborhood search, 4OR, 8, 2010, pp. 181– 194.

[20] P. Hansen, N. Mladenovic, and JA. Moreno Prez, Variable neighbourhood search: methods and applications, Annals of Operations Research, 175(1), 2010, pp. 367–407.

[21] N. Mladenovic, D. Urosevic, S. Hanafi, and A. Ilic, A General variable neighborhood search for the One-commodity pickup-and-delivery travelling salesman problem, European Journal of Operational Research, 220(1), 2012, pp. 270–285.

[22] GB. Dantzig, DR. Fulkerson, and SM. Johnson, Solution of a large-scale traveling salesman problem, Operations Research, 2, 1954, pp. 393–410.

[23] ZH. Ahmed, A lexisearch algorithm for the bottleneck traveling salesman problem, International Journal of Computer Science and Security, 3(6), 2010, pp. 569-577.

[24] ZH. Ahmed, A data-guided lexisearch algorithm for the asymmetric traveling salesman problem, Mathematical Problems in Engineering, Vol. 2011, Article ID 750968, 18 pages, doi:10.1155/2011/750968.

[25] ZH. Ahmed, A data-guided lexisearch algorithm for the bottleneck traveling salesman problem, International Journal of Operational Research, 12(1), 2011, pp. 20-33.

[26] ZH. Ahmed, An exact algorithm for the clustered traveling salesman problem, OPSEARCH, 50 (2), 2013, pp. 215-228.

[27] ZH Ahmed, A new reformulation and an exact algorithm for the quadratic assignment problem, Indian Journal of Science and Technology, 6(4), 2013, pp. 4368-4377.

[28] TSPLIB Website, http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/

Cite this paper

Zakir Hussain Ahmed. (2016) A Lexisearch Algorithm for the Distance-Constrained Vehicle Routing Problem. International Journal of Mathematical and Computational Methods, 1, 165-174