Harmony search algorithm for time-dependent vehicle routing problem with time windows

• Main Authors: LIANG, Yun-Chia, MINANDA, Vanny, GUNAWAN, Aldy, CHEN, Angela Hsiang-Ling
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: vehicle routing problem; time-dependent; time windows; harmony search algorithm; combinatorial optimization problem; Artificial Intelligence and Robotics; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4830; https://ink.library.smu.edu.sg/context/sis_research/article/5833/viewcontent/Collective_Outsourcing_COM_pv.pdf
• Institution: Singapore Management University

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.