An efficient algorithm applied to capacitated vehicle routing problem with consideration of time windows by using ranking-based concept and dynamic programming

Abstract

© 2019 ACM. Capacitated Vehicle Routing Problem and Time-Windows (CVRPTW) is one of the most well-known variations of Vehicle routing problems (VRP), which is a combinatorial optimization and can be classified as NP-hard problem. A considerable number of solving techniques have been proposed not only exact and heuristic, but also metaheuristic methods. Although the optimal solution can be guaranteed applying the exact algorithms, computational time is the most concern when the problem size is increased. Heuristic methods normally provide solutions with a very fast speed but most of them are local optima. Metaheuristic methods are also other approaches to solve this problem providing much larger search space. However, most of them are on the basis of experiments requiring an extensive number of parameter settings. In this research, a novel efficient approach to solve CVRPTW is proposed using the several concepts of graph traversal with breadth-first search and ranking-based algorithm during the initial route construction, and Dynamic programming is then used for solution improvement with regarding to capacity constraints and time windows. The performance of the proposed method compared to the state-of-the-art algorithms will be very competent in terms of both solution quality and computational time with no effort on parameter settings as a major advantage.