PDFAbstract: 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
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
Copyright © 2016 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0