A Lexisearch Algorithm for the Distance-Constrained Vehicle Routing Problem

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.