Personalised and Coordinated Demand-Responsive Feeder Transit Service Design: A Genetic Algorithms Approach

Bo Sun, Ming Wei, Chunfeng Yang, Zhihuo Xu, Han WangFuture 2018 · DOI

TL;DR

This paper introduces a novel optimization framework for demand-responsive feeder transit services that integrates personalized passenger travel preferences (like subway schedules) with the synchronous coordination of feeder buses and rail transit. By using a mixed-integer programming model and a distributed genetic algorithm, they significantly reduce total passenger travel time by optimizing ride and wait times, demonstrating a 2.46% improvement over traditional methods.

What Problem Does This Paper Address?

The "first-mile/last-mile" problem, connecting residential areas to major transit hubs like train stations, is a critical challenge in urban transportation. Traditional fixed-route feeder services are inflexible, while existing demand-responsive transit (DRT) systems often fail to account for individual passenger needs, particularly their chosen subway schedules and the crucial coordination required for seamless transfers. This paper addresses the gap in DRT design by developing a system that considers personalized passenger travel orders, including specific subway departure times, and optimizes the feeder bus routes and schedules to minimize both passenger ride time to the station and their waiting time for the connecting train.

Methods

The authors propose a two-pronged approach:

  1. Mixed-Integer Programming (MIP) Model: They formulate a mathematical model to minimize the total travel time for all passengers. This objective function considers both the time spent on the feeder bus (ride-time) and the time passengers wait for their connecting subway (wait-time). The model incorporates constraints for vehicle capacity, route feasibility, and, crucially, the synchronous transfer between the feeder bus and the rail transit, ensuring passengers arrive at the station in time for their chosen subway.
  2. Distributed Genetic Algorithm (GA): Recognizing that DRT problems are NP-hard, they develop a distributed parallel genetic algorithm. This approach divides the complex problem into smaller sub-problems, which are then solved concurrently by multiple threads. This "divide and conquer" strategy aims to find near-optimal solutions efficiently, especially for large-scale instances, by leveraging parallel processing. The GA incorporates a modified fitness function that penalizes violations of key constraints, guiding the search towards feasible and optimal solutions.

Datasets

The study utilizes a real-world case in Nanjing City, China. The data includes:

  • Geographical distribution: Six bus depots, fifteen demand points, and one rail station.
  • Passenger demand: Number of passengers at each demand point, their preferred boarding time windows, and their chosen subway schedules.
  • Traffic network data: Travel distances and times between locations, obtained from an open GIS tool.

The paper does not introduce a new benchmark dataset but applies its methodology to a realistic scenario.

Key Insights and Ideas

  • Personalization is Key: Integrating individual passenger subway schedules into the feeder bus routing significantly impacts the overall travel time. Ignoring this personalization leads to suboptimal solutions.
  • Synchronous Transfer Matters: The coordinated timing between feeder bus arrival and subway departure is crucial for minimizing passenger wait times. This synchronization, while potentially increasing feeder bus ride times, drastically reduces overall travel time.
  • Distributed GA for Scalability: For complex, large-scale DRT problems, a distributed parallel GA is more effective than standard GA or exact solvers (like Cplex) in finding good solutions within a reasonable time frame. The "divide and conquer" approach allows for more efficient exploration of the solution space.
  • Trade-off Between Ride and Wait Time: The model highlights the inherent trade-off between feeder bus ride time and passenger wait time for rail transit. Optimizing for one can negatively impact the other, and the proposed model effectively balances these to minimize total passenger travel time.

Key Results

  • Total Travel Time Reduction: The proposed model achieved a 2.46% reduction in total passenger travel time compared to a traditional DRT model without synchronous rail transit coordination.
  • Ride vs. Wait Time Impact: While the total ride time for the proposed model increased by 9.36%, the total wait time was significantly reduced by 67.5%. This demonstrates the effectiveness of prioritizing wait-time reduction through synchronized scheduling.
  • Algorithm Performance: The distributed GA showed comparable or better results than Cplex and standard GA, with a significant speed advantage for larger problem instances. The paper notes that the GA's calculation time was 5.6, 28.6, and 326.2 times faster than Cplex for scenarios with three, four, and five vehicles, respectively.

Limitations and Future Work

  • Assumptions: The model relies on key hypotheses, including stable passenger demand (OD table) and that demand points are fixed bus stops. It does not account for dynamic changes in traffic conditions or the integrated assignment of passengers to optimal stops.
  • Real-world Complexity: The model may not fully address scenarios with one-way streets, left-turn-only intersections, or dynamic passenger demand.
  • Future Directions: The authors suggest extending the model to simultaneously select optimal stops and handle time-varying OD demand. Further research could also explore more sophisticated methods for dealing with dynamic traffic conditions and more complex urban network constraints.

Summary updated

Abstract

The purpose of this work is to create an efficient optimization framework for demand-responsive feeder transit services to assign vehicles to cover all pickup locations to transport passengers to a rail station. The proposed methodology features passengers placing a personalized travel order involving the subway schedule chosen by passengers and windows of service time, etc. Moreover, synchronous transfer between the shuttle and feeder bus is fully accounted for in the problem. A mixed-integer linear programming model is formulated to minimize the total travel time for all passengers, which consists of ride-time for vehicles from the pickup locations to the rail station and wait-time for passengers taking the subway beforehand. Different from conventional methods, the proposed model benefits from using a real distribution of passenger demand aggregated from cellular data and travel time or the distance matrix obtained from an open GIS tool. A distributed genetic algorithm is further designed to obtain meta-optimal solutions in a reasonable amount of time. When applied to design a feeder bus system in Nanjing City, China, case study results reveal that the total travel time of the proposed model was reduced by 2.46% compared to the traditional model. Sensitivity analyses were also further performed to investigate the impact of the number of vehicles on the output. Finally, the difference in results of Cplex, standard GA, and the proposed algorithm were compared to prove the validity of the algorithm.
BibTeX
@inproceedings{sun2018personalised,
  author = {Bo Sun and Ming Wei and Chunfeng Yang and Zhihuo Xu and Han Wang},
  title = {{Personalised and Coordinated Demand-Responsive Feeder Transit Service Design: A Genetic Algorithms Approach}},
  booktitle = {Future},
  year = {2018},
  doi = {10.3390/fi10070061},
}
Figure