On some traffic equilibrium theory paradoxes

We consider the asymmetric equilibrium problem with fixed demands in a transportation network where the travel cost on each link may depend on the flow on this as well as other links of the network and we study how the travellers' cost is affected by changes in the travel demand or addition of new routes. Assuming that the travel cost functions are strongly monotone, we derive formulas which express, under certain conditions, how a change in travel demand associated with a particular origin-destination (O / D) pair will affect the travelers' cost for any O / D pair. We then use these formulas to show that an increase in the travel demand associated with a particular O / D pair (all other remaining fixed) always results in an increase in the travelers' cost on that O / D pair, however, the travelers' cost on other O / D pairs may decrease. We then derive formulas yielding, under certain conditions, the change in travelers' cost on every O / D pair induced by the addition of a new path. These can be used to determine, whether Braess' paradox occurs in the network. We then show that when a new path is added, the travelers' cost associated with the particular O / D pair joined by this path will decrease (hence Braess' paradox does not occur) if a test matrix is positive semidefinite.     

Queue-dependent vehicle dispatching with options and optimal fleet size

A queue-dependent vehicle dispatching rule, with options to use special vehicles (rented, reserve, shared etc.) for relieving long waiting lines, is considered. The transportation system under consideration has one source terminal and a fleet of N regular vehicles. Passengers are assumed to arrive individually at the source terminal according to a Poisson process. An efficient recursive algorithm is derived to analyse the performance of the system. An average cost criterion is used to determine the firm's fleet size and dispatching strategy for a simpler system. This is a variant of a “Random vehicle dispatching with options” rule proposed by Zuckerman and Tapiero (1980).     

Genetic algorithms in bus network optimization

This paper focuses on a new method to compute fitness function (ff) values in genetic algorithms for bus network optimization. In the proposed methodology, a genetic algorithm is used to generate iteratively new populations (sets of bus networks). Each member of the population is evaluated by computing a number of performance indicators obtained by the analysis of the assignment of the O/D demand associated to the considered networks. Thus, ff values are computed by means of a multicriteria analysis executed on the performance indicators so found. The goal is to design a heuristic that allows to achieve the best bus network satisfying both the demand and the offer of transport.     

Finding the k reliable shortest paths under travel time uncertainty

This paper investigates the problem of finding the K reliable shortest paths (KRSP) in stochastic networks under travel time uncertainty. The KRSP problem extends the classical K loopless shortest paths problem to the stochastic networks by explicitly considering travel time reliability. In this study, a deviation path approach is established for finding K α-reliable paths in stochastic networks. A deviation path algorithm is proposed to exactly solve the KRSP problem in large-scale networks. The A^* technique is introduced to further improve the KRSP finding performance. A case study using real traffic information is performed to validate the proposed algorithm. The results indicate that the proposed algorithm can determine KRSP under various travel time reliability values within reasonable computational times. The introduced A^* technique can significantly improve KRSP finding performance.     

A distributed origin–destination demand estimation approach for real-time traffic network management

Abstract

This paper describes a distributed recursive heuristic approach for the origin–destination demand estimation problem for real-time traffic network management applications. The distributed nature of the heuristic enables its parallelization and hence reduces significantly its processing time. Furthermore, the heuristic reduces dependency on historical data that are typically used to map the observed link flows to their corresponding origin–destination pairs. In addition, the heuristic allows the incorporation of any available partial information on the demand distribution in the study area to improve the overall estimation accuracy. The heuristic is implemented following a hierarchal multi-threading mechanism. Dividing the study area into a set of subareas, the demand of every two adjacent subareas is merged in a separate thread. The merging operations continue until the demand for the entire study area is estimated. Experiments are conducted to examine the performance of the heuristic using hypothetical and real networks. The obtained results illustrate that the heuristic can achieve reasonable demand estimation accuracy while maintaining superiority in terms of processing time.     

A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.     

A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows

A heuristic algorithm is described for a time-constrained version of the advance-request, multi-vehicle, many-to-many Dial-A-Ride Problem (DARP). The time constraints consist of upper bounds on: (1) the amount of time by which the pick-up or delivery of a customer can deviate from the desired pick-up or delivery time; (2) the time that a customer can spend riding in a vehicle. The algorithm uses a sequential insertion procedure to assign customers to vehicles and to determine a time schedule of pick-ups and deliveries for each vehicle. A flexible objective function balances the cost of providing service with the customers' preferences for pick-up and delivery times close to those requested, and for short ride times. Computational experience with the algorithm is described, including a run with a real database of 2600 customers and some 20 simultaneously active vehicles. The scenario for the application of the algorithm is also discussed in detail.     

On the convergence of iterative methods for the distribution balancing problem

A general distribution balancing problem, specified by the given outflows and inflows and the factorial form of its solution, is formulated. Solution uniqueness and boundedness is discussed—primarily in graph theoretical terms. An entropy maximisation problem, subject to general linear constraints, is transformed into an unconstrained optimisation problem by application of standard duality theory, and a relevant general convergence theorem for iterative solution methods is given. The optimum solution in a special case is identified with the flow solution. When expressed in flow variables, the dual objective has a unique and bounded optimum solution and is an appropriate unifying concept for measuring the rate of convergence of different solution methods. By regarding the balancing procedure as an iterative optimisation method, a new and simple proof of its convergence is given, together with some asymptotic results, which are also compared with those of Newton's method. It is pointed out that there are two different forms of Newton's method, according to the choice of variables—untransformed or transformed— in the original distribution balancing problem. When Newton's method is applied to the whole system of equations simultaneously, the trajectory of iterates is observed to depend on this variable choice. For the transformed variables it is noticed that the convergence with the balancing procedure is quicker than with Newton's method applied to the outflow- and inflow- equations, alternately. To guarantee global convergence with Newton's method and to increase the rate a supplementary linear search routine is recommended.     

Multi-fleet ferry service network design with passenger preferences for differential services

This paper investigates a multi-fleet ferry routing and scheduling problem that takes into account ferry services with different operation characteristics and passengers with different preferred arrival time windows. The logit model is used to represent passengers’ service choices. The full problem is formulated as a mixed integer nonlinear programming problem and solved with a heuristic procedure that first fixes the demand and then decomposes the resultant model by ferry services. At each iteration of the algorithm, the demand is updated and the relaxed problem is re-solved. Numerical results for the case of ferry service network design in Hong Kong are provided to illustrate the properties of the model and the performance of the heuristic.     

Just-in-time delivery for green fleets: A feedback control approach

With increasing attention being paid to greenhouse gas (GHG) emissions, the transportation industry has become an important focus of approaches to reduce GHG emissions, especially carbon dioxide equivalent (CO₂e) emissions. In this competitive industry, of course, any new emissions reduction technique must be economically attractive and contribute to good operational performance. In this paper, a continuous-variable feedback control algorithm called GEET (Greening via Energy and Emissions in Transportation) is developed; customer deliveries are assigned to a fleet of vehicles with the objective function of Just-in-Time (JIT) delivery and fuel performance metrics akin to the vehicle routing problem with soft time windows (VRPSTW). GEET simultaneously determines vehicle routing and sets cruising speeds that can be either fixed for the entire trip or varied dynamically based on anticipated performance. Dynamic models for controlling vehicle cruising speed and departure times are proposed, and the impact of cruising speed on JIT performance and fuel performance are evaluated. Allowing GEET to vary cruising speed is found to produce an average of 12.0–16.0% better performance in fuel cost, and −36.0% to +16.0% discrepancy in the overall transportation cost as compared to the Adaptive Large Neighborhood Search (ALNS) heuristic for a set of benchmark problems. GEET offers the advantage of extremely fast computational times, which is a substantial strength, especially in a dynamic transportation environment.     

An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows

The solution of routing problems with soft time windows has valuable practical applications. Soft time window solutions are needed when: (a) the number of routes needed for hard time windows exceeds the number of available vehicles, (b) a study of cost-service tradeoffs is required, or (c) the dispatcher has qualitative information regarding the relative importance of hard time-window constraints across customers. This paper proposes a new iterative route construction and improvement algorithm to solve vehicle routing problems with soft time windows. Due to its modular and hierarchical design, the solution algorithm is intuitive and able to accommodate general cost and penalty functions. Experimental results indicate that the average run time performance is of order O(n²). The solution quality and computational time of the new algorithm has been compared against existing results on benchmark problems. The presented algorithm has improved thirty benchmark problem solutions for the vehicle routing problems with soft time windows.     

A new offline optimization approach for designing a fuel cell hybrid bus

In this study a hydrogen powered fuel cell hybrid bus is optimized in terms of the powertrain components and in terms of the energy management strategy. Firstly the vehicle is optimized aiming to minimize the cost of its powertrain components, in an official driving cycle. The optimization variables in powertrain component design are different models and sizes of fuel cells, of electric motors and controllers, and batteries. After the component design, an energy management strategy (EMS) optimization is performed in the official driving cycle and in two real measured driving cycles, aiming to minimize the fuel consumption. The EMS optimization is based on the control of the battery’s state-of-charge. The real driving cycles are representative of bus driving in urban routes within Lisbon and Oporto Portuguese cities. A real-coded genetic algorithm is developed to perform the optimization, and linked with the vehicle simulation software ADVISOR. The trade-off between cost increase and fuel consumption reduction is discussed in the lifetime of the designed bus and compared to a conventional diesel bus. Although the cost of the optimized hybrid powertrain (62,230 €) achieves 9 times the cost of a conventional diesel bus, the improved efficiency of such powertrain achieved 36% and 34% of lower energy consumption for the real driving cycles, OportoDC and LisbonDC, which can originate savings of around 0.43 €/km and 0.37 €/km respectively. The optimization methodology presented in this work, aside being an offline method, demonstrated great improvements in performance and energy consumption in real driving cycles, and can be a great advantage in the design of a hybrid vehicle.     

Behavior of the cell transmission model and effectiveness of ramp metering

The paper characterizes the behavior of the cell transmission model of a freeway, divided into N sections or cells, each with one on-ramp and one off-ramp. The state of the dynamical system is the N-dimensional vector n of vehicle densities in the N sections. A feasible stationary demand pattern induces a unique equilibrium flow in each section. However, there is an infinite set—in fact a continuum—of equilibrium states, including a unique uncongested equilibrium n^u in which free flow speed prevails in all sections, and a unique most congested equilibrium n^con. In every other equilibrium n^e one or more sections are congested, and n^u  n^e  n^con. Every equilibrium is stable and every trajectory converges to some equilibrium state.Two implications for ramp metering are explored. First, if the demand exceeds capacity and the ramps are not metered, every trajectory converges to the most congested equilibrium. Moreover, there is a ramp metering strategy that increases discharge flows and reduces total travel time compared with the no-metering strategy. Second, even when the demand is feasible but the freeway is initially congested, there is a ramp metering strategy that moves the system to the uncongested equilibrium and reduces total travel time. The two conclusions show that congestion invariably indicates wastefulness of freeway resources that ramp metering can eliminate.     

Optimal shipment decisions for an airfreight forwarder: Formulation and solution methods

We study the freight forwarder’s shipment planning problem in an airfreight forwarding network where a set of cargo shipments have to be transported to given destinations. We provide mixed integer programming formulations that use piecewise-linear cargo rates and account for volume and weight constraints, flight departure/arrival times, as well as shipment-ready times.After exploring the solution of such models using CPLEX, we devise two solution methodologies to handle large problem sizes. The first is based on Lagrangian relaxation, where the problems decompose into a set of knapsack problems and a set of network flow problems. The second is a local branching heuristic that combines branching ideas and local search. The two approaches show promising results in providing good quality heuristic solutions within reasonable computational times, for difficult and large shipment consolidation problems.     

Traffic assignment in a two-dimensional continuous representation of a traffic network with flow-dependent speeds

The work deals with the assignment of traffic to a two-dimensional continuous representation of a traffic network. An important aspect of the treatment is that the reciprocal of the speed on each road in the network is at all times a linear function of the flow on that road. This speed-flow relationship is generalized to two-dimensional space using travel intensities and taking account of road densities, so that there is direct dependence of speeds upon flows at all points regardless of their location. There is also dependence of flows upon speeds at all points because Wardrop's first assignment principle is adopted. That is, for a given O-D pair, journey times on all routes actually used are identical, and less than journey times on all other possible routes. This results in the identification for each O-D pair of an “assignment zone”, an area within which all trips between that O-D pair are made, and beyond which no such trips are made. For a single O-D pair the assignment zone is identified by ?_m, the maximum angular divergence of a path from the straight line between O and D. Paths are then assumed to be bilinear so that for a single O-D pair the assignment zone is a parallelogram. Journey times, speeds, lateral displacement and other related quantities are obtained as functions of the flow Q between O and D. The work is extended to three O-D pairs located at the extremities of an equilateral triangle and four O-D pairs located at the corners of a square. At low flows these two configurations are trivial extensions of the single O-D pair problem because assignment zones do not overlap. At higher flows account is taken of this tendency to overlapping, so that although they do not overlap they do touch, becoming kite-shaped. Origins and destinations are assumed to be at the periphery of small circles of arbitrary radius. The work is inelegant to the extent that it involves a numerical integration but it is possible that this might eventually be circumvented.     

Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm

This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time-dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be NP-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, we propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times.     

Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times

This study investigates the important problem of determining a reliable path in a stochastic network with correlated link travel times. First, the distribution of path travel time is quantified by using trip records from GPS probe vehicles. Second, the spatial correlation of link travel time is explicitly considered by using a correlation coefficient matrix, which is incorporated into the α-reliable path problem by Cholesky decomposition. Third, the Lagrangian relaxation based framework is used to handle the α-reliable path problem, by which the intractable problem with a non-linear and non-additive structure can be decomposed into several easy-to-solve problems. Finally, the path-finding performance of this approach is tested on a real-world network. The results show that 15 iterations of calculation can yield a small relative gap between upper and lower bounds of the optimal solution and the average running time is about 5 s for most OD settings. The applicability of α-reliable path finding is validated by a case study.     

A statistical approach to the traveling salesman problem

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

Bus garage location planning with dynamic vehicle assignments: A methodology

A simultaneous vehicle scheduling and bus garage location and sizing optimization is described. The methodology's importance lies in its treating garage locations and sizes and vehicle schedules as dynamic. In other bus garage planning methodologies, vehicle schedules are assumed fixed.     

Equilibrium holdings distributions in durable asset markets

The stock of durable goods can be represented by its holdings distribution, defined as the joint distribution of age and physical condition of the population of durable goods. This paper derives the holdings distribution which arises under stationary conditions when durable goods deteriorate according to a Markov process. We show that given the scrappage and utilization decisions of consumers, the holdings distribution F(x) is an equilibrium distribution of an associated regenerative Markov process. Using a basic result from the theory of regenerative stochastic processes, we characterize F(x) as the ratio of the expected number of periods the durable's condition is better than x to the expected lifetime of the asset. Using data from the 1977 National Transportation Survey we illustrate these results by estimating a simple two-parameter model of automobile deterioration and comparing the implied distribution of automobile holdings to the actual distribution.