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

Kurzfassung

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) is developed based on the algorithm of Dorigo, in which the ants communicate pheromones both locally and globally and meanwhile the constraints are handled by setting penalties. 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.