Relaxation methods for fixed route demand responsive transit

Abstract

This article examines a partially responsive ride-sharing transit service with predetermined cyclic routes and deterministic travel times. The main operational challenge is setting the time schedule, which varies from day to day in response to upfront passenger requests. The need of passengers to adjust their departure times from their desired value causes inconvenience, which we wish to minimize. A previous study of the fixed route dial a ride problem (FRDARP) considered strict fleet constraints. We  solve two relaxed formulations, related to the one-dimensional p-median location problem, by efficient dynamic programming embedding the SMAWK algorithm. Numerical results show the potential benefit of the FRDARP compared to fixed schedule (traditional) service and illustrate the impact of demand level and fleet constraints. In addition, based on these results, we characterize the wide range of scenarios where an easier to solve relaxed formulation can be nearly as useful as the constrained formulation.

KEYWORDS:

• Fixed route dial-a-ride problem
• dial-a-ride problem
• demand responsive transit
• location problems
• scheduling

Acknowledgements

Special thanks to Hagai Ilani for his help, constant encouragement, advice, and support at the early stages of this study.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 CPLEX is a library of IBM-Ilog which includes numerous optimization algorithms for solving linear programing problems.

Additional information

Funding

This research was partially supported by the Israeli Ministry of Science, Technology and Space; The Israeli Centre for Promoting Research in Smart Transportation; and Ben-Gurion University of the Negev.

Notes on contributors

Oksana Pecherski Sabinik

Oksana Pecherski Sabinik is a lecturer in Statistics and Performance Research at the Department of Industrial Engineering and Management at Sami Shamoon College of Engineering. She received her B.Tech (Industrial Engineering and Management) from the Sami Shamoon College of Engineering and MSc (Industrial Engineering and Management) from the Ben-Gurion University. She is currently a doctoral (PhD) student at the Department of Industrial Engineering and Management at Ben-Gurion University, studying demand responsive transit (DRT) services.

Hillel Bar-Gera

Hillel Bar-Gera is a professor at the Department of Industrial Engineering and Management at Ben-Gurion University. His degrees are from the Hebrew University (BSc, MSc) and the University of Illinois at Chicago (PhD). His research on traffic safety and transportation systems combines quantitative methods, large scale dataset analysis, simulator studies, and field experiments.