Search

This paper addresses a travel time reliable signal control problem. Travel time distributional estimates are obtained from a stochastic microscopic traffic simulator. The estimates are embedded within a simulation-based optimization algorithm. Analytical approximations of the simulated metrics are combined with the simulated data in order to enhance the computational efficiency of the algorithm. The signal control problems are formulated based on the expectation and the standard deviation of travel time metrics. The proposed approach goes beyond the traditional use of first-order simulated information, it addresses a problem that embeds higher-order distributional information. It is used to solve a large-scale signal control problem. The approach addresses these challenging simulation-based optimization problems in a computationally efficient manner. Its performance is compared to that of a traditional simulation-based optimization approach. The proposed method systematically outperforms the traditional approach. Such an approach can be used to inform the design and operations of transportation systems by, for instance, addressing reliable and/or robust formulations of traditional transportation problems. The online appendix is available at https://doi.org/10.1287/trsc.2017.0812. [ABSTRACT FROM AUTHOR]

The capacitated LRP (CLRP) jointly takes decisions on the location of capacitated depots and the routing of capacitated vehicles to serve a set of customers with known demands from the opened depots. In city logistics, the CLRP is used for the planning of single-echelon distribution networks. In this application context, large-scale CLRP instances with a high number of potential depot locations (representing concrete candidates for running urban depots) and a high number of customers (as a result of densely populated urban areas) are particularly relevant. We introduce a tree-based search algorithm (TBSA) that explores the space of depot configurations in a tree-like fashion using a customized first improvement strategy. In the routing phase, the multi-depot vehicle-routing problem defined by the depot configuration is solved with a granular tabu search that uses a large composite neighborhood described by 14 operators. In numerical studies, we find that using the large composite neighborhood has a positive impact on the effectivity, efficiency, and robustness of TBSA. We show that the trade-off between run time and solution quality of TBSA can be controlled by the number of total iterations and the strength of the sparsification in the granular search, and we investigate a fast, a basic, and a quality-oriented variant of TBSA. On the commonly used small-to-medium–sized CLRP benchmark sets from the literature, the fast version is able to dominate all previously published heuristic solution methods, that is, it achieves better solution quality within shorter run times. The basic and quality-oriented variants provide outstanding solution quality within reasonable run times; on average, both variants achieve negative gaps to the previous best known solutions. Thus, on the considered benchmark sets, the three variants together form the Pareto frontier of heuristic solution methods for the CLRP. Moreover, TBSA matches or improves the large majority of previous best known solutions in these instances. Finally, TBSA is able to solve newly generated, large-scale instances with up to 600 customers and 30 depots with reasonable run times and convincing scaling behavior and robustness. Additional experiments on open LRP benchmarks confirm the performance of TBSA. Data are available at https://doi.org/10.1287/trsc.2017.0770. [ABSTRACT FROM AUTHOR]

We consider an integrated supply pricing and biomass logistics network design problem in which yield rates are uncertain. The base supply amount is modeled via a farmers' decision model that estimates the amount of land dedicated to biomass production under a given biomass wholesale price. We develop a two-stage stochastic integer program for integrated design of a network as well as biomass pricing decisions under yield uncertainty. To efficiently solve our model, we suggest a Benders decomposition–based algorithm in which the Benders cuts, one for each scenario, are aggregated by utilizing a scheme that takes into account yield rates as well as the geographical nature of the underlying problem. With further strengthening of the cuts, we present a significantly improved approach for solving relatively large instances and illustrate its performance via a computational study. We further present an extensive case study in Texas using realistic data to test our model's capabilities and to demonstrate its effectiveness in capturing the relationships between total cost, biomass wholesale price, network structure, and various input parameters. Finally, we examine the relationship between farmers' decision model parameters, which dictate the risk profile of farmers, and the expected total system cost, as well as the biomass wholesale price. [ABSTRACT FROM AUTHOR]

We extend the hazardous-materials (hazmat) network design problem to account for the time-dependent road closure as a policy tool to reduce hazmat transport risk by altering carriers' departure times and route choices.We formulate the time-dependent network design problem using an alternative-based model with each alternative representing a combined path and departure-time choice.We also present an extended model that can not only account for consecutive time-based road closure policies but also allow stopping at the intermediate nodes of the network in the routing/scheduling decisions of the carriers. Heuristic algorithms based on column generation and label setting are presented. To illustrate the advantages that can be gained through the use of our methodology, we present results from numerical experiments based on a transportation network from Buffalo, New York. To investigate the impact of the extensions, we consider three versions of the problem by gradually refining the model. We show that under consideration of extensions, the design policies are more applicable and effective. [ABSTRACT FROM AUTHOR]

We introduce an interesting variant of the well-known Chinese postman problem (CPP). While in the CPP the cost of traversing an edge is a constant (equal to its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment it is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two mathematical programming formulations, and propose two metaheuristics for its solution. Extensive computational experiments reveal the extraordinary difficulty of this problem. [ABSTRACT FROM AUTHOR]

This paper describes an exact algorithm for the fixed charge transportation problem based on a new integer programming formulation that involves two sets of variables representing flow patterns from sources to sinks and from sinks to sources. The formulation states to select a pattern for each source and each sink and to match the corresponding flows. The linear relaxation of this new formulation is enforced by adding a pseudo-polynomial number of equations that are shown to contain, as special cases, different valid inequalities recently proposed for the problem. The resulting lower bound dominates the lower bounds proposed in the literature. Such a lower bound is embedded into an exact branch-and-cut-and-price algorithm. Computational results on benchmark instances show that the proposed algorithm is several times faster than the state-of-the-art exact methods and could solve all open instances. New harder instances with up to 120 sources and 120 sinks were solved to optimality. [ABSTRACT FROM AUTHOR]

This article studies a capacitated fixed-charge multiperiod location–transportation problem in which, while the location and capacity of each facility must be determined immediately, the determination of the final production and distribution of products can be delayed until actual orders are received in each period. In contexts where little is known about future demand, robust optimization, namely using a budgeted uncertainty set, becomes a natural method for identifying meaningful decisions. Unfortunately, it is well known that these types of multiperiod robust decision problems are computationally intractable. To overcome this difficulty, we propose a set of tractable conservative approximations for the problem that each exploit to a different extent the idea of reducing the flexibility of the delayed decisions. While all of these approximation models outperform previous approximation models that have been proposed for this problem, each also has the potential to reach a different level of compromise between efficiency of resolution and quality of the solution. A row generation algorithm is also presented to address problem instances of realistic size. We also demonstrate that full flexibility is often unnecessary to reach nearly, or even exact, optimal robust locations and capacities for the facilities. Finally, we illustrate our findings with an extensive numerical study where we evaluate the effect of the amount of uncertainty on the performance and structure of each approximate solution that can be obtain d. [ABSTRACT FROM AUTHOR]

The timetabling subproblem of bus transit network planning determines the departure times for all trips of the lines along the entire day. Most of the public transport networks consider planning periods identical for all lines. In this study we drop this strong assumption by introducing specific periods for each line, which is more realistic. Thus, we propose the multiperiod synchronization bus timetabling (MSBT) problem, which specifies the departure times of the trips of all lines where each line has its own planning periods along the day, with the objective of optimizing synchronization events: maximize passenger transfers and minimize bus bunching along the network. We propose an integer linear programming formulation for the MSBT problem and analyze the structural properties of this formulation by a constraint propagation methodology. These properties are the basis for different operators that lead to the design of efficient metaheuristics for solving the problem. We empirically obtain high-quality feasible solutions for real size instances and show that by considering a multiperiod approach, synchronization events of trips belonging to different planning periods are not ignored, as it is the case when several single period timetables are merged. [ABSTRACT FROM AUTHOR]

Schedule disruptions are common place in the airline industry with many flight-delaying events occurring each day. Recently there has been a focus on introducing robustness into airline planning stages to reduce the effect of these disruptions. We propose a recoverable robustness technique as an alternative to robust optimisation to reduce the effect of disruptions and the cost of recovery. We formulate the recoverable robust tail assignment problem (RRTAP) as a stochastic program, solved using column generation in the master and subproblems of the Benders' decomposition. We implement a two-phase algorithm for the Benders' decomposition and identify pareto-optimal cuts. The RRTAP includes costs due to flight delays, cancellation, and passenger rerouting, and the recovery stage includes cancellation, delay, and swapping options. To highlight the benefits of simultaneously solving planning and recovery problems in the RRTAP we compare our tail assignment solution against current approaches from the literature. Using airline data we demonstrate that by developing a better tail assignment plan via the RRTAP framework, one can reduce recovery costs in the event of a disruption. [ABSTRACT FROM AUTHOR]

This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality, surpassing previous exact algorithms. [ABSTRACT FROM AUTHOR]

Traditionally, the airline crew scheduling problem has been decomposed into a crew pairing problem and a crew assignment problem, both of which are solved sequentially. The first consists of generating a set of least-cost crew pairings (sequences of flights starting and ending at the same crew base) that cover all flights. The second aims at finding monthly schedules (sequences of pairings) for crew members that cover all pairings previously built. Pairing and schedule construction must respect all safety and collective agreement rules. In this paper, we focus on the pilot crew scheduling problem in a bidline context where anonymous schedules must be built for pilots and high fixed costs are considered to minimize the number of scheduled pilots. We propose a model that completely integrates the crew pairing and crew assignment problems, and we develop a combined column generation/dynamic constraint aggregation method for solving them. Computational results on real-life data show that integrating crew pairing and crew assignment can yield significant savings-on average, 3.37% on the total cost and 5.54% on the number of schedules for the 7 tested instances. The integrated approach, however, requires much higher computational times than the sequential approach. [ABSTRACT FROM AUTHOR]

This paper proposes lower and upper bounds for the split-delivery capacitated arc-routing problem (SDCARP), a variant of the capacitated arc-routing problem in which an edge can be serviced by several vehicles. Recent papers on related problems in node routing have shown that this policy can bring significant savings. It is also more realistic in applications such as urban refuse collection, where a vehicle can become full in the middle of a street segment. This work presents the first lower bound for the SDCARP, computed with a cutting plane algorithm and an evolutionary local search reinforced by a multistart procedure and a variable neighborhood descent. Tests on 126 instances show that the new metaheuristic outperforms on average a published memetic algorithm; achieves small deviations to the lower bound; and finds 44 optima, including 10 new ones. [ABSTRACT FROM AUTHOR]

We propose a new method to compute bid prices in network revenue management problems. The novel aspect of our method is that it naturally provides dynamic bid prices that depend on how much time is left until departure. We show that our method provides an upper bound on the optimal total expected revenue and that this upper bound is tighter than the one provided by the widely known deterministic linear programming approach. Furthermore, it is possible to use the bid prices computed by our method as a starting point in a dynamic programming decomposition-like idea to decompose the network revenue management problem by the flight legs and to obtain dynamic and capacity-dependent bid prices. Our computational experiments indicate that the proposed method improves on many standard benchmarks. [ABSTRACT FROM AUTHOR]

Network games can be used to model competitive situations in which agents select routes to minimize their cost. Common applications include traffic, telecommunication, and distribution networks. Although traditional network models have assumed that realized costs only depend on congestion, in most applications they also have an uncertain component. We extend the traffic assignment problem first proposed by Wardrop in 1952 by adding random deviations, which are independent of the flow, to the cost functions that model congestion in each arc. We map these uncertainties into a Wardrop equilibrium model with nonadditive path costs. The cost on a path is given by the sum of the congestion on its arcs plus a constant safety margin that represents the agents' risk aversion. First, we prove that an equilibrium for this game always exists and is essentially unique. Then, we introduce three specific equilibrium models that fall within this framework: the percentile equilibrium where agents select paths that minimize a specified percentile of the uncertain cost; the added-variability equilibrium where agents add a multiple of the variability of the cost of each arc to the expected cost; and the robust equilibrium where agents select paths by solving a robust optimization problem that imposes a limit on the number of arcs that can deviate from the mean. The percentile equilibrium is difficult to compute because minimizing a percentile among all paths is computationally hard. Instead, the added-variability and robust Wardrop equilibria can be computed efficiently in practice: The former reduces to a standard Wardrop equilibrium problem and the latter is found using a column generation approach that repeatedly solves robust shortest path problems, which are polynomially solvable. Through computational experiments of some random and some realistic instances, we explore the benefits and trade-offs of the proposed solution concepts. We show that when agents are risk averse, both the robust and added-variability equilibria better approximate percentile equilibria than the classic Wardrop equilibrium. [ABSTRACT FROM AUTHOR]

This paper presents ration-by-distance (RBD), a new allocation method to be used in planning ground delay programs (GDPs) for traffic flow management. It is shown that RBD minimizes total expected delay, under certain assumptions related to the manner in which GDPs are dynamically controlled. On the other hand, RBD taken to the extreme has poor characteristics with respect to the equity of the allocation it produces. To address this issue, we propose a constrained version of RBD as a practical alternative to allocation procedures used in operations today. It is shown that this algorithm has superior overall performance in terms of efficiency and equity relative to existing procedures. [ABSTRACT FROM AUTHOR]

Assume that a train reaches a station with delay. At the station there is a bus ready to depart. The question of whether the bus should wait for the delayed train or depart on time is called the delay management problem. Different single objective functions for this problem have been introduced and analyzed. In this paper, we present a bicriteria model for the delay management problem, taking into account both the delay of the vehicles and the number of passengers who miss a connection. Our model does not depend on detailed data about the passengers and hence can be easily implemented in practice. To analyze the problem, we present an integer programming formulation and a graph-theoretic approach that is based on discrete time/cost trade-off project networks. Using results of project planning, we develop an efficient solution method. We tested our procedure using real-world data. The results show the applicability of the approach. [ABSTRACT FROM AUTHOR]

The period vehicle routing problem (PVRP) is a variation of the classic vehicle routing problem in which delivery routes are constructed for a period of time (for example, multiple days). In this paper, we consider a variation of the PVRP in which service frequency is a decision of the model. We refer to this problem as the PVRP with service choice (PVRP-SC). We explore modeling issues that arise when service choice is introduced, and suggest efficient solution methods. Contributions are made both in modeling this new variation of the PVRP and in introducing an exact solution method for the PVRP-SC. In addition, we propose a heuristic variation of the exact method to be used for larger problem instances. Computational tests show that adding service choice can improve system efficiency and customer service. We also present general insights on the impact of node distribution on the value of service choice. [ABSTRACT FROM AUTHOR]

The statement of the standard vehicle routing problem cannot always capture all aspects of real-world applications. As a result, extensions or modifications to the model are warranted. Here we consider the case when customers can call in orders during the daily operations; i.e., both customer locations and demands may be unknown in advance. This is modeled as a combined dynamic and stochastic programming problem, and a heuristic solution method is developed where sample scenarios are generated, solved heuristically, and combined iteratively to form a solution to the overall problem. [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]

Some instances of variational inequality models over polyhedral sets can be stated in a disaggregated or aggregated formulation related by an affine variable transformation. For such problems, we establish that sensitivity analysis results under parameterizations rely neither on the strict monotonicity properties of the problem in terms of the disaggregated variables, nor on any particular choice of their values at the solution. We show how to utilize the affine transformation to devise computational tools for calculating sensitivity results and apply them to the sensitivity analysis of elastic demand traffic equilibrium problems. The results reached show that sensitivity results do not rely on the choice of any particular route or commodity flow solution. Further, the sensitivity analysis, including the calculation of the gradient of the equilibrium link flow if it exists, can be performed by means of solving linearized traffic equilibrium problems. [ABSTRACT FROM AUTHOR]

In this paper, we undertake a detailed study of the bus stop problem in congested transit networks. In the first part of the paper, we present and discuss the bus stop models existing in the literature. In the second part, we propose a new general model for which we prove a number of good properties and we give equivalent formulations. Then, we examine two special cases of the general model. In the first case, the line capacities are considered limited and therefore they can not be exceeded by the on-board passenger flows. In the second case, the strict capacity constraints are relaxed in order to obtain a stop model that can be easily integrated into an assignment model to predict the global passenger behavior in transit networks. [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]

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]

Primal methods for the transportation problem of linear programming require substantial bookkeeping to deal with constant updating of a tree describing the shipments in the current feasible solution. This paper suggests a new means of book- keeping which is useful for long narrow problems. The method builds on previous work by the same author which reduces the number of records to be updated. The new methods reduce the number of items which have to be maintained for a replication of the tree and simplify some steps in updating the remaining items. [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]

Much of the literature involving the location of one or more new facilities on a network is concerned with minimizing a single objective function subject to constraints on the location variable. Here, we consider the problem of locating a single facility on a free network where there is more than one objective function to be minimized. A constructive method is given for finding the efficient set of solutions when the objective functions are convex and the constraints define a convex set. Partial results are given for the case where the feasible region is not a convex set. [ABSTRACT FROM AUTHOR]

This paper develops a primal simplex procedure to solve transshipment problems with an arbitrary additional constraint. The procedure incorporates efficient methods for pricing-out the basis, determining certain key vector representations, and implementing the change of basis. These methods exploit the near triangularity of the basis in a manner that takes advantage of computational schemes and list structures used to solve the pure transshipment problem. We have implemented these results in a computer code, I/O PNETS-L Computational results (necessarily limited) con/Inn that this code is significantly faster than APEX-III on some large problems. We have also developed a fast method for determining near optimal integer solutions. Computational results show that the near optimum integer solution value is usually within 0.5% of the value of the optimum continuous solution value. [ABSTRACT FROM AUTHOR]

The problem of locating a single new facility in the plane relative to several existing facilities is treated. Simultaneous consideration is given to minisum and minimax criteria. Rectilinear distances are assumed. In addition to linear programming formulations, search procedures are developed based on the special structure of the location problems examined. [ABSTRACT FROM AUTHOR]

The problem of locating a single new facility relative to m existing facilities has been studied extensively under the assumption that trips are always made between the new facility and a single existing facility each time a trip occurs. A variation of the problem is the traveling salesman location problem, which involves a traveling salesman who services m customers. Each time a trip occurs the salesman visits one or more customers during the trip. Thus, 2m - 1 different itineraries can be formed, each occurring with a given probability. The new facility, which is the starting and ending point of each itinerary, is to be located such that the expected distance traveled per unit time is minimized. An iterative procedure is presented for solving the traveling salesman location problem; computational experience with the procedure is provided. [ABSTRACT FROM AUTHOR]

Shadow prices derived from the optimal dual solution of a transportation problem give the rate at which the optimal cost changes when a warehouse capacity or market requirement is changed ceteris paribus. One of the limitations in interpreting shadow prices for managerial use is that they may be degenerate. i.e., their interpretation may be valid only over a zero range of the parameter to be varied. This paper provides an efficient procedure for computing all nondegenerate (or "real") shadow prices. The method involves breaking the optimal basis tree into subtress by dropping basic variables which are at their bounds, defining a measure of distance between the subtrees and solving a shortest path problem berween all pairs of subtrees. [ABSTRACT FROM AUTHOR]

We pursue the analysis of the Hub Operation Scheduling Problem (HOSP) over the finite and infinite horizons. The demand is assumed deterministic and stationary. We deduce the minimum fleet size V[subt] that satisfies all demands for 1 ≤ T ≤ ∞, as well as the optimal schedule that minimizes lost sales for a given fleet size smaller than V [subt]. Reintroducing the costs of empties and of delayed gales or, equivalently, the cost of empties and the gains from shipments, we resolve the issues of optimal allocation and optimal schedule over a horizon T ≤ ∞. Finally, we generalize the above results...still under the assumption of deterministic, stationary demands...first to the case in which each city communicates with its two "adjacent" cities (this is the "Wheel" problem) and then to the general network problem in which each terminal may communicate with any other terminal. [ABSTRACT FROM AUTHOR]

The problem considered is that of finding the location of a facility in the plane so that the maximum weighted rectilinear round-trip distance between the facility and N pairs of existing facilities is minimized. The round-trip distance is the total distance traveled starting from the new facility via a pair of existing facilities and back to the new facility. An efficient one-pass solution procedure is developed for finding all the optimal locations to the problem, and is compared computationally with the simplex method. Two special cases are investigated, namely, when the existing facilities lie on a line, and when all the weights are equal. [ABSTRACT FROM AUTHOR]

A schedule is a set of passages; is a 4-tuple p = (p1, p2, p3, p4) where p1, p2 denote departure and arrival terminals, p3, p4 departure and arrival times. A fleet is a partition of the schedule into chains; each chain is a finite or infinite sequence of passages p1, p2, … having the property pn² = pn+i¹ and pn4 ≤ pn+i³. The fleet-size is the minimal possible dimension (i.e., the number of chains) of the fleets. The deficit function d(t, a) for a terminal a is the difference between the number of departures and arrivals occuring at a during the interval [O, t]. It is proved that the fleet-size is equal to ∑o max≥0 d(t, a). A general method for constructing all optimal fleets is described. A special case of periodic schedules is studied and it is proved that a periodic schedule can ba decomposed into an optical periodic fleet. Applications of the deficit function technique to practical scheduling when passages have tolerances for departure times are discussed. [ABSTRACT FROM AUTHOR]

This paper provides a framework for choosing modes of transportation (rail, highway, air, etc.) by taking into account the conflicting objectives of minimizing total transportation costs and average shipment times. An efficient algorithm using the operator theory of parametric programming is presented for determining the Pareto-optimal or efficient curve denoting the minimum attainable value for the second objective for differing values of the first objective. The algorithm also provides the optimal routes, modes of transportation, and the corresponding shipping amounts for every efficient point. [ABSTRACT FROM AUTHOR]

This paper discusses the General Routing Problem approach to solving large scale routing problems. The General Routing Problem on network G = (N; A) requires finding the minimum cost, cycle that visits every node in subset Q ⊆ N and that traverses every arc in a subset R ⊆ A. Utilizing special problem characteristics and the structure of real transportation networks, large reduction in effective problem size and complexity can often be made. This permits a very effective heuristic. to produce optimum and near optimum solutions `quickly. [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]

For the solution of the multiple terminal delivery problem a formula for the actual savings is presented and a method of solution based on these actual savings is described. This method is simple both conceptually and computationally and gives results that appear to be `good.' [ABSTRACT FROM AUTHOR]

The purpose of this note is to study the calibration of the probabilistic assignment method of Dial (Trans. Res. 5, 83-111, 1971). The estimation of the parameters of the method is performed using the maximum likelihood principle and uses the observed traffic data. The estimates thus obtained can be evaluated with already existing algorithms. [ABSTRACT FROM AUTHOR]

This paper explores some of the traffic phenomena that arise when drivers have to navigate a network in which queues back up past diverge intersections. If a diverge provides two alternative routes to the same destination and the shorter route has a bottleneck that generates a queue, one would expect that queue to stabilize at an equilibrium level where the travel time on both routes is roughly equal. If the capacity of the alternative route is unlimited then this network can accommodate any demand level. However, if the bottleneck is so close to the upstream end of the link that the equilibrium queue cannot be contained in the link, then the trip time on the queued route cannot grow to match that on the alternate route. This means that the alternative route can never be attractive, even if the queue spills back past the diverge, and that drivers approaching the diverge will act as if the alternative route did not exist. As a result, a steady flow into the system greater than the capacity of the bottleneck will cause a queue to grow all the way back to the origin (blocking it). The final result is an "oversaturated static state" where the queue regulates the input flow into the system. Curiously, if the bottleneck capacity of this network is reduced below a critical level (or is eliminated altogether) then the alternative route becomes attractive again and the system cannot reach the saturation point. This phenomenon is explored in the paper, where it is also shown that: i) a network can become permanently oversaturated / undersaturated as a result of a temporary increase / decrease in link capacity, ii) even under the most favorable assumptions, and in contrast to the equivalent assignment problem with point queues, a network can be stable both in an oversaturated and an undersaturated state, and iii) temporary endogenous disturbances can permanently reverse the saturation state of a network. These findings suggest that in certain situations the time-dependent traffic assignment problem with physical queues is chaotic in nature and that (as in weather forecasting) it may be impossible to obtain input data with the required accuracy to make reliable predictions of cumulative output flows. [ABSTRACT FROM AUTHOR]

We examine the problem of determining an optimal schedule for a fleet of vehicles used to transport handicapped persons in an urban area. The problem is a generalization of the well-known advance-request Pickup and Delivery Problem with Time Windows. Due to the high level of service required by this kind of transport, several additional operational constraints must be considered. The problem is NP-hard in the strong sense, and exact approaches for the solution of real-life problems (typically with hundreds of users to be transported) are not practicable. We describe a fast and effective parallel insertion heuristic algorithm which is able to determine good solutions for real-world instances of the problem in a few seconds on a personal computer. We also present a Tabu Thresholding procedure which can be used to improve the starting solution obtained by the insertion algorithm. The application of the proposed procedures to a set of real-life instances for the city of Bologna, involving about 300 trips each, is also discussed. The heuristic algorithms obtain very good results compared with the hand-made schedules, both in terms of service quality (all the service requirements are met) and overall cost. [ABSTRACT FROM AUTHOR]

Distance constrained network location involves locating in new facilities on a transport network G so as to satisfy upper bounds on distances between pairs of new facilities and pairs of new and existing facilities. The problem is &Nscript;&Pscript;-complete in general, but polynomially solvable for certain classes. While it is possible to give a consistency characterization for these classes, it does not seem possible to give a global description of the feasible set. However, substantial geometrical insights can be obtained on the feasible set by studying its projections onto the network. The j-th projection defines the j-th composite region which is the set of all points in (3 at which new facility j can be feasibly placed without violating consistency. We give efficient methods to construct these regions for solvable classes without having to know the feasible set and discuss implications on consistency characterization, what if analysis, and recursive solution constructions. [ABSTRACT FROM AUTHOR]

The problem of optimally assigning highway trailers to railcar hitches in intermodal transportation is studied. An integer-linear programming formulation is constructed. The problem is formulated using set covering. The resulting formulation is very small, and possesses in practice a tight linear programming relaxation. This allows it to be solved effectively by a general purpose branch-and-bound code. This formulation also provided the basis for the development of a Greedy Randomized Adaptive Search Procedure (GRASP). This heuristic is observed to be extremely fast. Empirically, it finds the optimal solution to all of the problem instances furnished over a two year period by Consolidated Rail Corporation. [ABSTRACT FROM AUTHOR]

The multimedian problem is to locate "distinguishable" new facilities on a connected network G so as to minimize a total cost, which is a sum of costs directly proportional to (a) network distances between new facilities and existing facilities at vertex locations and (b) distances between pairs of new facilities. By solving a related multimedian problem in polynomial time on the "blocking graph" of G, which is a tree, we obtain information which localizes each optimal new facility location to some vertex or block (maximal nonseparable subgraph) of G. The problem then decomposes into independent multimedian problems, one for each localizing block, which can be solved by using branch and bound and a vertex-optimality property. [ABSTRACT FROM AUTHOR]

We describe algorithms for optimal single facility location problems with forbidden regions and barriers to travel. The former are those where location is not permitted, but one can travel through them, e.g., a lake. The latter are the regions where neither location nor travel is permitted, e.g., large parks in a city. Using the convexity properties of the objective function, in the first case, we develop an algorithm for finding the optimal solution. The objective function in the barrier case is shown to be non-convex. We use the concept of visibility to create a network with the location point as the source and use Dijkstra's algorithm to compute the shortest distance to all the other demand points. Using simulated annealing we find an approximate optimal solution. Numerical examples illustrate the implementation of the algorithms. [ABSTRACT FROM AUTHOR]

We address the problem of scheduling the delivery of multiple items from a single supplier to a manufacturer. The items are packaged into containers, and the containers are shipped by truck. There is a fixed charge per truck shipment, and inventory holding costs are charged on end-of-period inventory. We seek to minimize the sum of transportation and inventory costs. The problem is a combination of a bin-packing problem (due to the presence of containers and finite-capacity trucks) and a multi-item joint replenishment problem. We present a heuristic solution procedure which starts with the optimal solution of the problem in which the integrality of the containers is relaxed. (A solution procedure for this relaxed problem appears in BEN - KHEDER and YANO[2]. We develop a method to modify this solution to account for the integrality of containers. This modification scheme involves sequentially considering each item and optimally scheduling the fractional containers in the relaxed solution. To solve this single-item problem, we devise a procedure that accounts for the availability of "free" remaining capacity of trucks that have been partially filled with other items. In a computational study, our heuristic is compared with a lower bound, with variations of our heuristic, and with simple rule-of-thumb policies. The results suggest that our heuristic performs very well, especially in problems where considering tradeoffs between inventory and transportation costs is important. [ABSTRACT FROM AUTHOR]

This paper discusses the mathematical and computational underpinnings of an optimization model that reduces United Parcel Service, Inc.'s trailer-on-flat-car (TOFC) usage costs by $4 million per year. It includes an informal statement of the TOFC problem, an integer linear program (ILP) formulation, and a transformation of this ILP into a pure minimum cost network flow program, whose software implementation provides the TOFC planner with a rich set of practical features. [ABSTRACT FROM AUTHOR]

We consider a class of multistage stochastic programming problems that can be formulated as networks with random arc capacities. Large problems have proved intractable using exact methods and hence various approximations have been proposed, ranging from approximating the recourse function to sampling a small number of scenarios to capture future uncertainties. We explore the use of specialized recourse strategies that are not as general as network recourse but nonetheless capture some of the important tradeoffs. These new recourse strategies allow us to develop approximations to the recourse function that can be used to solve problems with thousands of random variables. Given these approximations, classical optimization methods can be used. The concept of hierarchical recourse is introduced and used to synthesize and generalize earlier notions of nodal recourse and cyclic recourse. [ABSTRACT FROM AUTHOR]

Location problems on a sphere can be solved easily by mathematical programming or geometrical methods i/it is known that all the demand points are located on a hemisphere. This paper presents an algorithm for determining whether m given demand points are on a hemisphere or not. In this algorithm, the great circle is rotated successively until the hemisphere which contains the m given demand points is found or it becomes known using our criteria that the m given demand points are not on a hemisphere. The convergence of this algorithm is proved, and two illustrative examples are presented. [ABSTRACT FROM AUTHOR]

The capacitated traveling salesmen location problem is the problem of locating one service station with servers, each having a limited capacity, q. The service units must visit each day all the calls that are registered in a service list. Each call is generated with a given probability and the service list contains at most n calls. In the paper we present an O(n³) time heuristic for the problem on networks. This heuristic finds a solution whose relative worst-case error equals &frac32; - 3/(2q). We also show how one can use this heuristic to solve the problem on the plane with rectilinear or Euclidean distances with the same worst-case error. In the latter case the heuristic is proved to be asymptotically optimal. [ABSTRACT FROM AUTHOR]

It is known that the planar Weber location problem with lp distances has all its solutions in the convex hull of the demand points. For l1 and l∞ distances, additional conditions are known which reduce the set 0/possible optimal points to the intersection of that convex hull, the efficient set, and the points defined by a certain grid. In this paper, we determine the smallest set which includes at least one optimal point for every Weber problem based on a given set of demand points. It is shown that for 1 < p < ∞ a certain part of the convex hull is the smallest possible set, but for p = 1 or p = &infin the known conditions do not necessarily yield the correct set. Finally, we find the smallest possible set for p = 1 or p = ∞. [ABSTRACT FROM AUTHOR]