Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

12-2019

Abstract

Vehicle Routing Problem (VRP) is a combinatorial problem where a certain set of nodes must be visited within a certain amount of time as well as the vehicle’s capacity. There are numerous variants of VRP such as VRP with time windows, where each node has opening and closing time, therefore, the visiting time must be during that interval. Another variant takes time-dependent constraint into account. This variant fits real-world scenarios, where at different period of time, the speed on the road varies depending on the traffic congestion. In this study, three objectives – total traveling time, total traveling distance, and the number of vehicles are considered with both time-dependent and time windows constraints to yield a model that is applicable to real-world problems. A metaheuristic - Harmony Search Algorithm (HSA) is then proposed for solving this Time Dependent Vehicle Routing Problem with Time Windows (TDVRPTW). In addition to the harmony memory and pitch adjustment mechanism for constructing new solutions, several local search operators and a Roulette wheel are also embedded to improve the performance of the HSA. The performance of the proposed algorithm was verified by testing on a set of well-known benchmark instances (56 Solomon’s VRP instances) by adding the speed matrix. The experiment results show that HSA is able to perform better in some instances when compare with the heuristic method in Figliozzi (2012) among all three speed-levels. HSA is also able to outperform the Genetic Algorithm (GA) proposed by Kumar (2015) in R1, R2, RC1, and RC2 instances for both the number of vehicles and the total traveling time. The research outcomes suggest that HSA can be used to solve TDVRPTW with comparable results to other commonly used metaheuristic approaches.

Keywords

vehicle routing problem, time-dependent, time windows, harmony search algorithm, combinatorial optimization problem

Discipline

Artificial Intelligence and Robotics | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of APIEMS 2019: The 20th Asia Pacific Industrial Engineering And Management Systems, Kanazawa, Japan, December 2-5

First Page

753

Last Page

757

ISBN

9784924861534

Publisher

APIEMS

City or Country

Kanazawa, Japan

Copyright Owner and License

Authors

Additional URL

http://www.apiems2019.org/

Download

Share

COinS