Traffic congestion is a huge problem for transportation service providers, which causes delay and incurs excessive operational cost. Many algorithms exist for the dial-a-ride problem (DARP), which assumes constant travel times throughout the day. This may cause serious constraint violations when they are applied in the real-world, where time-varying travel times are observed. This paper aims to solve time-dependent dial-a-ride problem (TDDARP). A new greedy ant colony optimization (GACO) algorithm is developed, in which two new decision factors (repeat counter and quantity counter) are introduced to efficiently explore the search space. In addition, a method for estimating travel time using staircase regression (SR) of speed data is developed, which in turn is incorporated into GACO. Computational experiments conducted on several DARP benchmark instances in the literature show the significance of incorporating time-dependent travel times into designing high quality solution for TDDARP, while considering peak hour traffic congestion. On average, GACO attains solutions with 88.77% less time window constraint violation and 98.04% less ride time constraint violation after taking time-dependent travel times into account.
Solving Time-dependent Dial-a-ride Problem using Greedy Ant Colony Optimization
2018-11-01
768959 byte
Conference paper
Electronic Resource
English
Mitigating Traffic Congestion: Solving the Ride-Matching Problem by Bee Colony Optimization
Taylor & Francis Verlag | 2008
|Mitigating Traffic Congestion: Solving the Ride-Matching Problem by Bee Colony Optimization
Online Contents | 2008
|DSpace@MIT | 1984
|Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem
British Library Online Contents | 2015
|