A large neighborhood search algorithm to optimize a demand-responsive feeder service

Authors

Bryan David Galarza Montenegro
Kenneth Sörensen
Pieter Vansteenwegen

Document Type

Journal Article

Publication Date

2021

Subject Area

mode - bus, mode - demand responsive transit, ridership - demand, operations - performance, infrastructure - stop, planning - integration, planning - methods, planning - service quality

Keywords

Meta-heuristics, Large neighborhood search, Public bus transport, Feeder service, Demand-responsive transportation

Abstract

Feeder services are public transit services that transport people from a low demand, typically suburban, area to a high demand area, such as a transportation hub or a city. Here, passengers continue their journey using traditional forms of public transport. On the one hand, on-demand feeder services have been a topic of discussion in a number of recent studies, since these services can serve the demand efficiently. On the other hand, traditional feeder services with predetermined routes and timetables provide predictability and easier cost control. In this paper, a demand-responsive feeder service is considered, which combines positive characteristics of both traditional services as well as on-demand-only services. This feeder service has mandatory bus stops which are always serviced, as well as optional bus stops which are only serviced when there is demand for transportation nearby. To optimize the performance of this feeder service, a large neighborhood search heuristic is developed. Experimental results on 14 benchmark instances illustrate that the LNS algorithm obtains solutions with an average gap of 1% or less compared to the optimal solution, within 1s of runtime. Larger instances can also be solved, typically in less than 60s. The results also show that the demand-responsive feeder service generally outperforms a traditional service in terms of service quality, often by more than 60%.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part C Home Page:

http://www.sciencedirect.com/science/journal/0968090X

Recommended Citation

Galarza Montenegro, B.D., Sörensen, K., & Vansteenwegen, P. (2021). A large neighborhood search algorithm to optimize a demand-responsive feeder service. Transportation Research Part C: Emerging Technologies, Vol. 127, 103102.