Solving time-dependent dial-a-ride problem using modified ant colony optimization

• Main Author: Koh, Hong Wei
• Other Authors: Justin Dauwels
• Format: Final Year Project
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: http://hdl.handle.net/10356/75159
• Institution: Nanyang Technological University

Traffic congestions pose great problems for businesses which provide shuttle services and logistic services as they have strict timings to adhere to. Delays caused by traffic congestions can cause late arrivals at customers and incur extra daily costs to the businesses. Therefore it is important for these businesses to be able to plan routes such that they can work around the delays by estimating time-dependent travel time to avoid these traffic congestions. By estimating time-dependent travel time, vehicles routes could be different as compared to reverse case. To achieve this goal, we introduce linear regression methods to translate speed data into meaningful information that can give us more precise details about the speed data. We also formulate a custom numerical integration method that is implemented in our scheduling and routing algorithm to estimate time-dependent travel time using regression models which are regressed from speed models. Results from our testing showed significant improvements in the performance of routes generated by the improved routing algorithm as compared to the routing algorithm without time-dependent travel time estimation, when tested against speed models. We observe that the solutions generated by the improved routing algorithm gave us better estimation of actual travel time and reduced frequency of late arrivals.