This paper proposes a metaheuristic algorithm to solve the dial-a-ride problem (DARP) with time windows and capacity restrictions. The algorithm was developed for the project "HubChain", which proposes an on demand system being integrated with local public transport in the Elde rural region, in northern Germany. Users can request their trips via an online platform by providing the origin and destination as well as the desired arrival or departure time. To solve the problem, ant colony optimization with penalties (ACOP), in which the ants communicate pheromones both locally and globally and meanwhile the constraints are handled by setting penalties, is developed. To validate the results, the proposed algorithm and an exact algorithm were run for multiple test scenarios using the simulation SUMO as a framework. The routes obtained with the proposed algorithm show travel times comparable to the optimal routes, yet obtained in low computation times. This allows therefore the implementation of the proposed ACOP algorithm in a dynamic booking system.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An ant colony algorithm with penalties for the dial-a-ride problem with time windows and capacity restriction


    Contributors:


    Publication date :

    2021-06-16


    Size :

    2365078 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



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

    Ho, Song Guang / Koh, Hong Wei / Pandi, Ramesh Ramasamy et al. | IEEE | 2018



    A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows

    Jaw, Jang-Jei / Odoni, Amedeo R. / Psaraftis, Harilaos N. et al. | Elsevier | 1984


    A dial-a-ride problem with driver preferences

    Ouasaid, Sana / Saddoune, Mohammed | IEEE | 2021


    GPU-Accelerated Tabu Search Algorithm for Dial-A-Ride Problem

    Pandi, Ramesh Ramasamy / Ho, Song Guang / Nagavarapu, Sarat Chandra et al. | IEEE | 2018