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.     

Solving the bicriterion routing and scheduling problem for hazardous materials distribution

Hazardous materials routing and scheduling decisions involve the determination of the minimum cost and/or risk routes for servicing the demand of a given set of customers. This paper addresses the bicriterion routing and scheduling problem arising in hazardous materials distribution planning. Under the assumption that the cost and risk attributes of each arc of the underlying transportation network are time-dependent, the proposed routing and scheduling problem pertains to the determination of the non-dominated time-dependent paths for servicing a given and fixed sequence of customers (intermediate stops) within specified time windows. Due to the heavy computational burden for solving this bicriterion problem, an alternative algorithm is proposed that determines the k-shortest time-dependent paths. Moreover an algorithm is provided for solving the bicriterion problem. The proximity of the solutions of the k-shortest time-dependent path problem with the non-dominated solutions is assessed on a set of problems developed by the authors.     

Simplical decomposition of the asymmetric traffic assignment problem

This paper presents a convergent simplicial decomposition algorithm for the variational inequality formulation of the asymmetric traffic assignment problem. It alternates between generating minimum path trees based on the cost function evaluated at the current iterate and the approximate solving of a master variational inequality subject to simple convexity constraints. Thus it generalizes the popular Frank-Wolfe method (where the master problem is a line search) to the asymmetric problem. Rules are given for dropping flow patterns which are not needed to express the current iterate as a convex combination of previous patterns. The results of some computational testing are reported.     

Solutions to the optimal network design problem with shipments related to transportation cost

Two versions of an optimal network design problem with shipments proportional to transportation costs are formulated. Extensions of an algorithm developed in prior research for solving these problems are proposed and tested. The performance of the algorithms is found to improve substantially as the dependence of shipments on costs is increased. Moreover, the optimal solutions obtained are unexpectedly robust with respect to a wide range of transportation cost assumptions. These findings could have important computational and policy implications if applicable to larger networks.     

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.     

Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts

Trucking companies (carriers) are increasingly facing combinatorial auctions conducted by shippers seeking contracts for their transportation needs. The bid valuation and construction problem for carriers facing these combinatorial auctions is very difficult and involves the computation of a number of NP-hard sub problems. In this paper we examine computationally tractable approximation methods for estimating these values and constructing bids. The benefit of our approximation method is that it provides a way for carriers to discover their true costs and construct optimal or near optimal bids by solving a single NP-hard problem. This represents a significant improvement in computational efficiency. We examine our method both analytically and empirically using a simulation based analysis.     

Bus maintenance systems and maintenance scheduling: model formulations and solutions

This paper deals with the problem of scheduling bus maintenance activities. The scheduling of maintenance activities is an important component in bus transit operations planning process. The other components include network route design, setting timetables, scheduling vehicles, and assignment of drivers. This paper presents a mathematical programming approach to the problem. This approach takes as input a given daily operating schedule for all buses assigned to a depot along with available maintenance resources. It, then, attempts to design daily inspection and maintenance schedules for the buses that are due for inspection so as to minimize the interruptions in the daily bus operating schedule, and maximize the utilization of the maintenance facilities. Three integer programming formulations are presented and different properties of the problem are discussed. Several heuristic methods are presented and tested. Some of these procedures produce very close to optimal solutions very efficiently. In some cases, the computational times required to obtain these solutions are less than 1% of the computational time required for the conventional branch and bound algorithm. Several small examples are offered and the computational results of solving the problem for an actual, 181-bus transit property are reported.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

Formulating and solving the network design problem by decomposition

The optimal transportation network design problem is formulated as a convex nonlinear programming problem and a solution method based on standard traffic assignment algorithms is presented. The technique can deal with network improvements which introduce new links, which increase the capacity of existing links, or which decrease the free-flow (uncongested) travel time on existing links (with or without simultaneously increasing link capacity). Preliminary computational experience with the method demonstrates that it is capable of solving very large problems with reasonable amounts of computer time.     

Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition

This paper focuses on the simultaneous passenger train routing and timetabling problem on the rail network consisting of both unidirectional and bidirectional tracks using an efficient train-based Lagrangian relaxation decomposition. We first build an integer linear programming model with many 0–1 binary and non-negative integer decision variables, after then reformulate it as a train path-choice model for providing an easier train-based Lagrangian relaxation decomposition mechanism based on the construction of space-time discretized network extending from node-cell-based rail network. Moreover, through reformulating safety usage interval restrictions with a smaller number of constraints in this reformulated model, the train-based decomposition needs fewer Lagrangian multipliers to relax these constraints. On the basis of this decomposition, a solving framework including a heuristic algorithm is proposed to simultaneously optimize both the dual and feasible solutions. A set of numerical experiments demonstrate the proposed Lagrangian relaxation decomposition approach has better performances in terms of minimizing both train travel time and computational times.     

Analytical and grid-free solutions to the Lighthill-Whitham-Richards traffic flow model

In this article, we propose a computational method for solving the Lighthill-Whitham-Richards (LWR) partial differential equation (PDE) semi-analytically for arbitrary piecewise-constant initial and boundary conditions, and for arbitrary concave fundamental diagrams. With these assumptions, we show that the solution to the LWR PDE at any location and time can be computed exactly and semi-analytically for a very low computational cost using the cumulative number of vehicles formulation of the problem. We implement the proposed computational method on a representative traffic flow scenario to illustrate the exactness of the analytical solution. We also show that the proposed scheme can handle more complex scenarios including traffic lights or moving bottlenecks. The computational cost of the method is very favorable, and is compared with existing algorithms. A toolbox implementation available for public download is briefly described, and posted at http://traffic.berkeley.edu/project/downloads/lwrsolver.     

Distributed computing approaches for large‐scale probit‐based stochastic user equilibrium problems

Applications of probit‐based stochastic user equilibrium (SUE) principle on large‐scale networks have been largely limited because of the overwhelming computational burden in solving its stochastic network loading problem. A two‐stage Monte Carlo simulation method is recognized to have satisfactory accuracy level when solving this stochastic network loading. This paper thus works on the acceleration of the Monte Carlo simulation method via using distributed computing system. Three distributed computing approaches are then adopted on the workload partition of the Monte Carlo simulation method. Wherein, the first approach allocates each processor in the distributed computing system to solve each trial of the simulation in parallel and in turns, and the second approach assigns all the processors to solve the shortest‐path problems in one trial of the Monte Carlo simulation concurrently. The third approach is a combination of the first two, wherein both different trials of the Monte Carlo simulation as well as the shortest path problems in one trial are solved simultaneously. Performances of the three approaches are comprehensively tested by the Sioux‐Falls network and then a randomly generated network example. It shows that computational time for the probit‐based SUE problem can be largely reduced by any of these three approaches, and the first approach is found out to be superior to the other two. The first approach is then selected to calculate the probit‐based SUE problem on a large‐scale network example. Copyright © 2011 John Wiley & Sons, Ltd.     

On the existence of pricing strategies in the discrete time heterogeneous single bottleneck model

In this paper, we study the pricing strategies in the discrete time single bottleneck model with general heterogeneous commuters. We first prove that in the system optimal assignment, the queue time must be zero for all the departures. Based on this result, the system optimal problem is formulated as a linear program. The solution existence and uniqueness are discussed. Applying linear programming duality, we then prove that the optimal dual variable values provide an optimal toll with which the system optimal solution is also an equilibrium solution. Extensive computational results are reported to demonstrate the insights gained from the formulations in this paper. These results confirm that a system optimal equilibrium can be found using the proposed approach.     

长三角一体化框架下新建苏州机场的战略价值

本文从"坚持以人民为中心"的发展立场、解决不平衡不充分发展问题、融入国内国际双循环、构建更高水平一体化的城市—区域、综合交通体系建设以及机场布局规划制度创新等多个维度,阐述了长三角一体化背景下规划新建苏州机场的战略价值和社会实践意义。     

A comparison of user-optimum versus system-optimum traffic assignment in transportation network design

In this report, we compare the computational efficiency and results of solving two alternative models for the problem of determining improvements to an urban road network. Using a 1462 link, 584 node test network of the north Dallas area, we compare a model which assumes user-optimum behavior of travelers with a model which assumes system-optimum flows. Both of these models allow improvements to the road network to take on any nonnegative value, rather than requiring discrete improvement values. Investment costs are modeled by functions with decreasing marginal costs. Unfortunately, the user-optimum model, which is much more realistic than the system-optimum one, normally cannot be solved optimally. However, the simpler system-optimum model can be optimally solved, provided that investment costs are approximated by linear functions. Thus, for this network design problem we compare an accurate representation which can be solved only approximately with an approximate representation which can be solved optimally. Our computational testing showed that the system-optimum model produces solutions as good as those from the user-optimum model, and thus seems justified when favored by other considerations, such as ease of coding, availability of “canned” programs, etc.     

Co-design of traffic network topology and control measures

The two main directions to improve traffic flows in networks involve changing the network topology and introducing new traffic control measures. In this paper, we consider a co-design approach to apply these two methods jointly to improve the interaction between different methods and to get a better overall performance. We aim at finding the optimal network topology and the optimal parameters of traffic control laws at the same time by solving a co-optimization problem. However, such an optimization problem is usually highly non-linear and non-convex, and it possibly involves a mixed-integer form. Therefore, we discuss four different solution frameworks that can be used for solving the co-optimization problem, according to different requirements on the computational complexity and speed. A simulation-based study is implemented on the Singapore freeway network to illustrate the co-design approach and to compare the four different solution frameworks.     

Approximate algorithms for the discrete network design problem

The discrete network design problem is one of finding a set of feasible actions (projects) from among a collection of possible actions, that when implemented, optimizes some objective function(s). This is a combinatorial optimization problem that is very expensive to solve exactly. This paper proposes two algorithms for obtaining approximate solutions to the discrete network design problem with much less computational effeort. The computational savings are achieved by approximating the original problem with a new formulation which is easier to solve. The first algorithm proposed solves this approximate problem exactly, while the second is even more efficient, but provides only a near-optimal solution to the approximate problem. Experience with test problems indicates that these approximations can reduce the computational effort by a factor of 3–5, with little loss in solution accuracy.     

Selection of a trip table which reproduces observed link flows

In urban traffic management and planning, an important problem is estimating the number of drivers traveling between each origin-destination zone. We review a model due to Nguyen for estimating these numbers of drivers, based on counts of the traffic flows on each street, and develop an effective algorithm for solving it. The multiplicity of solutions of this model poses the additional question of which solution to use; we introduce a secondary optimization problem to overcome this difficulty. Efficient solution techniques are described for these problems and computational results are reported. It is noted that the most efficient solution methods involve user interaction to specify values of parameters which improve the convergence rates.     

Regulating hazardous materials transportation by dual toll pricing

We investigate dual-toll setting as a policy tool to mitigate the risk of hazardous material (hazmat) shipment in road networks. We formulate the dual-toll problem as a bi-level program wherein the upper level aims at minimizing the risk, and the lower level explores the user equilibrium decision of the regular vehicles and hazmat carriers given the toll. When the upper level objective is to minimize the risk and all links are tollable, we decompose the formulation into first-stage and second-stage, and suggest a computational method to solve each stage. Our two-stage solution methodology guarantees nonnegative valid dual tolls regardless of the solution accuracy of the first-stage problem. We also consider a general dual-toll setting problem where the regulator rather wishes to minimize a combination of risk and the paid tolls and/or some links are untollable. To solve this truly bilevel problem, we provide heuristic algorithms that decompose the problem into subproblems each being solved by a line search. Case studies based on the Sioux Falls network illustrate the insights on the dual-toll policies.     

A robust optimization approach for dynamic traffic signal control with emission considerations

We consider an analytical signal control problem on a signalized network whose traffic flow dynamic is described by the Lighthill–Whitham–Richards (LWR) model (Lighthill and Whitham, 1955; Richards, 1956). This problem explicitly addresses traffic-derived emissions as constraints or objectives. We seek to tackle this problem using a mixed integer mathematical programming approach. Such class of problems, which we call LWR-Emission (LWR-E), has been analyzed before to certain extent. Since mixed integer programs are practically efficient to solve in many cases (Bertsimas et al., 2011b), the mere fact of having integer variables is not the most significant challenge to solving LWR-E problems; rather, it is the presence of the potentially nonlinear and nonconvex emission-related constraints/objectives that render the program computationally expensive.To address this computational challenge, we proposed a novel reformulation of the LWR-E problem as a mixed integer linear program (MILP). This approach relies on the existence of a statistically valid macroscopic relationship between the aggregate emission rate and the vehicle occupancy on the same link. This relationship is approximated with certain functional forms and the associated uncertainties are handled explicitly using robust optimization (RO) techniques. The RO allows emissions-related constraints and/or objectives to be reformulated as linear forms under mild conditions. To further reduce the computational cost, we employ a link-based LWR model to describe traffic dynamics with the benefit of fewer (integer) variables and less potential traffic holding. The proposed MILP explicitly captures vehicle spillback, avoids traffic holding, and simultaneously minimizes travel delay and addresses emission-related concerns.