Publication: An efficient algorithm applied to capacitated vehicle routing problem with consideration of time windows by using ranking-based concept and dynamic programming
5
Issued Date
2019-05-24
Resource Type
Other identifier(s)
2-s2.0-85071044431
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
ACM International Conference Proceeding Series. (2019), 267-274
Suggested Citation
Cheng Heng Uy, Nattanee Charoenlarpkul, Thana Sarttra, Supphachan Rajsiri An efficient algorithm applied to capacitated vehicle routing problem with consideration of time windows by using ranking-based concept and dynamic programming. ACM International Conference Proceeding Series. (2019), 267-274. doi:10.1145/3335550.3335588 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/50632
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
An efficient algorithm applied to capacitated vehicle routing problem with consideration of time windows by using ranking-based concept and dynamic programming
Other Contributor(s)
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.