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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Solving Time-dependent Dial-a-ride Problem using Greedy Ant Colony Optimization




    Publication date :

    2018-11-01


    Size :

    768959 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Dial-a-Ride

    Jørgensen, Rene Munk | BASE | 2003

    Free access

    Mitigating Traffic Congestion: Solving the Ride-Matching Problem by Bee Colony Optimization

    Teodorović, Dušan / Dell’ Orco, Mauro | Taylor & Francis Verlag | 2008




    Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem

    Gschwind, Timo / Irnich, Stefan | British Library Online Contents | 2015