Search

China has recently developed a large-scale high-speed railway (HSR) network that not only revolutionizes the perception of long-haul transport but also fundamentally improves the emergency response capability of the country. This gives rise to a problem of scheduling a set of emergency trains within the predefined HSR timetable. According to different degrees of disturbance of the timetable, this paper identifies three kinds of solutions, named, ideal, quasi-ideal, and feasible solutions, to the problem. We define a "headroom" function for computing the maximum number of emergency trains that can be inserted between two adjacent regular trains without any disturbance, from which a linear algorithm for finding ideal solutions is derived. By identifying the scope of changes to each regular train, quasi-ideal and feasible solutions can be found based on the ideal solutions on a set of alternative timetables. Numerical experiments demonstrate that our method is very efficient for supporting near-immediate emergency responses. We have used the solution method to evaluate the emergency capacity of most HSR lines in China. In particular, we successfully applied the method to schedule emergency trains in the rescue operation of the 2015 Tianjin chemical explosion. The online appendix is available at https://doi.org/10.1287/trsc.2017.0794. [ABSTRACT FROM AUTHOR]

This paper presents a theory of traffic equilibrium which involves responsive signal control policies; in this theory drivers' route choices and the control policy's choice of green times are treated in a symmetrical manner. The central theme of the paper is the iterative optimization assignment algorithm. This algorithm may be considered as a means of calculating equilibria which are consistent with a given responsive control policy. But it may also be regarded as a highly idealized model of the day to day dynamics of drivers' route choices when a responsive signal setting policy is employed; on "day" 1 the signals are held fixed and drivers settle down to an equilibrium flow pattern, on "day 2" the flow pattern is held fixed and the signals are updated according to the control policy for the fixed flow pattern, on "day" 3 the signals are held fixed and drivers settle down to an equilibrium flow pattern.... We state natural but strong conditions on the responsive control policy which guarantee that this algorithm is bound to converge to a convex set of (flow, control) pairs such that (i) the flow is a user equilibrium and (ii) the control parameters satisfy the responsive control policy; and we give a proof of convergence under these conditions--we do not seek to minimize total travel cost. Our conditions involve the delay or cost formula used; with the BPR cost formula, modified in a natural way to allow for green times, the traditional policy of choosing control parameters which minimize delay for the observed traffic pattern does satisfy these conditions in full. However, with Webster's delay formula traditional control policies are a long way... [ABSTRACT FROM AUTHOR]

Numerous transportation applications as diverse as capital investment decision- making, vehicle fleet planning, and traffic light signal setting all involve some form of (discrete choice) network design. In this paper, we review some of the uses and limitations of integer programming-based approaches to network design, and describe several discrete and continuous choice models and algorithms. Our objectives are threefold--to provide a unifying view for synthesizing many network design models, to propose a unifying framework for deriving many network design algorithms, and to summarize computational experience in solving design problems. We also show that many of the most celebrated combinatorial problems that arise in transportation planning are specializations and variations of a generic design model. Consequently, the network design concepts described in this paper have great potential application in a wide range of problem settings. [ABSTRACT FROM AUTHOR]

This paper discusses a family of general link cost functions that can be used to model multimodal transportation network equilibrium problems. The family includes as a special case the currently favored family of monotonically increasing functions but does not necessarily have to have a symmetric or semi-definite Jacobian. In this way multimodal networks can be modeled somewhat more realistically. The paper also allows stochastic link costs for some or all the links and modes. It is shown that under mild conditions the equilibrium exists and is unique, but more importantly, that there is a simple, single-equilibrium algorithm that is proven to converge for stochastic networks with the link cost family discussed in the paper. Finally, it is pointed out that many variable demand problems also exhibit unique equilibria, but that there are some which do not. An example which illustrates this fact is given. [ABSTRACT FROM AUTHOR]

This paper presents a method for finding optimal flows in a dynamic network with random inputs into the system and congestion limits on flow. This model has been used in deterministic settings to represent dynamic traffic assignment and job shop routing. This paper builds on the deterministic results to show that a globally optimal solution in the stochastic problem may be obtained by a sequence of linear optimizations. A decomposition algorithm for this procedure is presented that efficiently solves problems with large-scale deterministic equivalents of up to 66,000 variables. [ABSTRACT FROM AUTHOR]

Sensor systems as critical components of a transportation network provide a variety of real-time traffic surveillance information for traffic management and control. The deployment of sensors significantly affects their overall surveillance effectiveness. This paper proposes a reliable sensor location model to optimize surveillance effectiveness when sensors are subject to site-dependent probabilistic failures, and a general effectiveness measure is proposed to encompass most existing measures needed for engineering practice (e.g., flow volume coverage, vehicle-mile coverage, and squared error reduction). The problem is first formulated into a compact mixed-integer program, and we develop a variety of solution algorithms (including a custom-designed Lagrangian relaxation algorithm) and analyze their properties. We also propose alternative formulations including a continuum approximation model for single corridor problems and reliable fixed-charge sensor location models. Numerical case studies are conducted to test the performance of the proposed algorithms and draw managerial insights on how different parameter settings (e.g., failure probability and spatial heterogeneity) affect overall surveillance effectiveness and the optimal sensor deployment. [ABSTRACT FROM AUTHOR]

Traffic controllers regulate railway traffic by sequencing train movements and setting routes with the aim of ensuring smooth train behaviour and limiting, as much as possible, train delays. In this paper, we describe the implementation of a real-time traffic management system, called ROMA (Railway traffic Optimization by Means of Alternative graphs), to support controllers in the everyday task of managing disturbances. We make use of a branch-and-bound algorithm for sequencing train movements, while a local search algorithm is developed for rerouting optimization purposes. The compound problem of routing and sequencing trains is approached iteratively, computing an optimal train sequencing for given train routes and then improving this solution by locally rerouting some trains. An extensive computational study is carried out, based on a dispatching area of the Dutch railway network. We study practical size instances, and include in the model important operational constraints, including rolling stock and passenger connections. Different types of disturbances are analysed, including train delays and blocked tracks. Comparison with common dispatching practice shows the high potential of the system as an effective support tool to improve punctuality. [ABSTRACT FROM AUTHOR]

Recently, extensive studies have been conducted on the computational methods of sensitivity analysis for the Wardropian equilibrium modeling of traffic networks and their applications. But the same problems in the context of the stochastic user equilibrium modeling seem not to have been addressed. In this paper, we present a method for sensitivity analysis for network flows at stochastic user equilibrium. Our method is developed from a dual formulation of the stochastic user equilibrium analysis. By adopting Dial's algorithm for stochastic traffic assignment, we are able to formulate a computationally efficient link-based algorithm for the sensitivity analysis. Since the Wardropian equilibrium in a traffic network is an extreme case of stochastic user equilibrium with θ → ∞, θ being a dispersion parameter in the expected utility function for stochastic route choice, the method presented here can also be used for sensitivity analysis of the Wardropian equilibrium by setting θ large enough. [ABSTRACT FROM AUTHOR]

In this paper we present a version of the (static) traffic equilibrium problem in which the cost incurred on each path is not simply the sum of the costs on the arcs that constitute that path. We motivate this nonadditive version of the problem by describing several situations in which the classic additivity assumption fails. We describe existence and uniqueness conditions for this problem, and we also present convergence theory for a generic algorithm for solving nonadditive problems. [ABSTRACT FROM AUTHOR]

Traditionally, traffic assignment models, both for within-day static and dynamic demand, have been formulated following an equilibrium approach in which a state ensuring internal consistency between demand (flows) and costs is sought. However, equilibrium analysis is significant under some assumptions on its "representativeness" (coincidence or closeness with the actual attractor of the system) and analytical properties, such as existence, uniqueness, and stability. Moreover, transients due to modifications of demand and/or supply cannot be simulated through equilibrium models, nor can a statistical description of the state of the system, i.e. means, modes, moments and, more generally, frequency distributions of flows over time be obtained. In this paper, interperiodic (day-to-day) dynamic modeling of transportation networks is addressed following two different approaches, namely deterministic and stochastic processes. In both cases several theoretical results are shown by making use of a formal framework covering most models discussed in the literature as well as some possible extensions. Most of the results reported can be extended to cover within-day dynamic models but these models are not explicitly dealt with. Within the framework of deterministic processes the relevance of day-to-day dynamic models for demand/supply interaction in comparison with the traditional user equilibrium approach is discussed, and conditions for coincidence of fixed-point attractors and equilibrium states are stated. Conditions for existence and uniqueness of fixed-point attractors are proposed, generalizing and extending those presented in the literature for user equilibrium. Conditions for stability of both fixed-points and equilibrium states were formulated by making use of results from non-linear dynamic system theory. Moreover, it is possible to devise a new family of "dynamic" algorithms which simulate the system convergence to a fixed-point in order to obtain an equivalent equilibrium state, as opposed to conventional "optimisation" algorithms. In this case the fixed-point stability analysis can be viewed as a convergence analysis for the algorithms specified this way. Conditions for stochastic process regularity are proposed ensuring, among other things, existence and uniqueness of a stationary probability distribution of system states. These conditions generalize and extend results presented in the literature to a wider class of possible dynamic models. Relationships between a deterministic process, together with corresponding fixed-points or equilibrium states, and stochastic probability distribution are also briefly addressed. Finally, some numerical examples confirming theoretical results are reported for a small test network. [ABSTRACT FROM AUTHOR]

In this paper, we present a primal-dual, heuristic solution approach for large-scale multicommodity network flow problems. The original problem is solved indirectly by repeatedly solving restated feasibility problems. Restrictions on problem size imposed by exact methods are overcome by solving the restated problems with a pure network-based heuristic procedure. To control the heuristic solution process, the network-based procedure is embedded within an iterative primal-dual framework. At each iteration, feasible dual solutions are generated, the dual objective function value strictly ascends, and primal solutions that are measurably closer to feasibility are determined. The algorithm terminates when the heuristic network-based procedure cannot determine an improved primal solution or when optimality is achieved. To demonstrate the effectiveness of the network-based solution strategy, a large-scale freight assignment problem encountered in the trucking industry is formulated as a multicommodity network flow problem. Two linear programming based, exact solution strategies (a primal-dual algorithm and a price-directive algorithm) are unable to achieve even an initial solution for this problem due to excessive memory requirements. The network-based heuristic, however, determines an optimal solution. We compare the performance of the new heuristic with that of the exact procedures using a set of smaller test problems. The effects of problem formulation and congestion are evaluated for each of the alternative solution strategies. [ABSTRACT FROM AUTHOR]

In this paper a restriction (simplicial decomposition) strategy is employed to efficiently implement a modified Newton method to solve the general asymmetric network equilibrium problem. Implementation details are discussed. Numerical results on one small-scale and one medium-scale problem, with varying asymmetry levels, are presented. Performance o[ the algorithms with respect to the asymmetry level of the cost mapping is assessed. [ABSTRACT FROM AUTHOR]

This paper examines the problems of routing freight traffic, scheduling train services and allocating classification work between yards on a rail network. It describes a general optimization model which takes into account the interactions between these activities and develops global strategies for their management over a medium term planning horizon. A heuristic algorithm developed to solve this nonlinear, mixed-integer multicommodity flow problem is also presented with some computational results based on an example at the Canadian National Railroads. [ABSTRACT FROM AUTHOR]

This paper modifies the exact Dynamic Programming algorithm developed by the author for the single vehicle many-to-many immediate request Dial-A-Ride problem to solve the problem where each customer has specified upper and lower bounds for his pickup and delivery times and where the objective is to minimize the time needed to service all customers. The major difference between the two algorithms is the substitution of backward recursion with forward recursion. The new algorithm requires the same computational effort as the old one (0(N²3N) for N customers) and is able to recognize infeasible problem instances. [ABSTRACT FROM AUTHOR]

In a noncongested transportation network where each user chooses his quickest route, the creation of an additional route between some origin-destination pair clearly cannot result in an increase in travel time to users traveling between that o-d pair. It seems reasonable to assume the same can be said of congested networks. In 1968, D. Braess presented a remarkable example demonstrating this is not the case: a new route can increase travel time for all. The present paper gives, under reasonable assumptions, necessary and sufficient conditions for "Braess' Paradox" to occur in a general transportation network. As a corollary, we obtain that Braess' Paradox is about as likely to occur as not occur. [ABSTRACT FROM AUTHOR]

One of the most important functions of air traffic management systems is the assignment of ground-holding times to flights, i.e., the determination of whether and by how much the take-off of a particular aircraft headed for a congested part of the ATC system should be postponed to reduce the likelihood and extent of airborne delays. In this paper, we will present an analysis of the fundamental case in which flights from many origins must be scheduled for arrival at a single, congested airport. We will describe a set of approaches for addressing a deterministic and a stochastic version of the problem. A minimum cost flow algorithm can be used for the deterministic problem. Under a particular natural assumption regarding the functional form of delay costs, a very efficient, simple algorithm is also available. For the stochastic version, an exact dynamic programming formulation turns out to be impractical for typical instances of the problem and we present a number of heuristic approaches to it. The models and numerical results suggest the potential usefulness of formal decision support tools in developing effective ground-holding strategies. Many methodological and implementation issues, however, still require resolution. [ABSTRACT FROM AUTHOR]

The general problem is that of locating a central facility in a network so as to minimize the sum of its distances from the sources of flow to it, each distance being appropriately weighted to reflect the associated flow volume and/or cost. In this paper, simple one-pass solution algorithms are given for two classes of topologically simple networks, namely those which are either acyclic or contain exactly one cycle. The first algorithm is based on a reduction procedure that may also yield useful simplification of problems involving general networks. [ABSTRACT FROM AUTHOR]

In this paper the authors find the optimal allocation of servicing periods to a facility servicing N incoming traffic streams. In our model it is assumed that stream flows are deterministic, that there is a fixed amount of lime lost, τi , when the server switches attention from the ith to the i + 1st stream and that the objective is to minimize time average delay. [ABSTRACT FROM AUTHOR]