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.     

Adaptive traffic signal control using approximate dynamic programming

This paper presents a study on an adaptive traffic signal controller for real-time operation. The controller aims for three operational objectives: dynamic allocation of green time, automatic adjustment to control parameters, and fast revision of signal plans. The control algorithm is built on approximate dynamic programming (ADP). This approach substantially reduces computational burden by using an approximation to the value function of the dynamic programming and reinforcement learning to update the approximation. We investigate temporal-difference learning and perturbation learning as specific learning techniques for the ADP approach. We find in computer simulation that the ADP controllers achieve substantial reduction in vehicle delays in comparison with optimised fixed-time plans. Our results show that substantial benefits can be gained by increasing the frequency at which the signal plans are revised, which can be achieved conveniently using the ADP approach.     

An operational activity-based method to estimate CO2 emissions from container shipping considering empty container repositioning

This paper develops an operational activity-based method to estimate CO₂ emissions from container shipping in contrasts to the traditional aggregated activity-based method. Two case studies investigate the impacts of empty container repositioning policies and port handling capacity on CO₂ emission index. The results show that the aggregated method could well overestimate CO₂ emissions and the operational activity-based method is more appropriate. The paper also demonstrates that high port-handling capacity and efficient empty container repositioning could reduce CO₂ emissions in seaborne container transportation.     

Efficient planning of berth allocation for container terminals in Asia

Berth allocation is essential for efficient terminal utilization in container ports, especially those in Asia. This paper is concerned with a berth allocation problem(BAP) that minimizes the sum of port staying times of ships and that minimizes dissatisfaction of the ships in terms of the berthing order. In general there exist tradeoffs between these objectives. An algorithm is presented to identify noninferior solutions to the BAP. The algorithm is demonstrated with some sample problems and the results indicate the importance of the problem in efficient terminal utilization.     

Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach

This paper proposes a global optimization algorithm for solving a mixed (continuous/discrete) transportation network design problem (MNDP), which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). The upper level of the MNDP aims to optimize the network performance via both expansion of existing links and addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium (UE) problem. In this paper, we first formulate the UE condition as a variational inequality (VI) problem, which is defined from a finite number of extreme points of a link-flow feasible region. The MNDP is approximated as a piecewise-linear programming (P-LP) problem, which is then transformed into a mixed-integer linear programming (MILP) problem. A global optimization algorithm based on a cutting constraint method is developed for solving the MILP problem. Numerical examples are given to demonstrate the efficiency of the proposed method and to compare the results with alternative algorithms reported in the literature.     

An integrated, dynamic approach to travel demand forecasting

This paper presents a unified approach for improving travel demand models through the application and extension of supernetwork models of multi-dimensional travel choices. Proposed quite some time ago, supernetwork models solved to stochastic user equilibrium can provide a simultaneous solution to trip generation, distribution, mode choice, and assignment that is consistent with disaggregate models and predicts their aggregate effects. The extension to incorporate the time dimension through the use of dynamic equilibrium assignment methods is proposed as an enhancement that is necessary in order to produce realistic models. A variety of theoretical and practical problems are identified whose solution underlies implementation of this approach. Recommended future research includes improved algorithms for stochastic and dynamic equilibrium assignment, new methods for calibrating assignment models, and the use of Geographic Information Systems (GIS) technology for data and model management.     

Improving the performance of rail yards through dynamic reassignments of empty cars

This paper considers the problem of reducing the time that empty cars spend in classification yards of rail systems operating under real-time information and automated schedule-adjustment technologies. The proposed methodology performs dynamic reassignments of empty cars through a fast and efficient solution procedure based on the assignment algorithm. The procedure has been tested on real-life data from one of the major railroads in North America. Computational results show that the procedure runs fast and yields savings in the time that the empty cars spend in the yard.     

The price of uncertainty in pavement infrastructure management planning: An integer programming approach

Currently there is a true dichotomy in the pavement maintenance and rehabilitation (M&R) literature. On the one hand, there are integer programming-based models that assume that parameters are deterministically known. On the other extreme, there are stochastic models, with the most popular class being based on the theory of Markov decision processes that are able to account for various sources of uncertainties observed in the real-world. In this paper, we present an integer programming-based alternative to account for these uncertainties. A critical feature of the proposed models is that they provide – a priori – probabilistic guarantees that the prescribed M&R decisions would result in pavement condition scores that are above their critical service levels, using minimal assumptions regarding the sources of uncertainty. By construction of the models, we can easily determine the additional budget requirements when additional sources of uncertainty are considered, starting from a fully deterministic model. We have coined this additional budget requirement the price of uncertainty to distinguish from previous related work where additional budget requirements were studied due to parameter uncertainties in stochastic models. A numerical case study presents valuable insights into the price of uncertainty and shows that it can be large.     

A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem

A cell-based variant of the Merchant-Nemhauser (M-N) model is proposed for the system optimum (SO) dynamic traffic assignment (DTA) problem. Once linearized and augmented with additional constraints to capture cross-cell interactions, the model becomes a linear program that embeds a relaxed cell transmission model (CTM) to propagate traffic. As a result, we show that CTM-type traffic dynamics can be derived from the original M-N model, when the exit-flow function is properly selected and discretized. The proposed cell-based M-N model has a simple constraint structure and cell network representation because all intersections and cells are treated uniformly. Path marginal costs are defined using a recursive formula that involves a subset of multipliers from the linear program. This definition is then employed to interpret the necessary condition, which is a dynamic extension of the Wardrop’s second principle. An algorithm is presented to solve the flow holding back problem that is known to exist in many discrete SO-DTA models. A numerical experiment is conducted to verify the proposed model and algorithm.     

Combinatorial programming,statistical optimization and the optimal transportation network problem

This paper presents and evaluates a branch and bound algorithm and two heuristic hill-climbing techniques to solve a discrete formulation of the optimal transportation network design problem. For practical applications it is proposed to combine a hill-climbing algorithm with a uniform random generation of the initial solutions, thereby inducing a statistical distribution of local optima. In order to determine when to stop sampling local optima and in order to provide an estimate of the exact optimum based on the whole distribution of local optima, we follow previous work and fit a Weibull distribution to the empirical distribution of local optima. Several extensions are made over previous work: in particular, a new confidence interval and a new stopping rule are proposed. The numerical application of the statistical optimization methodology to the network design algorithms consolidates the empirical validity of fitting a Weibull distribution to the empirical distribution of local optima. Numerical experiments with hill-climbing techniques of varying power suggest that the method is best applied with heuristics of intermediate quality: such heuristics provide many distinct sample points for statistical estimation while keeping the confidence intervals sufficiently narrow.     

A relationship between the gravity model for trip distribution and the transportation problem in linear programming

A gravity model for trip distribution describes the number of trips between two zones as a product of three factors; one is associated with the zone in which a trip begins, one with the zone in which it ends and the third with the separation between the zones. The separation or deterrence factor is usually a decreasing function of the generalized cost of travelling between the zones, where generalized cost is usually some combination of the time of travel, the distance travelled and the actual monetary costs.If the deterrence factor is of the exponential form exp (-αc) and if the total numbers of origins and destinations in each zone are known, then the resulting trip matrix depends solely on α. In this paper it is shown that as α tends to infinity, this trip matrix tends to a limit in which the total cost of trips is the least possible allowed by the given origin and destination totals. That is to say the limit is a cost-minimizing solution to the linear programming transportation problem having the same origin and destination totals. If this transportation problem has many cost-minimizing solutions then it is shown that the limit is one particular solution in which each non-zero flow from an origin i to a destination j is of the form r_is_j. A numerical example is given.     

The use of dynamic programming in optimally allocating funds for highway safety improvements

An integrated system approach to traffic accident countermeasure selection is presented. This approach draws primarily upon the resources of a computerized accident records system for identifying high accident locations. Once high accident locations are identified by type, local investigations of these locations are conducted producing standardized cost and benefit data. These data are processed through a dynamic programming algorithm to produce optimal policies for implementation. Since this system has been in operation in two states in the United States for about five years, it should be of special interest to practitioners.     

An algorithm for the combined distribution and assignment problem

Much interest has recently been shown in the combination of the distribution and assignment models. In this paper we adopt a generalized Benders' decomposition to solve this combined problem for a system optimized assignment with linear link costs and explicit capacity constraints on link flows. The master problem which is generated is used to show that the combined problem can be viewed as a modified distribution problem, of gravity form, with a minimax instead of a linear objective function. An algorithm for solving the master problem is discussed, and some computational results presented.     

A statistical approach to the traveling salesman problem

A statistical approach is shown to be adaptable to the N-city traveling salesman problem by considering route distances to be random variables which are continuous and normally distributed. A solution to the shortest route distance and path can be approximated by utilizing a Monte Carlo simulation to obtain a representative sample of possible journeys. The approach involves recursive statistical inference which is used to select next-city visits leading to the most probable minimum route path. A statistical selection of the minimum route path is computationally efficient and computer run time increases in proportion to the square of the number of cities as opposed to an (N - 1)! increase for a deterministic approach. The accuracy of the statistical approach is directly proportional to the number of Monte Carlo simulations.     

FMOLP approach to the inland water transportation problem

Fuzzy optimization techniques can be applied in determining the optimal schedule for the transport of gravel by inland water transportation. Gravel demand, for example, is difficult to determine precisely since it depends on the industrial development of the regions supplied by gravel and on possible buyers. The duration of the annual navigation period varies depending on the water level, possible icebergs, heavy fog, strong and frequent wind. The transport company is usually satisfied if total transportation costs stay within a reasonable range. The formulation of a linear programme lacks flexibility in dealing with imprecise input data. In this paper this type of problem has been approached with fuzzy optimization techniques.     

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.     

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.     

Bi-objective optimization for the container terminal integrated planning

In this paper, we study the joint optimization of the tactical berth allocation and the tactical yard allocation in container terminals, which typically consist of berth side and yard side operations. The studied two objectives are: (i) the minimization of the violation of the vessels’ expected turnaround time windows with the purpose of meeting the timetables published by shipping liners, and (ii) the minimization of the total yard transportation distance with the aim to lower terminal operational cost. We propose a bi-objective integer program which can comprehensively address the import, export and transshipment tasks in port daily practice. Traditionally, a container transshipment task is performed as a couple of import and export tasks, called indirect-transshipment mode, in which the transit container are needed to be temporally stored in the yard. As the way of transferring containers directly from the incoming vessel to the outgoing vessel, called direct-transshipment mode, has potential to save yard storage resources, the proposed model also incorporates both indirect- and direct-transshipment modes. To produce Pareto solutions efficiently, we devise heuristic approaches. Numerical experiments have been conducted to demonstrate the efficiency of the approaches.     

An equilibrium algorithm for the spatial aggregation problem of traffic assignment

Present traffic assignment methods require that all possible origins and destinations of trips taking place within a study area be represented as if they were taking place to and from a small set of points or centroids. Each centroid is supposed to represent the location of all trip-ends within a given zone, and this necessarily misrepresents points located at the edges of the zone.In order to alleviate this problem (which we refer to as the spatial aggregation problem) one could use smaller zones and more centroids, but existing traffic assignment algorithms cannot efficiently handle many centroids.This paper introduces an algorithm procedure which is designed to handle a substantially larger number of centroids. In the paper that follows, the technique is further developed to take into account a continuous distribution of population.     

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.