Optimal Design of Demand-Responsive Feeder Transit Services with Passengers’ Multiple Time Windows and Satisfaction

Bo Sun, Ming Wei, Senlai ZhuFuture 2018 · DOI

TL;DR

This paper tackles the challenge of optimizing demand-responsive feeder transit services by developing a mixed-integer programming model that accounts for passengers' multiple time window preferences and their satisfaction with ride time. They propose an improved Bat Algorithm to efficiently find near-optimal solutions, demonstrating significant improvements in mileage reduction and passenger satisfaction compared to traditional methods.

What Problem Does This Paper Address?

Public transportation systems often struggle with the "first/last mile" problem – connecting people from their homes to major transit hubs like train stations. Traditional fixed-route transit is inflexible, while demand-responsive transit (DRT) offers more flexibility but faces its own complexities. This paper focuses on optimizing DRT by addressing two key limitations in existing models:

  1. Multiple Time Windows: Passengers often have flexible schedules and may be available to board within several distinct time periods, not just a single one. Existing DRT models typically only consider a single time window per passenger.
  2. Passenger Satisfaction: While DRT aims for convenience, passenger satisfaction is heavily influenced by factors like ride time. Current models often neglect to explicitly integrate passenger satisfaction, particularly how it relates to expected ride time, into the optimization process.

The authors aim to create a more realistic and passenger-centric DRT system that balances operational costs (like mileage) with service quality (passenger satisfaction).

Methods

The core of the paper is a mixed-integer linear programming (MIP) model designed to optimize DRT services. This model incorporates:

  • Demand Points and Rail Stations: Defining the locations that need to be served.
  • Dispatch Centers: The starting points for vehicles.
  • Multiple Time Windows: Allowing passengers to specify one or more preferred boarding times.
  • Expected Ride Time: Passengers provide a range for their acceptable ride duration.
  • Passenger Satisfaction Function: A novel function is introduced to quantify passenger satisfaction based on their actual ride time relative to their expected ride time. A shorter ride time within the acceptable window leads to higher satisfaction.
  • Dual Objective: The model simultaneously aims to minimize total operational mileage costs and maximize total passenger satisfaction.

Since DRT problems are NP-hard, an exact solution using traditional solvers can be computationally expensive for large-scale problems. To address this, the authors developed an Improved Bat Algorithm (BA). This hybrid algorithm combines the principles of the Bat Algorithm (simulating echolocation) with elements of the Group Search Optimizer (GSO) to enhance its ability to explore the solution space and avoid premature convergence. Key aspects of their algorithm include:

  • Novel Coding Scheme: Representing potential solutions (routes and assignments) in a way that's suitable for the DRT problem.
  • Heuristic Initial Population Generation: A method to create a diverse and feasible starting set of solutions, as random generation can be difficult for complex DRT constraints.
  • Updated Speed and Location Rules: Incorporating ideas from GSO to maintain diversity and explore the solution space more effectively.
  • Fitness Evaluation: Incorporating penalty terms for constraint violations into the fitness function.

Datasets

The paper uses a case study in Nanjing City, China, to demonstrate the model's applicability. This case study involves:

  • One rail station.
  • Six dispatch centers.
  • Fifteen demand points.

The data for demand points includes the number of passengers, their preferred time windows, and their expected ride times. The distances and travel times between locations were obtained using Baidu GIS. No new benchmark datasets were introduced; rather, a real-world scenario was used for evaluation.

Key Insights and Ideas

  • The Value of Multiple Time Windows: Allowing passengers to specify multiple boarding time windows significantly improves the efficiency and passenger satisfaction of DRT services. This flexibility reduces "invalid travel mileage and time" by enabling vehicles to pick up passengers more opportunistically.
  • Integrating Passenger Satisfaction: Explicitly modeling passenger satisfaction, particularly its link to ride time, leads to a more passenger-centric and potentially more adopted transit system. This moves beyond purely cost-driven optimization.
  • Hybrid Heuristics for Complex Problems: The Improved Bat Algorithm demonstrates that combining established swarm intelligence algorithms (like BA and GSO) can yield superior performance for complex optimization problems like DRT, offering a good balance between solution quality and computational time.
  • Trade-offs in Optimization: The study highlights the inherent trade-off between minimizing total mileage and maximizing passenger satisfaction. Increasing the number of vehicles can improve satisfaction but also increases mileage, suggesting a need for careful balancing based on operational costs and desired service levels.

Key Results

The proposed model and algorithm achieved notable improvements in the Nanjing case study:

  • Mileage Reduction: The proposed model reduced total mileage by 1.4 km compared to a traditional DRT model.
  • Satisfaction Increase: Total passenger satisfaction increased by 7.1%.
  • Overall Objective: The combined objective function (balancing cost and satisfaction) showed significant improvement. For instance, with 3 vehicles, the objective value was -36.4 yuan, with a total satisfaction of 96.4 and total mileage of 9.2 km.
  • Algorithm Comparison: The Improved BA performed comparably to Cplex for smaller problem scales and showed better quality and robustness than standard BA and GSO for larger scales, with computation times within an acceptable range.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Pedestrian Guidance: The current model assumes passengers are at designated boarding points (like bus stops). It does not account for the "pedestrian guidance" aspect, i.e., the walking distance from a passenger's home to a candidate bus stop.
  • Integrated Operation: Future work should consider integrating the selection of bus stops and the assignment of pedestrians to these stops with the feeder bus network design.
  • Stochasticity: The current model assumes deterministic travel times and passenger demand. Incorporating stochastic elements would make it more robust.
  • Broader Satisfaction Factors: While ride time satisfaction is modeled, other factors influencing passenger satisfaction (e.g., comfort, fare, reliability) could be explored.

Summary updated

Abstract

This paper presents a mixed-integer linear programming model for demand-responsive feeder transit services to assign vehicles located at different depots to pick up passengers at the demand points and transport them to the rail station. The proposed model features passengers’ one or several preferred time windows for boarding vehicles at the demand point and their expected ride time. Moreover, passenger satisfaction that was related only to expected ride time is fully accounted for in the model. The objective is to simultaneously minimize the operation costs of total mileage and maximize passenger satisfaction. As the problem is an extension of the nondeterministic polynomial problem with integration of the vehicle route problem, this study further develops an improved bat algorithm to yield meta-optimal solutions for the model in a reasonable amount of time. When this was applied to a case study in Nanjing City, China, the mileage and satisfaction of the proposed model were reduced by 1.4 km and increased by 7.1%, respectively, compared with the traditional model. Sensitivity analyses were also performed to investigate the impact of the number of designed bus routes and weights of objective functions on the model performance. Finally, a comparison of Cplex, standard bat algorithm, and group search optimizer is analyzed to verify the validity of the proposed algorithm.
BibTeX
@inproceedings{sun2018optimal,
  author = {Bo Sun and Ming Wei and Senlai Zhu},
  title = {{Optimal Design of Demand-Responsive Feeder Transit Services with Passengers’ Multiple Time Windows and Satisfaction}},
  booktitle = {Future},
  year = {2018},
  doi = {10.3390/fi10030030},
}
Figure