Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing

Emerging transportation network services, such as customized buses, hold the promise of expanding overall traveler accessibility in congested metropolitan areas. A number of internet-based customized bus services have been planned and deployed for major origin-destination (OD) pairs to/from inner cities with limited physical road infrastructure. In this research, we aim to develop a joint optimization model for addressing a number of practical challenges for providing flexible public transportation services. First, how to maintain minimum loading rate requirements and increase the number of customers per bus for the bus operators to reach long-term profitability. Second, how to optimize detailed bus routing and timetabling plans to satisfy a wide range of specific user constraints, such as passengers’ pickup and delivery locations with preferred time windows, through flexible decision for matching passengers to bus routes. From a space-time network modeling perspective, this paper develops a multi-commodity network flow-based optimization model to formulate a customized bus service network design problem so as to optimize the utilization of the vehicle capacity while satisfying individual demand requests defined through space-time windows. We further develop a solution algorithm based on the Lagrangian decomposition for the primal problem and a space-time prism based method to reduce the solution search space. Case studies using both the illustrative and real-world large-scale transportation networks are conducted to demonstrate the effectiveness of the proposed algorithm and its sensitivity under different practical operating conditions.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

Hybrid predictive control for real-time optimization of public transport systems’ operations based on evolutionary multi-objective optimization

A hybrid predictive control formulation based on evolutionary multi-objective optimization to optimize real-time operations of public transport systems is presented. The state space model includes bus position, expected load and arrival time at stops. The system is based on discrete events, and the possible operator control actions are: holding vehicles at stations and skipping some stations. The controller (operator) pursues the minimization of a dynamic objective function to generate better operational decisions under uncertain demand at bus stops. In this work, a multi-objective approach is conducted to include different goals in the optimization process that could be opposite. In this case, the optimization was defined in terms of two objectives: waiting time minimization on one side, and impact of the strategies on the other. A genetic algorithm method is proposed to solve the multi-objective dynamic problem. From the conducted experiments considering a single bus line corridor, we found that the two objectives are opposite but with a certain degree of overlapping, in the sense that in all cases both objectives significantly improve the level of service with respect to the open-loop scenario by regularizing the headways. On average, the observed trade-off validates the proposed multi-objective methodology for the studied system, allowing dynamically finding the pseudo-optimal Pareto front and making real-time decisions based on different optimization criteria reflected in the proposed objective function compounds.     

Optimally combined headway and timetable reliable public transport system

This paper presents a model-based multiobjective control strategy to reduce bus bunching and hence improve public transport reliability. Our goal is twofold. First, we define a proper model, consisting of multiple static and dynamic components. Bus-following model captures the longitudinal dynamics taking into account the interaction with the surrounding traffic. Furthermore, bus stop operations are modeled to estimate dwell time. Second, a shrinking horizon model predictive controller (MPC) is proposed for solving bus bunching problems. The model is able to predict short time-space behavior of public transport buses enabling constrained, finite horizon, optimal control solution to ensure homogeneity of service both in time and space. In this line, the goal with the selected rolling horizon control scheme is to choose a proper velocity profile for the public transport bus such that it keeps both timetable schedule and a desired headway from the bus in front of it (leading bus). The control strategy predicts the arrival time at a bus stop using a passenger arrival and dwell time model. In this vein, the receding horizon model predictive controller calculates an optimal velocity profile based on its current position and desired arrival time. Four different weighting strategies are proposed to test (i) timetable only, (ii) headway only, (iii) balanced timetable - headway tracking and (iv) adaptive control with varying weights. The controller is tested in a high fidelity traffic simulator with realistic scenarios. The behavior of the system is analyzed by considering extreme disturbances. Finally, the existence of a Pareto front between these two objectives is also demonstrated.     

A model of bus bunching under reliability-based passenger arrival patterns

If bus service departure times are not completely unknown to the passengers, non-uniform passenger arrival patterns can be expected. We propose that passengers decide their arrival time at stops based on a continuous logit model that considers the risk of missing services. Expected passenger waiting times are derived in a bus system that allows also for overtaking between bus services. We then propose an algorithm to derive the dwell time of subsequent buses serving a stop in order to illustrate when bus bunching might occur. We show that non-uniform arrival patterns can significantly influence the bus bunching process. With case studies we find that, even without exogenous delay, bunching can arise when the boarding rate is insufficient given the level of overall demand. Further, in case of exogenous delay, non-uniform arrivals can either worsen or improve the bunching conditions, depending on the level of delay. We conclude that therefore such effects should be considered when service control measures are discussed.     

Berth assignment planning for multi‐line bus stops

In this paper, we study an important problem that arises with the fast development of public transportation systems: when a large number of bus lines share the same bus stop, a long queue of buses often forms when they wait to get into the stop in rush hours. This causes a significant increase of bus delay and a notable drop of traffic capacity near the bus stop. Various measures had been proposed to relieve the congestions near bus stops. However, all of them require considerable financial budgets and construction time costs. In this paper, with the concept of berth assignment redesign, a simulation‐based heuristic algorithm is proposed to make full use of exiting bus berths. In this study, a trustable simulation platform is designed, and the major influencing factors for bus stop operations are considered. The concept of risk control is also introduced to better evaluate the performance of different berth arrangement plans and makes an appropriate trade‐off between the system's efficiency and stability. Finally, a heuristic algorithm is proposed to find a sub‐optimal berth assignment plan. Tests on a typical bus stop show that this algorithm is efficient and fast. The sub‐optimal berth assignment plan obtained by this algorithm could make remarkable improvements to an actual bus stop. Copyright © 2013 John Wiley & Sons, Ltd.     

快速公交系统站台停靠时间模型研究

快速公交系统停靠站台停车延误是影响快速公交运行车速的关键因素之一,因此构建快速公交系统站台停靠时间模型是提升快速公交服务水平的基础理论研究。本文选取盐城BRT-1号线的起始站、中途站、客流离散站等三类站点为研究对象,综合运用数理统计法与数据挖掘法,构建快速公交系统站台停靠时间模型,并对该模型的合理性进行了检验。研究表明:盐城市BRT-1号线三类站台的快速公交车辆停靠时间与上下车乘客人数呈线性关系,即快速公交车辆停靠时间与上下车乘客人数的检验参数R2均大于0.8。     

Bus arrival time prediction at bus stop with multiple routes

Provision of accurate bus arrival information is vital to passengers for reducing their anxieties and waiting times at bus stop. This paper proposes models to predict bus arrival times at the same bus stop but with different routes. In the proposed models, bus running times of multiple routes are used for predicting the bus arrival time of each of these bus routes. Several methods, which include support vector machine (SVM), artificial neural network (ANN), k nearest neighbours algorithm (k-NN) and linear regression (LR), are adopted for the bus arrival time prediction. Observation surveys are conducted to collect bus running and arrival time data for validation of the proposed models. The results show that the proposed models are more accurate than the models based on the bus running times of single route. Moreover, it is found that the SVM model performs the best among the four proposed models for predicting the bus arrival times at bus stop with multiple routes.     

The time-dependent vehicle routing problem with soft time windows and stochastic travel times

This paper studies a vehicle routing problem with time-dependent and stochastic travel times. In our problem setting, customers have soft time windows. A mathematical model is used in which both efficiency for service as well as reliability for customers are taken into account. Depending on whether service times are included or not, we consider two versions of this problem. Two metaheuristics are built: a Tabu Search and an Adaptive Large Neighborhood Search. We carry out our experiments for well-known problem instances and perform comprehensive analyses on the numerical results in terms of the computational time and the solution quality. Experiments confirm that the proposed procedure is effective to obtain very good solutions to be performed in real-life environment.     

Bus routing strategies in a transit market: A case study of Hong Kong

Conventionally, the objective of transit routing is often set either to minimize the total operational cost, subject to a given level of service quality, or to maximize the service quality at a given acceptable cost. In a deregulated, commercial‐based environment however, such as bus and railway operations in cities of the UK and Hong Kong where several private firms compete in route‐based or area‐based market, routing becomes one of the means for higher returns rather than just for cost saving. In such a case, how do the transit providers set up their routes for profit‐maximization? Will the routing based on the provider's objective meet the user's objective? How do government regulations and policies affect the choice of transit provider's routing strategy? To answer these questions, we first examine the relationship between the objectives of users and transit providers, set up criteria for transit routing quality, and then investigate the possible routing configurations/patterns for a hypothetical case. These criteria include (1) the load factor of transit, (2) the level of route directness, (3) the level of route overlapping, and (4) the total number of routes and (5) the average of route length. These measures are finally applied to a real case in Hong Kong to examine the route changes of Kowloon Motor Bus from 1975 to 1995. The result of the empirical case reveais how key measures such as load factor are controlled by the bus operator and affected by government policies and how the bus routing pattern was adjusted to meet users' need. Facing the dilemma as evident in Hong Kong between the route directness and the efficiency of road use, we suggest that a rational multi‐modal routing structure be put in place if an institutional solution is introduced so that bus and other transit modes can form a sharing program or an alliance.     

Multi-objective re-synchronizing of bus timetable: Model,complexity and solution

This work is originally motived by the re-planning of a bus network timetable. The existing timetable with even headways for the network is generated using line by line timetabling approach without considering the interactions between lines. Decision-makers (i.e., schedulers) intend to synchronize vehicle timetable of lines at transfer nodes to facilitate passenger transfers while being concerned with the impacts of re-designed timetable on the regularity of existing timetable and the accustomed trip plans of passengers. Regarding this situation, we investigate a multi-objective re-synchronizing of bus timetable (MSBT) problem, which is characterized by headway-sensitive passenger demand, uneven headways, service regularity, flexible synchronization and involvement of existing bus timetable. A multi-objective optimization model for the MSBT is proposed to make a trade-off between the total number of passengers benefited by smooth transfers and the maximal deviation from the departure times of the existing timetable. By clarifying the mathematical properties and solution space of the model, we prove that the MSBT problem is NP-hard, and its Pareto-optimal front is non-convex. Therefore, we design a non-dominated sorting genetic (NSGA-II) based algorithm to solve this problem. Numerical experiments show that the designed algorithm, compared with enumeration method, can generate high-quality Pareto solutions within reasonable times. We also find that the timetable allowing larger flexibility of headways can obtain more and better Pareto-optimal solutions, which can provide decision-makers more choice.     

Optimal design of a short‐turning strategy considering seat availability

We develop a methodology to optimize the schedule coordination of a full‐stop service pattern and a short‐turning service pattern on a bus route. To capture the influence of bus crowding and seat availability on passengers' riding experience, we develop a Markov model to describe the seat‐searching process of a passenger and an approach to estimate the transition probabilities of the Markov model. An optimization model that incorporates the Markov model is proposed to design the short‐turning strategy. The proposed model minimizes the total cost, which includes operational cost, passengers' waiting time cost and passengers' in‐vehicle travel time cost. Algorithm is developed to produce optimal values of the decision variables. The proposed methodology is evaluated in a case study. Compared with methodologies that ignore the effect of bus crowding, the proposed methodology could better balance bus load along the route and between two service patterns, provide passengers with better riding experience and reduce the total cost. In addition, it is shown that the optimal design of the short‐turning strategy is sensitive to seat capacity. Copyright © 2016 John Wiley & Sons, Ltd.     

Investigating the impact of stochastic vehicle arrivals to optimal stop spacing and headway for a feeder bus route

Stop spacing and service frequency (i.e., the inverse of headway) are key elements in transit service planning. The trade‐offs between increasing accessibility and reducing travel time, which affect transit system performance, need to be carefully evaluated. The objective of this study is to optimize stop spacing and headway for a feeder bus route, considering the relationship between the variance of inter‐arrival time (VIAT), which yields the minimum total cost (including user and operator costs). A solution algorithm, called successive substitution, is adapted to efficiently search for the optimal solutions. In a numerical example, the developed model is applied to planning a feeder bus route in Newark, New Jersey. The results indicate that the optimal stop spacing should be longer that those suggested by previous studies where the impact of VIAT was ignored. Reducing VIAT via certain operational control strategies (i.e., holding/stop‐skipping, transit signal priority) may shorten stop spacing and improve accessibility. Copyright © 2014 John Wiley & Sons, Ltd.     

Modeling the interaction between buses,passengers and cars on a bus route using a multi-agent system

This paper models part of a public transport network (PTN), specifically, a bus route, as a small-size multi-agent system (MAS). The proposed approach is applied to a case study considering a ‘real world’ bus line within the PTN in Auckland, New Zealand. The MAS-based analysis uses modeling and simulation to examine the characteristics of the observed system – autonomous agents interacting with one another – under different scenarios, considering bus capacity and frequency of service for existing and projected public transport (PT) demand. A simulation model of a bus route is developed, calibrated and validated. Several results are attained, such as when the PT passenger load is not close to bus capacity, this load has no effect on average passenger waiting time at bus stops. The model proposed can be useful to practitioners as a tool to model the interaction between buses and other agents.     

A competitive, charter air-service planning model for student athlete travel

This paper presents a model for planning an air charter service for pre-scheduled group travel. This model is used to investigate the competitiveness of such an enterprise for student athlete travel in conference sports. The relevant demand subset to be served by a limited charter fleet is identified through a comparison with existing scheduled travel options. Further, the routing and scheduling of the charter aircraft is performed within the same framework. Through this modeling a method for formulating and accommodating continuous time windows and competitive market dynamics in strategic planning for a charter service is developed. Computational improvements to the basic model are also presented and tested. The model is applied to the Big Sky Conference for the 2006-2007 season, quantifying the benefits to the students from such a service and the change in expenditure associated with such a benefit for various assumptions about operations and value of time. The findings indicate the lack of spatial or sport based patterns for maximizing benefit, indicating the absence of simplistic “rules of thumb” for operating such a service, and validating the need for the model.     

Optimal feeder bus routes on irregular street networks

The methodology presented here seeks to optimize bus routes feeding a major intermodal transit transfer station while considering intersection delays and realistic street networks. A model is developed for finding the optimal bus route location and its operating headway in a heterogeneous service area. The criterion for optimality is the minimum total cost, including supplier and user costs. Irregular and discrete demand distributions, which realistically represent geographic variations in demand, are considered in the proposed model. The optimal headway is derived analytically for an irregularly shaped service area without demand elasticity, with non‐uniformly distributed demand density, and with a many‐to‐one travel pattern. Computer programs are designed to analyze numerical examples, which show that the combinatory type routing problem can be globally optimized. The improved computational efficiency of the near‐optimal algorithm is demonstrated through numerical comparisons to an optimal solution obtained by the exhaustive search (ES) algorithm. The CPU time spent by each algorithm is also compared to demonstrate that the near‐optimal algorithm converges to an acceptable solution significantly faster than the ES algorithm.     

Multi-fleet ferry service network design with passenger preferences for differential services

This paper investigates a multi-fleet ferry routing and scheduling problem that takes into account ferry services with different operation characteristics and passengers with different preferred arrival time windows. The logit model is used to represent passengers’ service choices. The full problem is formulated as a mixed integer nonlinear programming problem and solved with a heuristic procedure that first fixes the demand and then decomposes the resultant model by ferry services. At each iteration of the algorithm, the demand is updated and the relaxed problem is re-solved. Numerical results for the case of ferry service network design in Hong Kong are provided to illustrate the properties of the model and the performance of the heuristic.     

Evaluation of exclusive bus lanes in a bi-modal degradable road network

In this paper, we proposed an evaluation method of exclusive bus lanes (EBLs) in a bi-modal degradable road network with car and bus transit modes. Link travel time with and without EBLs for two modes is analyzed with link stochastic degradation. Furthermore, route general travel costs are formulated with the uncertainty of link travel time for both modes and the uncertainty of waiting time at a bus stop and in-vehicle congestion costs for the bus mode. The uncertainty of bus waiting time is considered to be relevant to the degradation of the front links of the bus line. A bi-modal user equilibrium model incorporating travelers’ risk adverse behavior is proposed for evaluating EBLs. Finally, two numerical examples are used to illustrate how the road degradation level, travelers’ risk aversion level and the front link’s correlation level with the uncertainty of the bus waiting time affect the results of the user equilibrium model with and without EBLs and how the road degradation level affects the optimal EBLs setting scheme. A paradox of EBLs setting is also illustrated where adding one exclusive bus lane may decrease share of bus.     

Optimization of airport bus timetable in cultivation period considering passenger dynamic airport choice under conditions of uncertainty

An airport bus service, which is newly introduced in a multi-airport region, commonly leads to a gradually increasing market share of airports until a new state of equilibrium is reached. With the goal of speeding up and enlarging the increase in market share, this paper proposes a timetable optimization model by incorporating reactions of airport-loyal passengers to bus service quality. The simulation part of the model, which uses cumulative prospect theory to formulate discrete airport choices, results in predicted passenger demand needed in the optimization part. Then a genetic algorithm for multi-objective optimization problems called NSGA-II is applied to solve the model. To illustrate the model, the “Lukou airport-Wuxi” airport bus in China is taken as an example. The results show that the optimized timetables shorten the cultivation period and impel the market share to grow rapidly.     

A bi-level programming for bus lane network design

This paper proposes a bi-level programming model to solve the design problem for bus lane distribution in multi-modal transport networks. The upper level model aims at minimizing the average travel time of travelers, as well as minimizing the difference of passengers’ comfort among all the bus lines by optimizing bus frequencies. The lower level model is a multi-modal transport network equilibrium model for the joint modal split/traffic assignment problem. The column generation algorithm, the branch-and-bound algorithm and the method of successive averages are comprehensively applied in this paper for the solution of the bi-level model. A simple numerical test and an empirical test based on Dalian economic zone are employed to validate the proposed model. The results show that the bi-level model performs well with regard to the objective of reducing travel time costs for all travelers and balancing transit service level among all bus lines.