Disruption management in public transit: the bee colony optimization approach

Disruptions in carrying out planned bus schedules occur daily in many public transit companies. Disturbances are often so large that it is necessary to perform re-planning of planned bus and crew activities. Dispatchers in charge of traffic operations must frequently find an answer to the following question in a very short period of time: How should available buses be distributed among bus routes in order to minimize total passengers' waiting time on the network? We propose a model for assigning buses to scheduled routes when there is a shortage of buses. The proposed model is based on the bee colony optimization (BCO) technique. It is a biologically inspired method that explores collective intelligence applied by honey bees during the nectar collecting process. It has been shown that this developed BCO approach can generate high-quality solutions within negligible processing times.     

Ant Colony Routing algorithm for freeway networks

Dynamic traffic routing refers to the process of (re)directing vehicles at junctions in a traffic network according to the evolving traffic conditions. The traffic management center can determine desired routes for drivers in order to optimize the performance of the traffic network by dynamic traffic routing. However, a traffic network may have thousands of links and nodes, resulting in a large-scale and computationally complex non-linear, non-convex optimization problem. To solve this problem, Ant Colony Optimization (ACO) is chosen as the optimization method in this paper because of its powerful optimization heuristic for combinatorial optimization problems. ACO is implemented online to determine the control signal – i.e., the splitting rates at each node. However, using standard ACO for traffic routing is characterized by four main disadvantages: 1. traffic flows for different origins and destinations cannot be distinguished; 2. all ants may converge to one route, causing congestion; 3. constraints cannot be taken into account; and 4. neither can dynamic link costs. These problems are addressed by adopting a novel ACO algorithm with stench pheromone and with colored ants, called Ant Colony Routing (ACR). Using the stench pheromone, the ACR algorithm can distribute the vehicles over the traffic network with less or no traffic congestion, as well as reduce the number of vehicles near some sensitive zones, such as hospitals and schools. With colored ants, the traffic flows for multiple origins and destinations can be represented. The proposed approach is also implemented in a simulation-based case study in the Walcheren area, the Netherlands, illustrating the effectiveness of the approach.     

Mitigation of disruptions in public transit by Bee Colony Optimization

Dispatchers in many public transit companies face the daily problem of assigning available buses to bus routes under conditions of bus shortages. In addition to this, weather conditions, crew absenteeism, traffic accidents, traffic congestion and other factors lead to disturbances of the planned schedule. We propose the Bee Colony Optimization (BCO) algorithm for mitigation of bus schedule disturbances. The developed model takes care of interests of the transit operator and passengers. The model reassigns available buses to bus routes and, if it is allowed, the model simultaneously changes the transportation network topology (it shortens some of the planned bus routes) and reassigns available buses to a new set of bus routes. The model is tested on the network of Rivera (Uruguay). Results obtained show that the proposed algorithm can significantly mitigate disruptions.     

Passenger travel characteristics and bus operational states: a study based on IC card and GPS data in Yinchuan,China

ABSTRACT

In recent years, public transport has been developing rapidly and producing large amounts of traffic data. Emerging big data-mining techniques enable the application of these data in a variety of ways. This study uses bus intelligent card (IC card) data and global positioning system (GPS) data to estimate passenger boarding and alighting stations. First, an estimation model for boarding stations is introduced to determine passenger boarding stations. Then, the authors propose an innovative uplink and downlink information identification model (UDI) to generate information for estimating alighting stations. Subsequently, the estimation model for the alighting stations is introduced. In addition, a transfer station identification model is also developed to determine transfer stations. These models are applied to Yinchuan, China to analyze passenger flow characteristics and bus operations. The authors obtain passenger flows based on stations (stops), bus lines, and traffic analysis zones (TAZ) during weekdays and weekends. Moreover, average bus operational speeds are obtained. These findings can be used in bus network planning and optimization as well as bus operation scheduling.     

Joint deployment of charging stations and photovoltaic power plants for electric vehicles

The focus of this study is to jointly design charging stations and photovoltaic (PV) power plants with time-dependent charging fee, to improve the management of the coupled transportation and power systems. We first propose an efficient and extended label-setting algorithm to solve the EV joint routing and charging problem that considers recharging amount choices at different stations and loop movement cases. Then, a variational inequality problem is formulated to model the equilibrium of EV traffic on transportation networks, and an optimal power flow model is proposed to model the power network flow with PV power plants and optimally serve the EV charging requirements. Based on the above models for describing system states, we then formulate a model to simultaneously design charging stations, PV plants, and time-dependent charging fee. A surrogate-based optimization (SBO) algorithm is adopted to solve the model. Numerical examples demonstrate that the proposed SBO algorithm performs well. Additionally, important insights concerning the infrastructure design and price management of the coupled transportation and power networks are derived accordingly.     

The treatment of uncertainty in the dynamic origin–destination estimation problem using a fuzzy approach

Regardless of existing types of transportation and traffic model and their applications, the essential input to these models is travel demand, which is usually described using origin–destination (OD) matrices. Due to the high cost and time required for the direct development of such matrices, they are sometimes estimated indirectly from traffic measurements recorded from the transportation network. Based on an assumed demand profile, OD estimation problems can be categorized into static or dynamic groups. Dynamic OD demand provides valuable information on the within-day fluctuation of traffic, which can be employed to analyse congestion dissipation. In addition, OD estimates are essential inputs to dynamic traffic assignment (DTA) models. This study presents a fuzzy approach to dynamic OD estimation problems. The problems are approached using a two-level model in which demand is estimated in the upper level and the lower level performs DTA via traffic simulation. Using fuzzy rules and the fuzzy C-Mean clustering approach, the proposed method treats uncertainty in historical OD demand and observed link counts. The approach employs expert knowledge to model fitted link counts and to set boundaries for the optimization problem by defining functions in the fuzzification process. The same operation is performed on the simulation outputs, and the entire process enables different types of optimization algorithm to be employed. The Box-complex method is utilized as an optimization algorithm in the implementation of the approach. Empirical case studies are performed on two networks to evaluate the validity and accuracy of the approach. The study results for a synthetic network and a real network demonstrate the robust performance of the proposed method even when using low-quality historical demand data.     

Computing 4D near-optimal trajectories for dynamic air traffic flow management with column generation and branch-and-price

Abstract

The current air traffic system faces recurrent saturation problems. Numerous studies are dedicated to this issue, including the present research on a new dynamic regulation filter holding frequent trajectory optimisations in a real-time sliding horizon loop process. We consider a trajectory optimisation problem arising in this context, where a feasible four-dimensional (4D) trajectory is to be built and assigned to each regulated flight to suppress sector overloads while minimising the cost of the chosen policy. We model this problem with a mixed integer linear programme and solve it with a branch-and-price approach. The pricing sub-problem looks for feasible trajectories in a dynamic three-dimensional (3D) network and is solved with a specific algorithm based on shortest path labelling algorithms and on dynamic programming. Each algorithm is tested on real-world data corresponding to a complete traffic day in the European air traffic system; experimental results, including computing times measurement, validate the solution process.     

A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

An optimization model for integrated planning of railway traffic and network maintenance

Railway transportation systems are important for society and have many challenging and important planning problems. Train services as well as maintenance of a railway network need to be scheduled efficiently, but have mostly been treated as two separate planning problems. Since these activities are mutually exclusive they must be coordinated and should ideally be planned together. In this paper we present a mixed integer programming model for solving an integrated railway traffic and network maintenance problem. The aim is to find a long term tactical plan that optimally schedules train free windows sufficient for a given volume of regular maintenance together with the wanted train traffic. A spatial and temporal aggregation is used for controlling the available network capacity. The properties of the proposed model are analyzed and computational experiments on various synthetic problem instances are reported. Model extensions and possible modifications are discussed as well as future research directions.     

Area-wide urban traffic control: A Bee Colony Optimization approach

The paper describes a new method of optimizing traffic signal settings. The area-wide urban traffic control system developed in the paper is based on the Bee Colony Optimization (BCO) technique. The BCO method is based on the principles of the collective intelligence applied by the honeybees during the nectar collecting process. The optimal (or near-optimal) values of cycle length, offsets, and splits are discovered by minimizing the total travel time of all network users travelling through signalized intersections. The set of numerical experiments is performed on well-known traffic benchmark network. The results obtained by the BCO approach are compared with the results found by Simulated Annealing (SA). It has been shown that the suggested BCO approach outperformed the SA.     

Estimation of origin-destination matrices from link traffic counts on congested networks

Conventional methods for estimating origin-destination (O-D) trip matrices from link traffic counts assume that route choice proportions are given constants. In a network with realistic congestion levels, this assumption does not hold. This paper shows how existing methods such as the generalized least squares technique can be integrated with an equilibrium traffic assignment in the form of a convex bilevel optimization problem. The presence of measurement errors and time variations in the observed link flows are explicitly considered. The feasibility of the model is always guaranteed without a requirement for estimating consistent link flows from counts. A solution algorithm is provided and numerical simulation experiments are implemented in investigating the model's properties. Some related problems concerning O-D matrix estimation are also discussed.     

A quantum evolutionary algorithm for the second-best congestion pricing problem in urban traffic networks

This paper investigates the congestion pricing problem in urban traffic networks. A first-best strategy, a second-best strategy for toll leveling in closed cordons and a second-best strategy for determining both toll levels and toll points are considered. The problem is known to be a mixed integer programming model and formulated as a bi-level optimization problem, with an objective of maximizing the social welfare. A method is presented to solve the problem, based on a novel metaheuristic algorithm, namely quantum evolutionary algorithm (QEA). To verify the proposed method, the widely used genetic algorithm (GA) is also applied to solve the problem. The problem is solved for a medium-size urban traffic network and the results of the QEA are compared against the conventional GA. Computational results show that the QEA outperforms the GA in solution quality.     

A bilevel flow model for hazmat transportation network design

In this work we consider the following hazmat transportation network design problem. A given set of hazmat shipments has to be shipped over a road transportation network in order to transport a given amount of hazardous materials from specific origin points to specific destination points, and we assume there are regional and local government authorities that want to regulate the hazmat transportations by imposing restrictions on the amount of hazmat traffic over the network links. In particular, the regional authority aims to minimize the total transport risk induced over the entire region in which the transportation network is embedded, while local authorities want the risk over their local jurisdictions to be the lowest possible, forcing the regional authority to assure also risk equity. We provide a linear bilevel programming formulation for this hazmat transportation network design problem that takes into account both total risk minimization and risk equity. We transform the bilevel model into a single-level mixed integer linear program by replacing the second level (follower) problem by its KKT conditions and by linearizing the complementary constraints, and then we solve the MIP problem with a commercial optimization solver. The optimal solution may not be stable, and we provide an approach for testing its stability and for evaluating the range of its solution values when it is not stable. Moreover, since the bilevel model is difficult to be solved optimally and its optimal solution may not be stable, we provide a heuristic algorithm for the bilevel model able to always find a stable solution. The proposed bilevel model and heuristic algorithm are experimented on real scenarios of an Italian regional network.     

On the dual approach to the traffic assignment problem

This paper attempts to explore the possibility of solving the traffic assignment problem with elastic demands by way of its dual problem. It is shown that the dual problem can be formulated as a nonsmooth convex optimization problem of which the objective function values and subgradients are conveniently calculated by solving shortest path problems associated with the transportation network. A subgradient algorithm to solve the dual problem is presented and limited computational experience is reported. The computational results are encouraging enough to demonstrate the effectiveness of the proposed approach.     

Hybrid artificial neural network and locally weighted regression models for lane-based short-term urban traffic flow forecasting

ABSTRACT

In recent years, there has been considerable research interest in short-term traffic flow forecasting. However, forecasting models offering a high accuracy at a fine temporal resolution (e.g. 1 or 5?min) and lane level are still rare. In this study, a combination of genetic algorithm, neural network and locally weighted regression is used to achieve optimal prediction under various input and traffic settings. The genetically optimized artificial neural network (GA-ANN) and locally weighted regression (GA-LWR) models are developed and tested, with the former forecasting traffic flow every 5-min within a 30-min period and the latter for forecasting traffic flow of a particular 5-min period of each for four lanes of an urban arterial road in Beijing, China. In particular, for morning peak and off-peak traffic flow prediction, the GA-ANN 5-min traffic flow model results in average errors of 3–5% and most 95th percentile errors of 7–14% for each of the four lanes; for the peak and off-peak time traffic flow predictions, the GA-LWR 5-min traffic flow model results in average errors of 2–4% and most 95th percentile errors are lower than 10% for each of the four lanes. When compared to previous models that usually offer average errors greater than 6–15%, such empirical findings should be of interest to and instrumental for transportation authorities to incorporate in their city- or state-wide Advanced Traveller Information Systems (ATIS).     

Locating rental stations and bikeways in a public bike system

To determine the spatial distribution of rental stations and bikeways in a public bike system, this paper proposes a facility location and network design model. The model is developed as a multi-objective programing problem that considers four objectives (minimizing cyclist risk, maximizing cyclist comfort, minimizing adverse impacts on traffic and maximizing service coverage) and multiple constraints (monetary budget, network connectivity, station spacing, bikeway types, station number and value ranges of decision variables). The ε-constraint method solves the programing problem for the public bike system in Daan District, Taipei City, Taiwan. The nine non-dominated alternatives generated are all markedly better than existing locations of rental stations and bikeways. Scenario analysis results indicate that increasing the construction budget for bikeways significantly improves cyclist safety and comfort whilst increasing the adverse impact on traffic. Planners can use this model to develop public bike systems that spatially integrate rental stations and bikeway networks.     

Incorporating refuelling behaviour and drivers’ preferences in the design of alternative fuels infrastructure in a city

The purpose of this article is to present an optimization model to plan the deployment strategy for hydrogen refuelling stations in a city when Origin–Destination (OD) data are not available. This model considers two objectives: to maximize the traffic covered by the selected hydrogen refuelling stations and minimize the average distance of the city’s inhabitants to the nearest hydrogen refuelling station. As OD data are assumed to be unavailable, the clustering of stations in the highest traffic zones is prevented by a new constraint that takes into account information on the distribution of existing conventional refuelling stations. This model is applied to Seville, a city in Southern Spain of about 140 km² with a population of around 700,000. This application uses the results of a survey of more than 200 Sevillian drivers on their current refuelling tendencies, their willingness to use alternative fuel vehicles and their minimum requirements (regarding maximum distance to be travelled to refuel and number of stations in the city) when establishing a network of alternative refuelling stations.     

A discrete-convex programming approach to the simultaneous optimization of land use and transportation

Three design problems are discussed in this article. First, it is shown that the network design problem with congestion reduces to an all-or nothing traffic assignment problem under some assumptions on the congestion function and the investment cost function. Second, the land use design problem is formulated as an extension of the Koopmans-Beckmann problem and a heuristic is proposed to solve this problem. Third, it is shown that the seemingly more complex problem of designing jointly a land-use plan and a transportation network reduces to a pure land-use design problem. All that is needed to solve the joint optimization problem is a shortest path algorithm and a heuristic to solve the land use design problem. Computational experience is reported for each algorithm.     

Identifying the spatial distribution of public transportation trips by node and community characteristics

ABSTRACT

Identifying the spatial distribution of travel activities can help public transportation managers optimize the allocation of resources. In this paper, transit networks are constructed based on traffic flow data rather than network topologies. The PageRank algorithm and community detection method are combined to identify the spatial distribution of public transportation trips. The structural centrality and PageRank values are compared to identify hub stations; the community detection method is applied to reveal the community structures. A case study in Guangzhou, China is presented. It is found that the bus network has a community structure, significant weekday commuting and small-world characteristics. The metro network is tightly connected, highly loaded, and has no obvious community structure. Hub stations show distinct differences in terms of volume and weekend/weekday usage. The results imply that the proposed method can be used to identify the spatial distribution of urban public transportation and provide a new study perspective.