Efficient heuristic methods for berth allocation at multi-line, multi-berth curbside bus stops

Minyu Shen, Weihua Gu, Sangen Hu, Feng Xiao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

Transit management agencies often pre-allocate a multi-berth stop's berths to specific bus lines so that passengers can find the right place to wait for their buses. Developing optimal berth allocation plans that minimize the total bus delay is essential for mitigating bus queues at busy multi-berth stops. However, this problem is challenging due to the huge solution space, the high degree of stochasticity in bus queues, and the resulting extremely high computational cost. In this paper, we first propose a simple heuristic method inspired by queueing theory. It is based on the idea that evenly distributing the total traffic intensity (defined as the total bus arrival rate times the mean dwell time) among all the berths would produce a lower bus delay. Numerical results demonstrate that this simple method generated very good berth allocation plans (with optimality gaps <6% for no-overtaking and free-overtaking stops) in seconds! It does not rely on time-consuming simulation surrogate models or numerous input data such as the stochastic bus arrival processes and dwell time distributions of each bus line. To further improve the simple heuristic's performance (especially for limited-overtaking stops), we develop a cluster-based nested partition algorithm that can find a near-optimal plan (e.g., with an optimality gap of <3%) in a much shorter time than a previous algorithm. The algorithm employs the simple heuristic plan as the initial solution. Our methods can be applied to stops with various berth numbers, different proximities to nearby traffic signals, and under diverse bus queueing rules.

Original languageEnglish
Article number104269
JournalTransportation Research Part C: Emerging Technologies
Volume154
DOIs
Publication statusPublished - Sept 2023

Keywords

  • Berth allocation
  • Bus delays
  • Bus stop queues
  • Nested partition
  • Simulation-based optimization
  • Traffic intensity

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Automotive Engineering
  • Transportation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Efficient heuristic methods for berth allocation at multi-line, multi-berth curbside bus stops'. Together they form a unique fingerprint.

Cite this