Search

Insertion heuristics have proven to be popular methods for solving a variety of vehicle routing and scheduling problems. In this paper, we focus on the impact of incorporating complicating constraints on the efficiency of insertion heuristics. The basic insertion heuristic for the standard vehicle routing problem has a time complexity of O(n³). However, straightforward implementations of handling complicating constraints lead to an undesirable time complexity of O(n4. We demonstrate that with careful implementation it is possible, in most cases, to maintain the O⊃3 complexity or, in a few cases, increase the time complexity to O(n⊃3 log n). The complicating constraints we consider in this paper are time windows, shift time limits, variable delivery quantities, fixed and variable delivery times, and multiple routes per vehicle. Little attention has been given to some of these complexities (with time windows being the notable exception), which are common in practice and have a significant impact on the feasibility of a schedule as well as the efficiency of insertion heuristics. [ABSTRACT FROM AUTHOR]

This paper discusses the uniqueness of user equilibrium in transportation networks with heterogeneous commuters. Daganzo (1983) proved the uniqueness of (stochastic) user equilibrium when commuters have heterogeneous tastes over possible paths, but identical disutility functions from time costs. We first show, by example, that his result may not apply in general networks if disutility functions are allowed to differ. However, for "simple" transportation networks, we show that user equilibrium is always unique and weakly Pareto efficient (cf. the Braess example) for a general class of utility functions. We investigate whether this result applies to more general networks. We also show that user equilibrium is unique in a dynamic bottleneck model with a simple network. We discuss an interesting relationship between the following two problems: the existence of user equilibrium in a finite model and the uniqueness of user equilibrium in a continuum model. In the appendix, we also provide a proof of a slightly generalized version of Daganzo's theorem. [ABSTRACT FROM AUTHOR]

The queueing-theoretical model for stationary traffic flow developed in a former paper is extended and modified for nonstationary flow. In particular it is shown how speed-flow-density relationships under nonstationary conditions may deviate from those obtained for stationary conditions.It is shown how the wide scatter which is often observed with empirical speed-flow-density data can be explained by nonstationarity. Furthermore, hysteresis loops,which may show up in speed-flow-density relationships, are interpreted by means of nonstationarity. [ABSTRACT FROM AUTHOR]

Recently, Daganzo introduced the cell transmission model--a simple approach for modeling highway traffic flow consistent with the hydrodynamic model. In this paper, we use the cell transmission model to formulate the single destination System Optimum Dynamic Traffic Assignment (SO DTA) problem as a Linear Program (LP). We demonstrate that the model can obtain insights into the DTA problem, and we address various related issues, such as the concept of marginal travel time in a dynamic network and system optimum necessary and sufficient conditions. The model is limited to one destination and, although it can account for traffic realities as they are captured by the cell transmission model, it is not presented as an operational model for actual applications. The main objective of the paper is to demonstrate that the DTA problem can be modeled as an LP, which allows the vast existing literature on LP to be used to better understand and compute DTA. A numerical example illustrates the simplicity and applicability of the proposed approach. [ABSTRACT FROM AUTHOR]

Bounds and approximate formulae are developed for the average optimum distance of the transportation linear programming (TLP) problem with homogeneously, but randomly distributed points and demands in a region of arbitrary shape. It is shown that if the region size grows with a fixed density of points, then the cost per item is bounded from above in 3 + dimensions (3 +-D), but not in 1-D and 2-D. Lower bounds are also developed, based on a mild monotonicity conjecture. Computer simulations confirm the conjecture and yield approximate formulae. These formulae turn out to have the same functional form as the upper bounds. Curiously, the monotonicity conjecture implies that the cost per item does not depend on zone shape asymptotically, as problem size increases,for 2+-D problems but it does in 1-D. Therefore, the 2-D case can be viewed as a transition case that shares some of the properties of 1-D (unbounded cost) and some of the properties of 3-D (shape independence). The results are then extended to more general network models with subadditive link costs. It is found that if the cost functions have economies of scale, then the cost per item is bounded in 2-D. This explains the prevalence of the "last mile" effect in many logistics applications. The paper also discusses how the results were used to estimate costs under uncertainty for a vehicle repositioning problem. [ABSTRACT FROM AUTHOR]

This paper addresses the development of effective heuristics for solving the vehicle routing and scheduling problem with time window constraints. Both tour construction and local search tour improvement heuristics are developed. A major premise of the paper is that embedding global tour improvement procedures within the tour construction process can lead to improved solutions. Computational results are reported on test problems from the literature as well as real world applications. The hybrid construction / improvement heuristic is more effective in reducing vehicle fleet size requirements than previously reported heuristics. [ABSTRACT FROM AUTHOR]

The paper develops a dynamic model of peak period traffic congestion that considers a limited number of bottlenecks. The model predicts the temporal distribution of traffic volumes with an elastic demand model. In response to changes in the traffic conditions travelers can switch to a different mode, divert to an alternate route, or shift the trip forward or backward in time to avoid a long delay. A simple example would be the case of two parallel routes with travelers jointly selecting route and departure time. The choice of route and mode are dependent on travel times and travel costs. The choice of departure time is based on the trade-off between travel time and schedule delay which is the difference between the actual and the desired arrival times. The delays at the bottlenecks are modeled with a deterministic queueing model that determines waiting time as a function of the length of the queue at the time of arrival at the bottleneck. The day to day adjustment of the distribution of traffic is derived from a dynamic Markovian model The model is used to perform simulation experiments. The results demonstrate the response of the traffic conditions at the bottlenecks to a change in the system. The model is used to analyze the impacts of alternative pricing policies and preferential treatment of high occupancy vehicles. [ABSTRACT FROM AUTHOR]

This paper attempts to provide some insight into the structure of' a large class of fleet scheduling problems. Scheduling under fixed due date constraints is shown to be easily solved using a new formulation of the problem. Scheduling under flexible due date constraints is shown to be inherently complex, and strong evidence is given for asserting that no efficient (polynomial bounded) algorithm, exists for solving this problem exactly. A fast heuristic approach is described which has worked well in some school bus scheduling applications. [ABSTRACT FROM AUTHOR]

In this paper, M/G/CIC state dependent queueing models are proposed for modeling and analyzing vehicular traffic flows. Congestion aspects of traffic flow are represented by introducing state dependent service rates as a function of number of vehicles on each road link. Analytical models for unidirectional and multisource flows are presented. Finally, queueing models to analytically determine the optimal capacity and performance measures of the road links are incorporated into a series of software programs available from the authors. [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]

Motorists going through a bottleneck during the morning rush hour have to time their departure times to ensure they arrive to work at a reasonable time. Traffic and congestion levels at the bottleneck depend on the motorists' work schedule and the disutility of unpunctuality. This paper shows that, under certain conditions, there is only one equilibrium order of arrivals; an order under which motorists do not have an incentive to jockey for position in the queue. [ABSTRACT FROM AUTHOR]

The paper gives conditions which guarantee the existence of an equilibrium arrival pattern at a single bottleneck. In the model, the times at which a driver wishes to leave the bottleneck depend on the driver. The equilibrium queue length in this model always has a continuous time derivative everywhere. However, the slope of the equilibrium cumulative arrival distribution is discontinuous at the beginning and end of congestion. [ABSTRACT FROM AUTHOR]

An important strategic phase in the planning process of a railway operator is the development of a line plan, i.e., a set of routes (paths) in a network of tracks, operated at a given hourly frequency. We consider a model formulation of the line-planning problem where total operating costs are to be minimized. This model is solved with a branch-and-cut approach, for which we develop a variety of valid inequalities and reduction methods. A computational study of five real-life instances based on examples from Netherlands Railways (NS) is included. [ABSTRACT FROM AUTHOR]

Under relatively general assumptions a unique deterministic departure-time user equilibrium with a finite departure rate exists in the bottleneck model with drivers who differ in their unit costs of travel time, preferred times of arrival, and schedule delay cost functions. Existence requires that schedule delay cost functions be upper semicontinuous with respect to arrival time, and that schedule delay costs decline at a rate smaller than the unit cost of travel time. Uniqueness requires, more restrictively, that schedule delay cost functions be continuous. Several properties of equilibrium trip cost functions are derived for n groups of users with Ni in group i. The trip cost of a user in group i is a nondecreasing function of each Nj, but typically rises more quickly with respect to N i than Nj, j ≠i. Thus, users experience lower trip costs when they travel with users unlike themselves than with an equal number of users like themselves. [ABSTRACT FROM AUTHOR]

This study developed a dynamic traffic-control formulation that considers the entire Fundamental Diagram. This incorporation of the Fundamental Diagram is especially important for modeling oversaturated traffic. For this purpose, traffic is modeled after the cell-transmission model (CTM), which is a convergent numerical approximation to the hydrodynamic model. We transformed CTM to a set of mixed-integer constraints and subsequently cast the dynamic signal-control problem to a mixed-integer linear program. As a dynamic platform, the formulation is flexible in dealing with dynamic timing plans and traffic patterns. It can derive dynamic as weil as fixed timing plans and address preexisting traffic conditions and time-dependent demand patterns. This study produced results to show the benefit of dynamic timing plans and demonstrated that some of the existing practice on signal coordination could be further improved. [ABSTRACT FROM AUTHOR]