Solution methods for the taxi pooling problem

In Taiwan, taxi pooling is currently performed by some taxi companies using a trial-and-error experience-based method, which is neither effective nor efficient. There is, however, little in the literature on effective models and solution methods for solving the taxi pooling problem. Thus, in this study we employ network flow techniques and a mathematical programming method to develop a taxi pooling solution method. This method is composed of three models. First, a fleet routing/scheduling model is constructed to produce fleet/passenger routes and schedules. A solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the fleet routing/scheduling model. Then, two single taxi-passenger matching models are constructed with the goals of decreasing number of passenger transfers and matching all passengers and taxis. These two taxi-passenger matching models are directly solved using a mathematical programming solver. For comparison with the solution method, we also develop another heuristic by modifying a heuristic recently proposed for solving a one-to-many taxi pooling problem. The performance of the solution method and the additional heuristic are evaluated by carrying out a case study using real data and suitable assumptions. The test results show that these two solution methods could be useful in practice.     

Rail line length in a crosstown corridor with many-to-many demand

An analytical model that determines the optimal location and length of rail line along a crosstown transportation corridor with the objective of minimizing the total transportation cost is presented. A general, many-to-many passenger demand pattern is considered. The objective function, which includes the rail and bus riding costs, rail and bus operating costs, rail fleet costs and rail line costs, is minimized by using the classical optimization method with the aid of a computer program developed for the model. The model is applied to the Northwest-South transportation corridor in Calgary, Alberta, and the sensitivity of the optimal rail line location and length to the unit cost and demand parameters at their reasonable ranges is tested. It is found that although the total passenger demand, unit rail line cost, and unit bus operating cost have greater influence than the unit bus and rail riding costs, and unit rail fleet and operating costs, the optimal line length is generally insensitive to all these parameters. It is also found that the length of the existing LRT line in the corridor is comparable to the optimal line length obtained from the model, but the existing line should be extended further south in order to meet the heavier demand in that direction optimally.     

Integrating bus services with mixed fleets

Conventional bus service (with fixed routes and schedules) has lower average cost than flexible bus service (with demand-responsive routes) at high demand densities. At low demand densities flexible bus service has lower average costs and provides convenient door-to-door service. Bus size and operation type are related since larger buses have lower average cost per passenger at higher demand densities. The operation type and other decisions are jointly optimized here for a bus transit system connecting a major terminal to local regions. Conventional and flexible bus sizes, conventional bus route spacings, areas of service zones for flexible buses, headways, and fleet sizes are jointly optimized in multi-dimensional nonlinear mixed integer optimization problems. To solve them, we propose a hybrid approach, which combines analytic optimization with a Genetic Algorithm. Numerical analysis confirms that the proposed method provides near-optimal solutions and shows how the proposed Mixed Fleet Variable Type Bus Operation (MFV) can reduce total cost compared to alternative operations such as Single Fleet Conventional Bus (SFC), Single Fleet Flexible Bus (SFF), Mixed Fleet Conventional Bus (MFC) and Mixed Fleet Flexible Bus (MFF). With consistent system-wide bus sizes, capital costs are reduced by sharing fleets over times and over regions. The sensitivity of results to several important parameters is also explored.     

Vehicle scheduling under stochastic trip times: An approximate dynamic programming approach

Due to unexpected demand surge and supply disruptions, road traffic conditions could exhibit substantial uncertainty, which often makes bus travelers encounter start delays of service trips and substantially degrades the performance of an urban transit system. Meanwhile, rapid advances of information and communication technologies have presented tremendous opportunities for intelligently scheduling a bus fleet. With the full consideration of delay propagation effects, this paper is devoted to formulating the stochastic dynamic vehicle scheduling problem, which dynamically schedules an urban bus fleet to tackle the trip time stochasticity, reduce the delay and minimize the total costs of a transit system. To address the challenge of “curse of dimensionality”, we adopt an approximate dynamic programming approach (ADP) where the value function is approximated through a three-layer feed-forward neural network so that we are capable of stepping forward to make decisions and solving the Bellman’s equation through sequentially solving multiple mixed integer linear programs. Numerical examples based on the realistic operations dataset of bus lines in Beijing have demonstrated that the proposed neural-network-based ADP approach not only exhibits a good learning behavior but also significantly outperforms both myopic and static polices, especially when trip time stochasticity is high.     

Designing large-scale bus network with seasonal variations of demand

Creating a bus network that covers passenger demand conveniently is an important ingredient of the transit operations planning process. Certainly determination of optimal bus network is highly sensitive to any change of demand, thus it is desirable not to consider average or estimated figures, but to take into account prudently the variations of the demand. Many cities worldwide experience seasonal demand variations which naturally have impact on the convenience and optimality of the transit service. That is, the bus network should provide convenient service across all seasons. This issue, addressed in this work, has not been thoroughly dealt with neither in practice nor in the literature. Analyzing seasonal transit demand variations increases further the computational complexity of the bus-network design problem which is known as a NP-hard problem. A solution procedure using genetic algorithm efficiently, with a defined objective-function to attain the optimization, is proposed to solve this cumbersome problem. The method developed is applied to two benchmarked networks and to a case study, to the city of Mashhad in Iran with over 3.2 million residents and 20 million visitors annually. The case study, characterized by a significant seasonal demand variation, demonstrates how to find the best single network of bus routes to suit the fluctuations of the annual passenger demand. The results of comparing the proposed algorithm to previously developed algorithms show that the new development outperforms the other methods between 1% and 9% in terms of the objective function values.     

A simulation model of the bus transitway (TRNSIM)

For planning and design of a bus rapid transit system and for the analysis of multimodal corridors, methodology is required for simulating bus traffic operation on a Transitway. Macroscopic models of vehicle flow are gaining popularity due to their capability to analyze complex operations and yet offer efficiency in development and applications. A macroscopic model is developed for the investigation of travel time, energy and emissions that correspond to bus volume levels on the Transitway. This paper describes the travel time part of the model. The model treats stochastic characteristics of bus traffic and passenger activities. Also, safety regimes in vehicle flow and factors affecting minimum headways in station areas are incorporated. The model is verified by comparing simulated travel time for the Ottawa-Carleton Transitway with actual data.     

Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations

This study addresses the problem of scheduling a fleet of taxis that are appointed to solely service customers with advance reservations. In contrast to previous studies that have dealt with the planning and operations of a taxi fleet with only electric vehicles (EVs), we consider that most taxi companies may have to operate with fleets comprised of both gasoline vehicles (GVs) and plug-in EVs during the transition from GV to (complete) EV taxi fleets. This paper presents an innovative multi-layer taxi-flow time-space network which effectively describes the movements of the taxis in the dimensions of space and time. An optimization model is then developed based on the time-space network to determine an optimal schedule for the taxi fleet. The objective is to minimize the total operating cost of the fleet, with a set of operating constraints for the EVs and GVs included in the model. Given that the model is formulated as an integer multi-commodity network flow problem, which is characterized as NP-hard, we propose two simple but effective decomposition-based heuristics to efficiently solve the problem with practical sizes. Test instances generated based on the data provided by a Taiwan taxi company are solved to evaluate the solution algorithms. The results show that the gaps between the objective values of the heuristic solutions and those of the optimal solutions are less than 3%, and the heuristics require much less time to obtain the good quality solutions. As a result, it is shown that the model, coupled with the algorithms, can be an effective planning tool to assist the company in routing and scheduling its fleet to service reservation customers.     

A connected-vehicle-based dynamic control model for managing the bus bunching problem with capacity constraints

This paper describes a connected-vehicle-based system architecture which can provide more precise and comprehensive information on bus movements and passenger status. Then a dynamic control method is proposed using connected vehicle data. Traditionally, the bus bunching problem has been formulated into one of two types of optimization problem. The first uses total passenger time cost as the objective function and capacity, safe headway, and other factors as constraints. Due to the large number of scenarios considered, this type of framework is inefficient for real-time implementation. The other type uses headway adherence as the objective and applies a feedback control framework to minimize headway variations. Due to the simplicity in the formulation and solution algorithms, the headway-based models are more suitable for real-time transit operations. However, the headway-based feedback control framework proposed in the literature still assumes homogeneous conditions at all bus stations, and does not consider restricting passenger loads within the capacity constraints. In this paper, a dynamic control framework is proposed to improve not only headway adherence but also maintain the stability of passenger load within bus capacity in both homogenous and heterogeneous situations at bus stations. The study provides the stability conditions for optimal control with heterogeneous bus conditions and derives optimal control strategies to minimize passenger transit cost while maintaining vehicle loading within capacity constraints. The proposed model is validated with a numerical analysis and case study based on field data collected in Chengdu, China. The results show that the proposed model performs well on high-demand bus routes.     

Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: An approximate dynamic programming approach

In a heavily congested metro line, unexpected disturbances often occur to cause the delay of the traveling passengers, infeasibility of the current timetable and reduction of the operational efficiency. Due to the uncertain and dynamic characteristics of passenger demands, the commonly used method to recover from disturbances in practice is to change the timetable and rolling stock manually based on the experiences and professional judgements. In this paper, we develop a stochastic programming model for metro train rescheduling problem in order to jointly reduce the time delay of affected passengers, their total traveling time and operational costs of trains. To capture the complexity of passenger traveling characteristics, the arriving ratio of passengers at each station is modeled as a non-homogeneous poisson distribution, in which the intensity function is treated as time-varying origin-to-destination passenger demand matrices. By considering the number of on-board passengers, the total energy usage is modeled as the difference between the tractive energy consumption and the regenerative energy. Then, we design an approximate dynamic programming based algorithm to solve the proposed model, which can obtain a high-quality solution in a short time. Finally, numerical examples with real-world data sets are implemented to verify the effectiveness and robustness of the proposed approaches.     

Simulation of fixed route bus travel time

Travel time on fixed route urban bus route is discussed. Given that the travel time is a function of three basic variables, Monte Carlo procedure is used to simulate trips during a specific time interval. Each variable is assumed to have a specific probability distribution with known or estimatable parameters. It is shown that this micro-computer simulation model can be used for examining the effects of traffic management schemes, number of stops and passenger demand on travel time, and subsequently fleet size and level of service.     

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.     

Switching service types for multi-region bus systems

Conventional fixed-route bus services are generally preferred to flexible-route services at high demand densities, and vice versa. This paper formulates the problem of integrating conventional and flexible services that connect a main terminal to multiple local regions over multiple time periods. The system’s vehicle size, route spacing (for conventional services), service area (for flexible services), headways and fleet sizes are jointly optimized to minimize the sum of supplier costs and user costs. The route spacing for conventional bus services and service area for flexible bus services are also optimized for each region. The proposed solution method, which uses a genetic algorithm and analytic optimization, finds good solutions quickly. Numerical examples and sensitivity analyses confirm that the single fleet variable-type bus service may outperform either the single fleet conventional bus service or the single fleet flexible bus service when demand densities vary substantially among regions and time periods.     

A stochastic fleet size and mix model for maintenance operations at offshore wind farms

A fleet of vessels and helicopters is needed to support maintenance operations at offshore wind farms. The cost of this fleet constitutes a major part of the total maintenance costs, hence keeping an optimal or near-optimal fleet is essential to reduce the cost of energy. In this paper we study the vessel fleet size and mix problem that arises for the maintenance operations at offshore wind farms, and propose a stochastic three-stage programming model. The stochastic model considers uncertainty in vessel spot rates, weather conditions, electricity prices and failures to the system. The model is tested on realistic-sized problem instances, and the results show that it is valuable to consider uncertainty and that the proposed model can be used to solve instances of a realistic size.     

Optimal bus service patterns and frequencies considering transfer demand elasticity with genetic algorithm

This paper attempts to optimize bus service patterns (i.e., all-stop, short-turn, and express) and frequencies which minimize total cost, considering transfer demand elasticity. A mathematical model is developed based on the objective total cost for a generalized bus route, which is optimized subject to a set of constraints ensuring sufficient capacity, an operable bus fleet, and service frequency conservation. To optimize the integrated service of a bus route with many stops, which is a combinatorial optimization problem, a genetic algorithm is developed and applied to search for the solution. A case study, based on a real-world bus route in New Jersey, is conducted to demonstrate the applicability and effectiveness of the developed model and the solution algorithm. Results show that the proposed methodology is fairly efficient, and the optimized bus service significantly reduces total cost.     

Crowding in public transport systems: Effects on users,operation and implications for the estimation of demand

The effects of high passenger density at bus stops, at rail stations, inside buses and trains are diverse. This paper examines the multiple dimensions of passenger crowding related to public transport demand, supply and operations, including effects on operating speed, waiting time, travel time reliability, passengers’ wellbeing, valuation of waiting and in-vehicle time savings, route and bus choice, and optimal levels of frequency, vehicle size and fare. Secondly, crowding externalities are estimated for rail and bus services in Sydney, in order to show the impact of crowding on the estimated value of in-vehicle time savings and demand prediction. Using Multinomial Logit (MNL) and Error Components (EC) models, we show that alternative assumptions concerning the threshold load factor that triggers a crowding externality effect do have an influence on the value of travel time (VTTS) for low occupancy levels (all passengers sitting); however, for high occupancy levels, alternative crowding models estimate similar VTTS. Importantly, if demand for a public transport service is estimated without explicit consideration of crowding as a source of disutility for passengers, demand will be overestimated if the service is designed to have a number of standees beyond a threshold, as analytically shown using a MNL choice model. More research is needed to explore if these findings hold with more complex choice models and in other contexts.     

Numerical analysis of electric bus fast charging strategies for demand charge reduction

Electric transit buses have been recognized as an important alternative to diesel buses with many environmental benefits. Electric buses employing lithium titanate batteries can provide uninterrupted transit service thanks to their ability of fast charging. However, fast charging may result in high demand charges which will increase the fuel costs thereby limiting the electric bus market penetration. In this paper, we simulated daily charging patterns and demand charges of a fleet of electric buses in Tallahassee, Florida and identified an optimal charging strategy to minimize demand charges. It was found that by using a charging threshold of 60–64%, a $160,848 total saving in electricity cost can be achieved for a five electric bus fleet, comparing to a charging threshold of 0–28%. In addition, the impact of fleet sizes on the fuel cost was investigated. Fleets of 4 and 12 buses will achieve the lowest cost per mile driven when one fast charger is installed.     

The planning of aircraft routes and flight frequencies in an airline network operations

This research is aimed at developing a model that maximizes system profit when determining the aircraft routes and flight frequencies in a network. The model employs network flow techniques to effectively collect or deliver passenger flows from all origins to all destinations using non‐stop and multi‐stop flights in multi‐fleet operations. The model was formulated as a multi‐commodity network flow problem. A Lagrangian‐based algorithm was developed to solve the problem. To test the model in practice, a case study is presented.     

Bus arrival time calculation model based on smart card data

Bus arrival time is usually estimated using the boarding time of the first passenger at each station. However, boarding time data are not recorded in certain double-ticket smart card systems. As many passengers usually swipe the card much before their alighting, the first or the average alighting time cannot represent the actual bus arrival time, either. This lack of data creates difficulties in correcting bus arrival times. This paper focused on developing a model to calculate bus arrival time that combined the alighting swiping time from smart card data with the actual bus arrival time by the manual survey data. The model was built on the basis of the frequency distribution and the regression analysis. The swiping time distribution, the occupancy and the seating capacity were considered as the key factors in creating a method to calculate bus arrival times. With 1011 groups of smart card data and 360 corresponding records from a manual survey of bus arrival times, the research data were divided into two parts stochastically, a training set and a test set. The training set was used for the parameter determination, and the test set was used to verify the model’s precision. Furthermore, the regularity of the time differences between the bus arrival times and the card swiping times was analyzed using the “trend line” of the last swiping time distribution. Results from the test set achieved mean and standard error rate deviations of 0.6% and 3.8%, respectively. The proposed model established in this study can improve bus arrival time calculations and potentially support state prediction and service level evaluations for bus operations.     

A self-adaptive method to equalize headways: Numerical analysis and comparison

In uncontrolled bus systems, buses tend to bunch due to the stochastic nature of traffic flows and passenger demand at bus stops. Although schedules and priori target methods introduce slack time to delay buses at control points to maintain constant headways between successive buses, too much slack required delay passengers on-board. In addition, these methods focus on regular headways and do not consider the rates of convergence of headways after disturbances. We propose a self-adaptive control scheme to equalize the headways of buses with little slack in a single line automatically. The proposed method only requires the information from the current bus at the control point and both its leading and following buses. This elegant method is shown to regulate headways faster than existing methods. In addition, compared to previous self-equalizing methods, the proposed method can improve the travel time of buses by about 12%, while keeping the waiting time of passengers almost the same.     

A system dynamics model of CO2 mitigation in China’s inter-city passenger transport

Mitigation of greenhouse gas emissions from transportation has become increasingly important and challenging especially for developing countries. This paper takes the inter-city passenger transport in China as a case, and develops a system dynamics model for policy assessment and CO₂ mitigation potential analysis. It is found that the future demand for China’s inter-city passenger transport is expected to be large, with the turnover volume growing at a rate of 9% per annum and amounting to 6600 billion p-km in 2020. Major emissions reduction potential exists in inter-city passenger transport. In 2020, comparing to the case without any specific policies stressing mitigation, the reduction of CO₂ emissions ranges from 26% to 32% under those scenarios with policy controls. Sensitivity analysis reveals that the CO₂ mitigation will be best achieved by accelerating the development of railway network, together with slowing down the extension of highway network and imposing fuel taxes.