Search

This paper presents a method to identify the set of routes and their flows in a user-equilibrium traffic assignment solution. We present a general consistency condition that is satisfied by any set of minimum-cost routes, and show how it can be used in choosing a set of routes that is likely to be similar to the set of user-equilibrium routes. The proposed consistency condition is also essential for finding the entropy-maximizing route flows solution, which may be regarded as the most likely one. An efficient method for finding the entropy-maximizing solution is presented. Numerical results on several networks, including one of large scale, demonstrate the effectiveness of the proposed method. In most cases the method achieves a duality gap of practically zero in a short computation time. [ABSTRACT FROM AUTHOR]

Many complex transportation models can be formulated as fixed-point problems. Typical examples are the "equilibrium-like" models, motivated by the need to capture the interaction between the transport supply (that is, the infrastructure) and transport demand (that is, travelers' behavior) in various ways. In this paper, we propose a new approach for solving fixed-point problems and, equivalently, systems of nonlinear equations. It is a generalization of secant methods, and uses several previous iterates to generate a linear approximation of the nonlinear function. Although it belongs to the quasi-Newton family of methods, our algorithm is matrix free, allowing it to solve large-scale systems of equations without derivative and without any particular assumption about the structure of the problem or its Jacobian. Computational experiments on standard problems show that this algorithm outperforms classical, large-scale quasi-Newton methods in terms of efficiency and robustness. Its numerical performances are similar to Newton- Krylov methods currently considered as the best algorithms to solve large-scale nonlinear systems of equations. Furthermore, our approach, using multiple previous iterates to build a linear approximation of the nonlinear function, exhibits robust behavior in the presence of noise in the equations, which makes it particularly well adapted to transportation problems. We run our algorithm on a simple origin-destination (OD) matrix estimation problem and on some instances of the consistent anticipatory route guidance (CARG) problem, to illustrate the applicability of the proposed method and to show its significant superiority to the classical method of successive averages (MSA). Regarding size, we were able to solve a CARG problem with more than 120,000 variables. We were also able to solve classical problems with up to two million variables. [ABSTRACT FROM AUTHOR]

Classical facility location models like the P-median problem (PMP) and the uncapacitated fixed-charge location problem (UFLP) implicitly assume that, once constructed, the facilities chosen will always operate as planned. In reality, however, facilities "fail" from time to time due to poor weather, labor actions, changes of ownership, or other factors. Such failures may lead to excessive transportation costs as customers must be served from facilities much farther than their regularly assigned facilities. In this paper, we present models for choosing facility locations to minimize cost, while also taking into account the expected transportation cost after failures of facilities. The goal is to choose facility locations that are both inexpensive under traditional objective functions and also reliable. This reliability approach is new in the facility location literature. We formulate reliability models based on both the PMP and the UFLP and present an optimal Lagrangian relaxation algorithm to solve them. We discuss how to use these models to generate a trade-off curve between the day-to-day operating cost and the expected cost, taking failures into account, and we use these trade-off curves to demonstrate empirically that substantial improvements in reliability are often possible with minimal increases in operating cost. [ABSTRACT FROM AUTHOR]

Passengers on a transit network with common lines are often faced with the problem of choosing between either to board the arriving bus or to wait for a faster one. Many assignment models are based on the classical assumption that at a given stop passengers board the first arriving carrier of a certain subset of the available lines, often referred to as the attractive set. In this case, it has been shown that, if the headway distributions are exponential, then an optimal subset of lines minimizing the passenger travel time can be easily determined. However, when online information on future arrivals of buses are posted at the stop, it is unlikely that the above classical assumption holds. In this case, passengers may choose to board a line that offers the best combination of displayed waiting time and expected travel time to their destination once boarded. In this paper, we propose a general framework for determining the probability of boarding each line available at a stop when online information on bus waiting times is provided to passengers. We will also show that the classical model without online information may be interpreted as a particular instance of the proposed framework, this way achieving an extension to general headway distributions. The impact of the availability of information regarding bus arrivals and that of the regularity of transit lines on the network loads, as well as on the passenger travel times, will be illustrated with small numerical examples. [ABSTRACT FROM AUTHOR]

The current airline practice in conducting fleet assignments is to begin assigning aircraft capacity to scheduled flights well in advance of departures. However, the accuracy of the passenger demand forecast improves markedly over time, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. The demand-driven refleeting (DDR) approach proposed in this paper offers a dynamic reassignment of aircraft capacities to the flight network, when improved demand forecasts become available, so as to maximize the total revenue. Because of the need to preserve the initial crew schedule, this reassignment approach is limited within a single family of aircraft types and to the flights assigned to this particular family. This restriction makes it computationally tractable to include more relevant path-level demand information into the DDR model. Accordingly, we construct a mixed-integer programming model for this enhanced problem context and study its polyhedral structure to explore ways for tightening its representation and for deriving certain classes of valid inequalities. Various schemes for implementing such reformulation techniques are investigated and tested using a set of simulated and real instances obtained from United Airlines. [ABSTRACT FROM AUTHOR]

This paper surveys the research on the metaheuristics for the Vehicle Routing Problem with Time Windows (VRPTW).The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Metaheuristics are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvement heuristics described in the first part of this article. In addition to describing basic features of each method, experimental results for Solomon's benchmark test problems are presented and analyzed. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a model structure that analyzes the hub-spoke network design issue within a competitive framework. Under deregulation, airlines have developed hub- and-spoke networks, enabling them to increase frequency by aggregating demand and to prevent entry into the marketplace by educing airfares. While liberalization in the United States and Europe was undertaken to increase competition, the results in this direction are unclear. This research evaluates airline profits based on a microeconomic theory of airline behavior under deregulation and the effect on hub-and-spoke networks. Through a two-stage, Nash best-response game, we search for equilibria in the air transportation industry. The game is applied to Western Europe,where profitable hubs and monopolistic equilibria are clearly identifiable, and duopolistic equilibria are potentially viable, given sufficient demand. [ABSTRACT FROM AUTHOR]

In this paper we examine the traveling saleman problem with time windows for various degrees of dynamism. In contrast to the static problem, where the dispatcher can plan ahead, in the dynamic version, part or all of the necessary information becomes available only during the day of operation. We seek to minimize lateness and examine the impact of this criterion choice on the distance traveled. Our focus on lateness is motivated by the problem faced by overnight mail service providers. We propose a real-time solution method that requires the vehicle, when idle, to wait at the current customer location until it can service another customer without being early. In addition, we develop several enhanced versions of this method that may reposition the vehicle at a location different from that of the current customer based on a priori information on future requests. The results we obtained on both randomly generated data and on a real-world case study indicate that all policies proved capable of significantly reducing lateness. Our results also show that this can be accomplished with only small distance increases. The basic policy outperformed the other methods primarily when lateness and distance were equally minimized and proved very robust in all environments studied. When only lateness was considered, the policy to reposition the vehicle at a location near the current customer generally provided the largest reductions in average lateness and the number of late customers. It also produced the least extra distance to be traveled among the relocation policies. [ABSTRACT FROM AUTHOR]

In this paper,we present a solution approach for the inventory-routing problem. The inventory-routing problem is a variation of the vehicle-routing problem that arises in situations where a vendor has the ability to make decisions about the timing and sizing of deliveries, as well as the routing, with the restriction that customers are not allowed to run out of product. We develop a two-phase approach based on decomposing the set of decisions: A delivery schedule is created first, followed by the construction of a set of delivery routes. The first phase utilizes integer programming, whereas the second phase employs routing and scheduling heuristics. Our focus is on creating a solution methodology appropriate for large-scale real-life instances. Computational experiments demonstrating the effectiveness of our approach are presented. [ABSTRACT FROM AUTHOR]

This paper presents a solution approach to the dynamic vehicle scheduling problem. This approach consists of solving a sequence of optimization problems, where we take into account different scenarios for future travel times. We discuss the potential benefit of our approach compared to the traditional one, where the vehicle scheduling problem is solved only once for a whole period and the travel times are assumed to be fixed. Because in the multiple-depot case we cannot solve the problem exactly within reasonable computation time, we use a "cluster-reschedule" heuristic where we first assign trips to depots by solving the static problem and then solve dynamic single-depot problems. We use new mathematical formulations of these problems that allow fast solution by standard optimization software. Results of a computational study with real-life data are presented, in which we compare different variants of our approach and perform a sensitivity analysis with respect to deviations of the actual travel times from estimated ones. [ABSTRACT FROM AUTHOR]

There has been considerable recent interest in the dynamic vehicle routing problem, but the complexities of this problem class have generally restricted research to myopic models. In this paper, we address the simpler dynamic assignment problem, where a resource (container, vehicle, or driver) can serve only one task at a time. We propose a very general class of dynamic assignment models,and propose an adaptive,nonmyopic algorithm that involves iteratively solving sequences of assignment problems no larger than what would be required of a myopic model. We consider problems where the attribute space of future resources and tasks is small enough to be enumerated,and propose a hierarchical aggregation strategy for problems where the attribute spaces are too large to be enumerated. Finally,we use the formulation to also test the value of advance information,which offers a more realistic estimate over studies that use purely myopic models. [ABSTRACT FROM AUTHOR]

This paper deals with a generalisation of the well-known traveling salesman problem (TSP) in which cities correspond to customers providing or requiring known amounts of a product, and the vehicle has a given upper limit capacity. Each customer must be visited exactly once by the vehicle serving the demands while minimising the total travel distance. It is assumed that any unit of product collected from a pickup customer can be delivered to any delivery customer. This problem is called one-commodity pickup-and-delivery TSP (1-PDTSP). We propose two heuristic approaches for the problem: (1) is based on a greedy algorithm and improved with a k-optimality criterion and (2) is based on a branch-and-cut procedure for finding an optimal local solution. The proposal can easily be used to solve the classical "TSP with pickup-and-delivery," a version studied in literature and involving two commodities. The approaches have been applied to solve hard instances with up to 500 customers. [ABSTRACT FROM AUTHOR]

A game between two players acting on the same road transportation network is considered in this paper. The first player aims at minimizing the transportation costs, whereas the second player aims at maximizing her profit (or, in general, her utility) that is proportional to the flow passing through the arcs under her control. We introduce bilevel linear programming formulations for this problem. We derive conditions of existence and properties of the equilibrium points and propose an algorithm finding a local optimal solution. Finally, we present an application of the model to a real system involving trucks travelling through Europe from a Middle Eastern country. [ABSTRACT FROM AUTHOR]

This paper describes a novel optimization-based approach to benefits analysis that allows us to analyze new collaborative air traffic management tools. We apply this method to analysis of the Collaborative Arrival Planner (CAP), a concept under development by NASA as part of a suite of decision-support tools for improved air traffic management. Central to our benefits analysis is an integer program, the Arrival Sequencing Model (ASM), which minimizes cost through adjustments to the arrival sequence. We use the ASM to evaluate whether CAP-enabled airline control over and/or visibility into the airport arrival sequencing process could improve overall performance of the air transportation system. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of shortest path problems where, in addition to congestion related time-dependent link travel times on a given transportation network, we also have specific labels for each arc denoting particular modes of travel. The problem then involves finding a time-dependent shortest path from an origin node to a destination node that also conforms with some admissible string of labels. This problem arises in the Route Planner Module of Transportation Analysis Simulation System (TRANSIMS), which is developed by the Los Alamos National Laboratory and is part of a multitrack Travel Model Improvement Program sponsored by the U.S. Department of Transportation (DOT) and the Environmental Protection Agency (EPA). We propose an effective algorithm for this problem by adapting efficient existing partitioned shortest path algorithmic schemes to handle time dependency along with the label constraints. We also develop several heuristics to curtail the search based on various route restrictions, indicators of progress, and projected travel times to complete the trip. The proposed methodology is applied to solve some real multimodal test problems related to the Portland, Oregon, transportation system. Computational results for both the exact method and the heuristic curtailing schemes are provided. [ABSTRACT FROM AUTHOR]

We consider the problem of assigning trains to the available tracks at a railway station, given the daily timetable and the structural and operational constraints. This train-platforming problem is a key problem in railway station operations, and for a large station, many working days are required for an expert planner to construct the train-platforming. This problem was studied in De Luca Cardillo and Mione (1998), where it is formulated as a graph-coloring problem. These authors propose to solve it by an efficient heuristic algorithm combined with reduction techniques. In this paper, we show that integer programming is a very interesting tool to exactly solve the train-platforming problem as formulated in De Luca Cardillo and Mione (1998) by a graph-coloring problem. The fact of being able to solve it in an exact way by using an integer-programming solver obviously has many advantages. Some computational results are reported. [ABSTRACT FROM AUTHOR]

Queue overflow is a critical issue in developing queue prediction technologies for applications in Advanced Transportation Management System (ATMS). Conventional queue prediction methods, however, are limited to incident-free queue length prediction where traffic arrivals can be readily obtained using detectors. Despite the problems posed by queue overflow, studies addressing queue-overflow issues, or for predicting queue overflows beyond detectors, appear inadequate. This paper describes an advanced methodology which uses a stochastic system modeling approach and random processes for predicting queue lengths beyond detectors in real time. Lane changing is taken into account in developing the queue-overflow prediction model because lane changing accompanies queue overflow in most cases. A discrete-time, nonlinear stochastic system is specified for modeling the queues and lane changes beyond detectors during queue-overflow occurrence. The noise terms of the recursive equations of the model account for the effects of queues and a variety of arriving volumes on vehicular lane-changing maneuvers during queue-overflow occurrence. The unknown traffic arrivals beyond detectors are predicted employing random processes. In addition, a recursive estimation algorithm for predicting real-time queue overflows is developed utilizing the extended Kalman filtering technique. Preliminary test results indicate that the proposed methodology is promising for real-time prediction of queue overflows. The predicted queue overflows can be used not only in understanding the phenomenon of lane traffic patterns during queue-overflow occurrence, but also in developing related advanced technologies such as real-time road traffic congestion control and management systems. [ABSTRACT FROM AUTHOR]

This paper investigates minimum time and minimum cost path problems in street networks regulated by periodic traffic lights. We show that the minimum time path problem is polynomially solvable. On the other hand, minimum cost path problems are generally NP-hard. Special, realistic cases which are polynomially solvable are discussed. [ABSTRACT FROM AUTHOR]

Real traffic networks typically exhibit considerable day-to-day variations in traffic flows and travel times, yet these variations are commonly neglected in network performance models. Recently, two alternative theoretical approaches were proposed for incorporating stochastic flow variation in the equilibration of route choices: the stochastic process (SP) approach (Cantarella and Cascetta 1995) and the second order generalized stochastic user equilibrium (GSUE(2)) model (Watling 2002). The theoretical basis of the two approaches is contrasted, and the paper goes on to present a heuristic solution method for the GSUE(2) model, and two alternative simulation methods for the SP model, each applicable to the realistic case of probit-based choice probabilities. These solution methods are then applied to two realistic networks. Factors affecting convergence and reproducibility are first identified, followed by comparisons of the GSUE(2) and SP predictions. It is seen that a quasi-periodic behaviour commonly arises in the SP model, with the predictions radically different from the GSUE(2) model. However, by modifying the link performance functions in the overcapacity regime, the nature of the SP solution changes, and for a memory filter based on a large number of days' experience, its moments are seen to be approximated by those of the GSUE(2) model. Implications for the application of these models are discussed. [ABSTRACT FROM AUTHOR]

In this paper we describe a new approach to solving the express shipment service network design problem. Conventional polyhedral methods for network design and network loading problems do not consistently solve instances of the planning problem we consider. Under a restricted version of the problem, we transform conventional formulations to a new formulation using what we term composite variables. By removing flow decisions as explicit decisions, this extended formulation is cast purely in terms of the design elements. We establish that its linear programming relaxation gives stronger lower bounds than conventional approaches. We apply this composite variable formulation approach to the UPS Next Day Air delivery network and demonstrate potential annual cost savings in the hundreds of millions of dollars. [ABSTRACT FROM AUTHOR]

The delivery of vehicles to dealers is one of the major tasks in the vehicle production industry. It has relied on transportation companies that use special tractor-trailer trucks called auto-carriers. One of the main problems these companies have to solve is the optimal loading and routing of the auto-carriers, referred to as the Auto-Carrier Transportation (ACT) problem. In this paper we provide an integer programming formulation of the ACT problem and show that the problem is NP-hard in the strong sense. A three-step heuristic procedure strongly based on the IP formulation, which considers loading, vehicle selection, and routing aspects, is proposed. An application to a real case study of a vehicle transportation company located in northern Italy is given, with an average deviation lower than 3% from an upper bound on the optimal solution value. [ABSTRACT FROM AUTHOR]

This paper presents a new graph theoretic framework for the passenger assignment problem that encompasses simultaneously the departure time and the route choice. The implicit FIFO access to transit lines is taken into account by the concept of available capacity. This notion of flow priority has not been considered explicitly in previous models. A traffic equilibrium model is described and a computational procedure based on asymmetric boarding penalty functions is suggested. [ABSTRACT FROM AUTHOR]

In order to improve the performances of transit modeling and in particular to assess the effects of the introduction of ITS technologies, which imply substantial changes in user behavior, in the last 10 years transit path choice and assignment models that use a schedule-based approach, instead of the traditional frequency-based one, have been developed. This paper presents a schedule-based path choice model for high-frequency transit networks, which allows us to consider the evolution in time of transit services, both within-day and day-to-day, as well as the day-to-day learning process of attributes by which users choose. On the basis of this path choice model a dynamic process assignment model, both within-day and day-to-day (from which the term "doubly dynamic" derives), was developed and tested on a realistically sized network to verify its applicability for operations planning. [ABSTRACT FROM AUTHOR]

This paper is concerned with the existence of solutions to a dynamic network equilibrium problem modeled as an infinite dimensional variational inequality. Our results are based on properties of operators that map path flow departure rates to consistent time-dependent path flows and other link performance functions. The existence result requires the introduction of a novel concept that strengthens the familiar concept of First-In-First-Out (FIFO). [ABSTRACT FROM AUTHOR]

Average delay is an important criterion of evaluating traffic signals. Traffic signals, stream merges, and stream splits influence vehicular delay in signalized networks through influencing random fluctuation of traffic. This paper proposes a method of estimating the random component of queues and delays at signalized intersections inside a network of urban streets. Equations describing the effect of signals and traffic merging and splitting are derived, as well as a comprehensive equation combining the considered effects. Fixed speeds and capacities are assumed. The derived comprehensive equation is used to discuss certain cases of signalized streets. The equation is evaluated using the Monte Carlo technique. The proposed method can be incorporated into existing procedures for evaluating and optimizing traffic signals. [ABSTRACT FROM AUTHOR]

This paper introduces a network design problem with a structure that is encountered in many transportation processes. The general organization of these systems is as follows. Freight has to be transported between a large number of origins and destinations. To consolidate the freight, it is first shipped to a terminal. Next, it is transported directly to a terminal where it is re-loaded and shipped to its destination. The task is to decide which terminals have to be used and how the freight is transported among the terminals. We describe an application where the terminals are airports and the freight is letter mail. Here, the transportation between terminals is by air, which is required due to temporal constraints. The economical impact of these decisions is huge because air transportation is costly and the process is repeated every night. We show how the problem can be modeled as a capacitated warehouse location problem with side constraints and propose a hybrid Tabu Search/Branch-and-Bound algorithm, which solves large real-world instances with acceptable computation times. [ABSTRACT FROM AUTHOR]

We consider stochastic, time-varying transportation networks, where the arc weights (arc travel times) are random variables with probability distribution functions that vary with time. Efficient procedures are widely available for determining least time paths in deterministic networks. In stochastic but time-invariant networks, least expected time paths can be determined by setting each random arc weight to its expected value and solving an equivalent deterministic problem. This paper addresses the problem of determining least expected time paths in stochastic, time-varying networks. Two procedures are presented. The first procedure determines the a priori least expected time paths from all origins to a single destination for each departure time in the peak period. The second procedure determines lower bounds on the expected times of these a priori least expected time paths. This procedure determines an exact solution for the problem where the driver is permitted to react to revealed travel times on traveled links en route, i.e., in a time-adaptive route choice framework. Modifications to each of these procedures for determining least expected cost (where cost is not necessarily travel time) paths and lower bounds on the expected costs of these paths are given. Extensive numerical tests are conducted to illustrate the algorithms' computational performance as well as the properties of the solution. [ABSTRACT FROM AUTHOR]

One of the many problems faced by rail transportation companies is to optimize the utilization of the available stock of locomotives and cars. In this paper, we describe a decomposition method for the simultaneous assignment of locomotives and cars in the context of passenger transportation. Given a list of train legs and a fleet composed of several types of equipment, the problem is to determine a set of minimum cost equipment cycles such that every leg is covered using appropriate equipment. Linking constraints, which appear when both locomotives and cars are treated simultaneously, lead to a large integer programming formulation. We propose an exact algorithm, based on the Benders decomposition approach, that exploits the separability of the problem. Computational experiments carried on a number of real-life instances indicate that the method finds optimal solutions within short computing times. It also outperforms other approaches based on Lagrangian relaxation or Dantzig-Wolfe decomposition, as well as a simplex-based branch-and-bound method. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a generalization of the directed rural postman problem including new features that can be encountered in practice when routes have to be operated on a street network: some turns are forbidden and other turns are allowed but with some penalties. This new problem is called the directed rural postman problem with turn penalties (DRPP-TP); we present some complexity results and three heuristics for the DRPP-TP: two of them are constructive, whereas the third one is an improvement heuristic. We also present a transformation of the DRPP-TP into an asymmetric traveling salesman problem (ATSP) that allows us to solve the problem exactly using an existing ATSP code. Computational results on a set of instances with up to 180 nodes and 666 arcs, are given. [ABSTRACT FROM AUTHOR]

The paper presents a feedback route guidance strategy for complex, meshed traffic networks. Essential components of the strategy are simple, decentralized control laws of the bang-bang, P, or PI types that may be designed based on trial-and-error. Simulation investigations demonstrate the efficiency of the proposed strategy for two example networks under several scenarios of demand and incident conditions. Feedback route guidance, though exclusively based on measurable instantaneous travel times (no predictions, no demand nor origin- destination information are provided), is shown to equalize experienced travel times along any couple of used alternative routes in the network, and to considerably reduce travel delays compared to the no-control case. [ABSTRACT FROM AUTHOR]

Consider a multiple booking class airline-seat inventory control problem that relates to either a single flight leg or to multiple flight legs. During the time before the flight, the airline may face the problems of (1) what are the suitable prices for the opened booking classes, and (2) when to close those opened booking classes. This work deals with these two problems by only using the pricing policy. In this paper, a dynamic pricing model is developed in which the demand for tickets is modeled as a discrete time stochastic process. An important result of this work is that the strategy for the ticket booking policy can be reduced to sets of critical decision periods, which eliminates the need for large amounts of data storage. [ABSTRACT FROM AUTHOR]

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the vehicle routing problem with time windows. It also develops an effective separation algorithm to find such inequalities. We next incorporate them as needed in the master problem of a Dantzig-Wolfe decomposition approach. In this enhanced optimization algorithm, the coupling constraints require that each customer be serviced. The subproblem is a shortest path problem with time window and capacity constraints. We apply branch and bound to obtain integer solutions. We first branch on the number of vehicles if this is fractional, and then on the flow variables. The algorithm has been implemented and tested on problems of up to 100 customers from the Solomon datasets. It has succeeded in solving to optimality several previously unsolved problems and a new 150-customer problem. In addition, the algorithm proved faster than algorithms previously considered in the literature. These computational results indicate the effectiveness of the valid inequalities we have developed. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a survey of recent optimization models for the most commonly studied rail transportation problems. For each group of problems, we propose a classification of models and describe their important characteristics by focusing on model structure and algorithmic aspects. The review mainly concentrates on routing and scheduling problems since they represent the most important portion of the planning activities performed by railways. Routing models surveyed concern the operating policies for freight transportation and railcar fleet management, whereas scheduling models address the dispatching of trains and the assignment of locomotives and cars. A brief discussion of analytical yard and line models is also presented. The emphasis is on recent contributions, but several older yet important works are also cited. [ABSTRACT FROM AUTHOR]

The dynamic traffic equilibrium problem has been a pivotal area of research in transportation for a few decades. The current state-of-the-art research in this area generally considers simultaneous departure time and route choice. In this paper, we theoretically prove that, in the simplest standard bottleneck model with a sufficient number of commuters, a dynamic user equilibrium (DUE) cannot be reached through a day-to-day evolution process of travelers' departure rate--a central idea behind the iterative dynamic traffic equilibrium algorithms prevalent in the literature. We carry out our exploration with the proportional swap system and then extend our analysis to other typical dynamic equilibrium algorithms such as the network tatonnement process, the simplex gravity flow dynamics, the projected dynamical system, and the evolutionary traffic dynamics. Our investigation indicates that any algorithm analogous to the five categories of systems must be cautious in terms of convergence when it is applied to solve the DUE problem with a departure time choice, and hence puts forward a general question: Are we really solving the DUE problem with a departure time choice? [ABSTRACT FROM AUTHOR]

This paper discusses an element of forecasting with disaggregate demand models that has received little attention so far; namely, the extent to which the accuracy of the final prediction depends on the accuracy of the calibration process. The paper introduces a numerical technique to evaluate approximate confidence intervals for the expected number of people using a transportation facility and approximate prediction intervals for the actual usage. It is shown that, unless the magnitude of the variance of the estimated parameters is considerably small,the predictions that result may be biased and the resulting confidence intervals, inaccurate. The degree of accuracy that can be obtained with different parameter variances is illustrated numerically for the binary probit model. [ABSTRACT FROM AUTHOR]

The paper describes a simple mathematical model of the behaviour of buses, on a relatively frequent service, after one has arrived at a stop at a time different from that scheduled. The model is similar to that used in some earlier papers on the pairing of buses, but derives a different objective function. Results are presented in terms of parameters relating to the scheduled headway (h) and the size of the initial deviation from it (hd), the usual time spent by a bus at a stop, and the ratio (k) of the passenger arrival rate to the boarding rate. A graphical method was employed to find P, the number of the stop at which the first two buses form a pair. For the typical values of parameters used the relationship P = 1/6dk was deduced which, although no generality is claimed, can be used to set operational limits so that the bunching of buses does not occur. Limitations of the model are discussed. [ABSTRACT FROM AUTHOR]

Given the multicommodity flow solution for a current transportation or communication network, planners often require some kind of heuristic measure of the effectiveness of new links which might potentially be added to the network. Exact procedures are usually prohibitive or expensive to use. This paper suggests the use of the dual variables associated with the new arcs. The paper also develops an efficient method for determining these dual variables from the current solution. [ABSTRACT FROM AUTHOR]

This paper contains a quantitative evaluation of probabilistic traffic assignment models and proposes an alternate formulation. First, the concept of stochastic-user-equilibration (S-U-E) is formalized as an extension of Wardrop's user-equilibration criterion. Then, the stochastic-network-loading (S-N-L) problem (a special case of S-U-E for networks with constant link costs) is analyzed in detail and an expression for the probability of route choice which is based on two general postulates of user behavior is derived. The paper also discusses the weaknesses of existing S-N-L techniques (with special attention paid to Dial's multipath method) and compares them to the suggested approach. The proposed model seems reasonable and does not exhibit the inherent weaknesses of the logit model when applied to sets of routes which overlap heavily. The discussion is supported by several numerical examples on small contrived networks. The paper concludes with the discussion of two techniques that can be used to approximate the link flows resulting from the proposed model in large networks. [ABSTRACT FROM AUTHOR]

This paper considers the problem of locating p facilities on a tree network in order to minimize the maximum distance from a point on the network to its nearest facility. Such a problem might arise, for a street network. The present paper identifies an underlying min-max theorem that governs such a p-center problem. More specifically, this p-center problem is shown to be equipment to the "dual" problem of locating p + 1 points on the network so as to maximize the minimum distance between pairs of points. [ABSTRACT FROM AUTHOR]

The article claims that a passenger in A will not use just any of a number of available routes. Because some routes might have a very long travel time to reach B, he may disregard them. In that way, the passenger operates a selection: among the set of all routes passing through A and B, he will select a subset so as to minimize his total expected travel time, which is made up of his expected waiting time plus his expected travel time. Once this subset is selected, the passenger will take the first vehicle serving one of the routes in this subset to arrive at A. The purpose of this paper is to present a probabilistic framework for the study of this problem, which takes into account the frequencies and the speeds of each competing A. In this paper the problem of the determination of the expected travel time is regarded as an optimization problem. The approach used allows the consideration of any distribution function for first arrival time of a vehicle on a route. In practice, the cases of uniform and exponential distributions are of much interest: they are studied in greater detail.

In this paper models will be developed for estimating the number of overtake conflicts and crossing conflicts expected to occur within an air traffic control sector in a specified time period. In addition, the distribution of the number of each type of conflict is considered. These three topics are treated together because the ultimate application of these results is for estimating controller workload, and for that application the number of overtake conflicts and the number of crossing conflicts are added together to obtain an estimate of the total expected conflict workload. In addition, the distribution of workload is of critical concern in the application of the methods developed in this paper. Therefore, the distribution of the number of conflicts is also treated. The above applications are described in detail in another paper by the author. The purpose of this paper is to demonstrate the application of previous findings of other researches to the development of two analytical models for estimating the expected number of times controllers perceive the separations.

Tall buildings result largely from the scarcity of land in the centers of towns. Provision of the vertical transportation involves a loss of some useful floor ares in these buildings. The main objective of the research reported in this paper is to compare different design arrangements of elevator systems in terms of the floor area, they consume, and to point out the implications for the limits to height of tall buildings. The research approach is to formulate models of several types of elevator systems, in which the area of elevator shafts and the useful area (on various floors and in total) are expressed as functions of building' s height, inclusive of such parameters as: the base area of a building, duration of the peak period, density of a building's population, the cruise speed of elevators, etc. Solutions are found for the optimal height of buildings, when the objective is to maximize the total useful floor area. This part of the paper presents two simple models: the first is of on all-express system where each elevator serves only one floor, while the second is the familiar system where each elevator serves all floors. a building's population, the cruise speed of elevators, etc. Solutions are found for the optimal height of buildings, when the objective is to maximize the total useful floor area. [ABSTRACT FROM AUTHOR]

This paper derives six objectives for routing hazardous material by viewing shipments as a sequence of independent Bernoulli trials. An example that compares these objectives is presented. Suitable approximations toward the use of these objectives in an optimization framework are provided. The paper also discusses the objectives from the viewpoint of their use to make actual hazardous material routing decisions. [ABSTRACT FROM AUTHOR]

To achieve high productivity in manufacturing plants and warehouses, an orderly and flexible flow of materials is essential. The interaction between the manufacturing plants and warehouses and issues related to distribution of multiple commodities to customers from warehouses represents a crucial step toward an integrated and systematic facilities' design. In this paper we develop a mixed integer programming model for the plant and warehouse location problem where the objective is to minimize the total transportation and distribution costs and the fixed costs for opening and operating plants and warehouses. We employ Lagrangian relaxation to the model, and also present a heuristic to produce an effective feasible solution for the problem. This problem has resulted from a study conducted by the authors for a large company manufacturing health-care products. The paper reports on the development of a model structure that can be used to predict the performance of the company. [ABSTRACT FROM AUTHOR]

Dynamic models of the behavior of automobile drivers in choosing routes through urban transportation networks are required for the design and operation of intelligent transportation systems generally, and traveler information systems in particular. In this paper, drivers' route choice behavior based on current, or instantaneous, information on network conditions is described using an optimal control theory formulation. The time-dependent origin-destination vehicle trip pattern is assumed to be known. The instantaneous dynamic user-optimal route choice problem is to allocate vehicle flows to the current minimal-cost routes, defined as the routes that minimize the route travel cost between each decision node (any node on the route including the origin) and the destination node based on the currently prevailing travel times. The continuous time formulation of the problem is transformed into a discrete time nonlinear programming (NLP) formulation. Each of a sequence of NLPs is then solved by an algorithm based on the Frank-Wolfe technique. In this sequence, approximate link travel times are updated iteratively in order to represent flow propagation over routes. Computational results from applying the algorithm to two test networks conclude the paper. [ABSTRACT FROM AUTHOR]

This paper examines a routing problem in which vehicles from a single depot cover a large area, where randomly located customers request pickup and delivery service. The paper assumes that each vehicle must serve its deliveries before it collects any pickups, that vehicles do not need to return to the depot between delivery and collection, and that each vehicle can serve at most C deliveries, but an unlimited number of pickups. This paper does not propose a detailed algorithm; rather, it discusses the pros and cons of various broad routing schemes, and quantifies their performance with simple distance formulas. The broad schemes describe implementable solutions, which can in turn be used to initialize fine-tuning algorithms. The choice of a routing scheme only depends on two dimensionless parameters: the size of the service area, relative to the area covered by one delivery route; and the ratio of the number of pickup customers to the number of deliveries. The clusters of deliveries and pickups served by a vehicle should often be radically different; unlike deliveries, pickups should be clustered in zones that have been elongated as much as possible, reaching all the way to the depot if it is internally located. It also appears that in a majority of cases not much is lost by routing for deliveries first (ignoring pickups) and for pickups second. Instances where they should be considered jointly are identified. [ABSTRACT FROM AUTHOR]

A pavement deterioration model predicts the performance of a pavement over time as a function of traffic, pavement characteristics and environmental factors. The most important performance characteristics of a pavement are its ability to bear traffic loads and its ability to provide a smooth ride. However, there is no unambiguous approach to directly measure these performance characteristics. Therefore, we consider pavement performance to be unobservable. The problem of designing pavement deterioration models is the problem of defining the above unobservable characteristics in terms of what is observed, i.e., in terms of measured extents and severities of different damage components. The methodology presented in this paper describes a statistical technique to estimate latent pavement performance from observed pavement damage. No constraints are placed on the number or type of measurements required, so the methodology is flexible enough to include different measurement techniques and data collection strategies. The estimation procedure simultaneously fits a deterioration model and a performance index calibration model to data, thereby producing much better fits to data than traditional deterioration models. The methodology presented in this paper will be useful for deriving more realistic predictive models of pavement deterioration and for defining better data collection strategies. [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]

The study of stochastic networks of queues in transportation has been confined to the use of highly simplified analytical models or the development of large, computationally expensive Monte Carlo simulations. We introduce a discrete-time approach for simulating stochastic, transient networks of bulk queues that often arise in consolidation networks. This paper presents the state variables and equations required to model the problem, and introduces a set of approximations to produce a computationally tractable algorithm. A companion paper describes the results of extensive numerical experiments which test the accuracy of the approximations and the overall efficiency of the procedure. [ABSTRACT FROM AUTHOR]

The objective of the ‘transportation problem’ is to minimize the cost of satisfying customer product requirements without exceeding supplier capacities. This paper examines the transportation problem with the purpose of ascribing graphical meaning to the solution. The paper summarizes prior results as well as provides new results relative to supplier lattice structures and nonlinear costs. [ABSTRACT FROM AUTHOR]