bluuebunny/crossref_metadata_2025 huggingface dataset:
Equitable Sequencing of a Given Set of Hazardous Materials Shipments
Authors: Lindner-Dutton Laurel , Batta Rajan , Karwan Mark H.
Published: October 2008

In a recent paper, R. Gopalan, K. Kolluri, R. Batta and M. Karwan (1990) consider a model to route a set of hazardous materials shipments from an origin to a destination, so as to minimize the global risk to the community while simultaneously maintaining a desired level of equity between zones within the community. If one follows the routes produced via their solution methodology, the overall risk is small and equity between zones is achieved after all the shipments are over. However, equity may be severely violated at an intermediate stage of the shipment process. Since an accident can occur at any stage, this is not a desirable situation. Motivated by this, in this paper we consider the problem of equitably sequencing a given set of hazardous materials shipments. We presume, of course, that the set of routes are such that they engender low overall risk to the community as a whole, and once they are all traversed the risk is equitably distributed among the zones of the community—Gopalan, Kolluri, Batta, and Karwan's paper provides such routes for the case of a single origin and destination; their procedure is easily adaptable for the case of multiple origins and destinations. The objective function considered in this paper is to minimize the sum of the maximum differences in risk that exist between any two zones, where the sum is taken over the trips made. We formulate the resulting equitable sequencing problem as an integer programming problem and as a dynamic programming problem. Optimal solution strategies are examined for small-sized problems. Several heuristic solution strategies are proposed to obtain the upper bounds needed for dynamic programming fathoming and for obtaining reasonable solutions to large-sized problems. The proposed solution methods are tested on a real data set from the City and County of Albany, New York, as well as on a randomly generated data set.
Simultaneous Siting and Routing in the Disposal of Hazardous Wastes
Authors: ReVelle Charles , Cohon Jared , Shobrys Donald
Published: October 2008

The development of a system of storage facilities for spent fuel rods from commercial nuclear reactors requires solution of a model which simultaneously sites the storage facilities, assigns reactors to those facilities and chooses routes for the shipment of the spent fuel. The problem is multiobjective in its transportation component because shipment is made under two criteria: minimum transportation burden and minimum perceived risk. We blend methods of shortest paths, a zero-one mathematical program for siting, and the weighting method of multiobjective programming to show how to derive optimal solutions to this problem. Applications of the methodology demonstrate how transportation burden and risk influence location decisions and the dual role of siting/routing models in transportation policy analysis. The model is a prototype for the shipment and storage of any hazardous waste whose characteristics make the process of shipment itself an activity with risk.
The Facility Location Problem with Limited Distances
Authors: Drezner Zvi , Mehrez Avram , Wesolowsky George O.
Published: October 2008

In this paper we consider minisum and minimax single facility location problems where the effective service distance becomes a constant when the actual distance attains or exceeds a certain value. Properties of these problems are studied, and algorithms for their solution are presented.
In Memoriam
Authors: Odoni Amedeo , Nagurney Anna
Published: October 2008

In Memoriam to Stella Dafermos, 1940–1990, the original Guest Editor of this special issue on Network Equilibrium.
Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem
Authors: Larsson Torbjörn , Patriksson Michael
Published: October 2008

The class of simplicial decomposition (SD) schemes has shown to provide efficient tools for nonlinear network flows. When applied to the traffic assignment problem, shortest route subproblems are solved in order to generate extreme points of the polyhedron of feasible flows, and, alternately, master problems are solved over the convex hull of the generated extreme points. We review the development of simplicial decomposition and the closely related column generation methods for the traffic assignment problem; we then present a modified, disaggregated, representation of feasible solutions in SD algorithms for convex problems over Cartesian product sets, with application to the symmetric traffic assignment problem. The new algorithm, which is referred to as disaggregate simplicial decomposition (DSD), is given along with a specialized solution method for the disaggregate master problem. Numerical results for several well known test problems and a new one are presented. These experimentations indicate that only few shortest route searches are needed; this property is important for large-scale applications. The modification proposed maintains the advantages of SD, and the results show that the performance of the new algorithm is at least comparable to that of state-of-the-art codes for traffic assignment. Moreover, the reoptimization capabilities of the new scheme are significantly better; this is a main motive for considering it. The reoptimization facilities, especially with respect to changes in origin-destination flows and network topology, make the new approach highly profitable for more complex models, where traffic assignment problems arise as subproblems.
Transfer Optimization in a Transit Network
Authors: Bookbinder James H. , Désilets Alain
Published: October 2008

Transfer optimization attempts to minimize the overall inconvenience to passengers who must transfer between lines in a transit network. Bus trips are scheduled to depart from their terminal so as to minimize some objective function measuring that inconvenience. In this paper, the transit network is assumed to be given, and the scheduled headway is treated as fixed on each line. We denote by ti the departure time of the first bus on line i. {ti} are termed “offset times,” and constitute the decision variables of our model. To take into account stochastic travel times of buses, our treatment of transfer optimization employs a simulation procedure in combination with an optimization model. That model turns out to be a relaxation of the Quadratic Assignment Problem. It can incorporate a wide range of objective functions (measures of overall passenger disutility) and a variety of policies for holding buses at a transfer point. In the case where buses are not held at all, we show, for a number of different objective functions and transit networks, the negative consequences of optimizing transfers with a deterministic bus-travel-times assumption, if these travel times are in fact random variables. Suggestions are then made for future research.
Boolean and Graph Theoretic Formulations of the Simple Plant Location Problem
Authors: Dearing P. M. , Hammer P. L. , Simeone B.
Published: October 2008

A formulation of the simple plant location problem as the minimization of a pseudo-Boolean function is transformed into a set covering problem and into a weighted vertex packing problem on a graph, called the “plant location graph.” For the special case of a simple plant location problem derived from a tree network, the plant location graph is shown to be weakly triangulated, so that a maximum weighted vertex packing can be found in polynomial-time by existing algorithms.
On Parametric Medians of Trees
Authors: Erkut Erhan , Tansel Barbaros C.
Published: October 2008

In this paper we consider the optimal location of a single facility with respect to a set of demand points on a tree network. The demands of the points to be served are dynamic and our model takes into account predictable changes in these demands. We study problems with both linear and nonlinear demand functions. We make use of the analytical properties of tree networks and sensitivity analysis, and devise efficient algorithms to construct the optimal trajectory of the parametric location problem. We also give theory that exploits the network topology.
An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints
Authors: Koskosidis Yiannis A. , Powell Warren B. , Solomon Marius M.
Published: October 2008

The Vehicle Routing and Scheduling Problem with Time Window constraints is formulated as a mixed integer program, and optimization-based heuristics which extend the cluster-first, route-second algorithm of Fisher and Jaikumar are developed for its solution. We present a new formulation based on the treatment of the time window constraints as soft constraints that can be violated at a cost and we heuristically decompose the problem into an assignment/clustering component and a series of routing and scheduling components. Numerical results based on randomly generated and benchmark problem sets indicate that the algorithm compares favorably to state-of-the-art local insertion and improvement heuristics.
Operators-Users Equilibrium Model in a Partially Regulated Transit System
Authors: Fernandez Enrique , Marcotte Patrice
Published: October 2008

We present two formulations of a model for finding equilibrium passenger and operator flows in a partially regulated transit system where bus operators are free to choose the routes on which they offer public transport services. The transit fares are assumed fixed and known. The model offers a detailed representation of the transit system network and of the transit users behavior. Congestion effects are also considered as a consequence of the operation of cars and buses over a common road network. Two algorithmic solution approaches are investigated.
The Vehicle Routing Problem with Stochastic Travel Times
Authors: Laporte Gilbert , Louveaux François , Mercure Hélène
Published: October 2008

This paper considers vehicle routing problems (VRPs) with stochastic service and travel times, in which vehicles incur a penalty proportional to the duration of their route in excess of a preset constant. Three mathematical programming models are presented: a chance constrained model, a three-index simple recourse model and a two-index recourse model. A general branch and cut algorithm for the three models is described. Computational results indicate that moderate size problems can be solved to optimality.
Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
Authors: Malandraki Chryssi , Daskin Mark S.
Published: October 2008

The time dependent vehicle routing problem (TDVRP) is defined as follows. A vehicle fleet of fixed capacities serves customers of fixed demands from a central depot. Customers are assigned to vehicles and the vehicles routed so that the total time of the routes is minimized. The travel time between two customers or between a customer and the depot depends on the distance between the points and time of day. Time windows for serving the customers may also be present. The time dependent traveling salesman problem (TDTSP) is a special case of the TDVRP in which only one vehicle of infinite capacity is available. Mixed integer linear programming formulations of the TDVRP and the TDTSP are presented that treat the travel time functions as step functions. The characteristics and properties of the TDVRP preclude modification of most of the algorithms that have been developed for the vehicle routing problem. Several simple heuristic algorithms are given for the TDTSP and TDVRP without time windows based on the nearest-neighbor heuristic. A mathematical-programming-based heuristic for the TDTSP without time windows using cutting planes is also briefly discussed. Test results on small, randomly generated problems are reported.
The Moving and “Phantom” Bottlenecks
Authors: Gazis Denos C. , Herman Robert
Published: October 2008

When a slow-moving vehicle occupies one of the lanes of a multilane highway, it often causes queueing behind it, not unlike one caused by an actual stoppage on that lane. This happens when the traffic flow rate upstream from the slow vehicle exceeds a certain critical value. We define this situation as the case of the Moving Bottleneck. There are other situations when people caught in a traffic jam slowly advance to the point of a suspected breakdown or other obstruction, only to find out that no such obstruction exists but suddenly the flow of traffic is free and rapid. We define this situation as that of the Phantom Bottleneck. We present a model describing these two situations on the basis of reasonable assumptions about the behavior of drivers whose movement is obstructed by the slow vehicle. Using a phenomenological relationship between flow and concentration, we derive formulas describing the behavior of the moving queue caused by the obstruction. Finally, we suggest procedures for validating the model and using it for a rational approach to the design of allowable minimum speeds on highways.
Shipment Routing Algorithms with Tree Constraints
Authors: Powell Warren B. , Koskosidis Ioannis A.
Published: October 2008

Routing shipments efficiently on less-than-truckload trucking networks represents an important subproblem of the general network design problem that arises when designing a service network. The objective of the LTL shipment routing problem is to minimize the total transportation and handling costs subject to two key constraints: (i) service between two terminals must always satisfy a given minimum frequency (measured in trailers per week) and (ii) the paths from all origins into a destination should form a tree. This second constraint reflects a practical limitation on the types of instructions that can be implemented in the field. A solution approach is developed using a shortest path based formulation with additional routing constraints imposed to refine the routing in response to minimum frequency constraints. A local improvement heuristic is presented which manipulates the routing constraints. A separate set of primal-dual algorithms are also developed which provide both upper and lower bounds. Numerical experiments are presented to evaluate the effectiveness of both the local improvement heuristic and the primal-dual algorithms.
Designing Railroad Operating Plans: A Dual Adjustment Method for Implementing Lagrangian Relaxation
Authors: Keaton Mark H.
Published: October 2008

The problem of determining optimal train connections, frequencies, and blocking and routing plans for freight cars in single-carload general commodity service is modeled as an all-integer linear programming problem. The objective is to minimize train cost, car time cost, and yard classification cost, subject to limits on train size, number of blocks formed by yard, and maximum origin-to-destination trip times. A Lagrangian relaxation technique is used to solve the problem. A dual adjustment procedure, which exploits the structure of the model, is used to implement the relaxation. This procedure makes it possible to efficiently obtain close-to-optimal solutions to problems of realistic size.
Numerical Methods for Simulating Transient, Stochastic Queueing Networks—I: Methodology
Authors: Simão Hugo P. , Powell Warren B.
Published: October 2008

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.
Numerical Methods for Simulating Transient, Stochastic Queueing Networks—II: Experimental Design
Authors: Simão Hugo P. , Powell Warren B.
Published: October 2008

In a companion study, Simão and Powell have introduced a numerical, discrete-time approach for simulating stochastic transient networks of bulk queues that often arise in consolidation networks. A set of approximations was proposed in order to produce a computationally tractable algorithm. This paper describes the numerical methods actually used for calculating probabilities and the results of extensive numerical experiments which test the accuracy of those approximations and the overall efficiency of the procedure, vis-à-vis the alternative Monte Carlo method.
Competition on Networks: Some Introductory Notes
Authors: de Palma André , Thisse Jacques-François
Published: October 2008

Problems involving competition on networks play an increasingly important role in modern economies. This can be partially explained by the development of new technologies in transportation and telecommunications, which have favored the entry of firms offering customized products. For example, the increased variety in telephone services has led new companies to segment the market and to exploit specific niches. Furthermore many services have been privatized or deregulated in North America and in Europe (such as the airline industry, bus companies in many cities, truncking, energy, cable television and long distance telephone services), thus fostering the emergence of competition in new economic sectors. These problems have many facets which have begun to be analyzed in the operations research and economics literature, as shown by the expanding flow of papers dealing with the various dimensions of competition on networks.
Equilibrium on a Traffic Corridor with Several Congested Modes
Authors: Jehiel Philippe
Published: October 2008

This paper examines the user equilibrium on a traffic corridor with several congested modes, a continuum of entry points and a single exit point. The approach taken is in the spirit of Beckmann et al. (1956) since it exploits the equivalence between the user equilibrium problem and a minimization problem. It is shown that this equivalence can be derived from a general economic principle due to Pigou (1950) that “If people are forced through taxes to pay the social costs of their actions, they act optimally.” The paper also demonstrates a set of conditions under which efficiency can be achieved by the application of only a gasoline tax on auto travel.
A Competitive Network Design Problem with Pricing
Authors: Lederer Phillip J.
Published: October 2008

This paper presents a simple model of competition between transport firms that captures the interaction of system design, price setting, and consumer choice. Transport competition is modeled as a noncooperative game where firms first select network designs, then prices for transportation between any two nodes. The goal is to find a Nash equilibrium in prices and system designs for all competing firms. Competition is studied under two alternate assumptions about consumer choice: customers can bundle separately purchased legs and customers cannot. If bundling cannot occur, it is shown that unique Nash equilibrium prices exist and that each firm's profit can be written as the difference between two minimum cost flow problems. Sufficient conditions for the existence of equilibrium network designs are also developed. If bundling can occur, it is shown that a price equilibrium may not exist, and if it does, the price equilibrium may not be unique. Lack of existence or uniqueness implies that firm profit is not a well defined function of network designs. This shows that the network design problem with bundling is difficult. With bundling, some results are possible in the case of duopoly competition: an equilibrium in prices always exists but equilibrium prices may not be unique. However, when each firm chooses a network design to maximize the lower bound of its profit, the equilibrium network designs chosen are the same as those chosen when bundling is ignored.
Variational Inequalities and Networks in the Formulation and Computation of Market Equilibria and Disequilibria: The Case of Direct Demand Functions
Authors: Nagurney Anna , Zhao Lan
Published: October 2008

In this paper we introduce competitive spatial market models with direct demand functions, which permit policy interventions in the form of price controls. We derive variational inequality formulations of the governing economic conditions and establish existence and uniqueness results. A decomposition algorithm that exploits the network structure is proposed and convergence results given. The algorithm is then interpreted as an adjustment process to highlight the underlying economic behavior. Finally, numerical results for a variety of problems are presented.
A Network-Based Primal-Dual Heuristic for the Solution of Multicommodity Network Flow Problems
Authors: Barnhart Cynthia , Sheffi Yosef
Published: October 2008

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.
Transit Assignment for Congested Public Transport Systems: An Equilibrium Model
Authors: de Cea Joaquín , Fernández Enrique
Published: October 2008

We propose a new formulation for the assignment problem over congested transit networks. The congestion effects due to insufficient capacity of system elements (transit lines) are considered to be concentrated at transit stops. Waiting times on access links are therefore dependent on passenger flows. A special formulation of the transit network is used in order to model correctly the congestion effects. Finally, algorithms for solution are analyzed.
Properties of Dynamic Traffic Equilibrium Involving Bottlenecks, Including a Paradox and Metering
Authors: Arnott Richard , de Palma André , Lindsey Robin
Published: October 2008

D. Braess and others have shown that creating a new link in a congested network, or adding capacity to an existing link, can raise total travel costs if drivers switch routes. Here we show that a paradox can also result when routes are fixed, but users choose when to travel. As is true of the Braess paradox, the paradox here arises when the inefficiency due to underpricing of congestion increases by more than the direct benefit of the new capacity. For a corridor with two groups of drivers, we show that expanding capacity of an upstream bottleneck raises travel costs when the reduction in congestion upstream is more than offset by increased congestion downstream. Metering can thus improve efficiency. Optimal capacity for an upstream bottleneck is equal to, or smaller than, optimal capacity downstream. Total construction costs equal total variable travel costs when capacities are optimal and construction costs are independent of scale.
A Combined, Equilibrium Model of Urban Personal Travel and Goods Movements
Authors: Oppenheim Norbert
Published: October 2008

A combined equilibrium model of urban personal travel and goods movements is developed, in which commodity flows are generated by the consumption of a commodity, as part of the conduct of a given, generic urban activity undertaken by individual consumers/travelers. A fundamental feature of the model is the explicit, full representation of the interacting behaviors of commodity consumers/travelers and commodity suppliers/shippers, within the framework of a spatial, competitive economy. Concurrently, passenger and freight flows take place on a common, congestible network, which is also used for general travel. Travelers/consumers are assumed to minimize their costs (activity plus travel) through their joint choice of an activity site and travel itinerary to it. Activity suppliers also minimize the costs of buying and shipping goods, through their joint choice of wholesaler and freight shipping routes. In both cases, activity costs are perceived randomly, and travel costs are perceived deterministically. Commodity supply meets demand at activity sites. Locational commodity prices are determined endogenously. The transportation network, in which a given link may or may not be shared by private cars and freight trucks, is in user equilibrium, for all users. As a special case, a spatial price equilibrium for the commodity is obtained. It is shown that, under certain conditions, the model always possesses a unique solution. An algorithm for obtaining that solution is described. In conclusion, several areas for further extensions of the model are discussed.
Technical Note—On the Equivalence of Dual Methods for Two Location Problems
Authors: Xu Ning , Lowe Timothy J.
Published: October 2008

Separate algorithms have been reported in the literature to find dual solutions to the linear programming relaxations of the simple plant location problem, and the location covering problem. We explore the connection between these two algorithms.
Solving Optimally the Static Ground-Holding Policy Problem in Air Traffic Control
Authors: Richetta Octavio , Odoni Amedeo R.
Published: October 2008

As air traffic congestion grows, ground-holding (or “gate-holding”) of aircraft is becoming increasingly common. The “ground-holding policy problem” (GHPP) consists of developing strategies for deciding which aircraft to hold on the ground and for how long. In this paper we present a stochastic linear programming solution to the static GHPP for a single airport. The computational complexity of existing solutions requires heuristic approaches in order to solve practical instances of the problem. The advantage of our solution is that, even for the largest airports, problem instances result in linear programs that can be solved optimally using just a personal computer. We present a set of algorithms and compare their performance to a deterministic solution and to the passive strategy of no ground-holds (i.e., to the strategy of taking all delays in the air) under different weather scenarios.
Modeling the Customer Arrival Process and Comparing Decision Rules in Perishable Asset Revenue Management Situations
Authors: Weatherford Lawrence R. , Bodily Samuel E. , Pfeifer Phillip E.
Published: October 2008

A model for customer arrivals is presented that allows evaluation of different decision rules in perishable asset revenue management (PARM) situations. The model is used to derive probabilities necessary to operationalize the implementation of an optimal decision rule for PARM problems with diversion and two price classes. Heuristic approaches are compared to the proper closing out of price classes to see how much of an improvement can be made in expected contribution. The sensitivity of the difference in expected contribution between these rules is tested relative to changes in the model's input parameters. Managerial insights are presented.
A Decision Support Framework for Airline Flight Cancellations and Delays
Authors: Jarrah Ahmad I. Z. , Yu Gang , Krishnamurthy Nirup , Rakshit Ananda
Published: October 2008

Aircraft shortages occasionally occur during day-to-day airline operation due to factors such as unfavorable weather conditions, mechanical problems, and delays in the schedule of incoming flights. Flight controllers need to respond to such shortages on a real-time basis by delaying or cancelling flights, swapping aircraft among scheduled flights, or requesting the usage of surplus aircraft. The choices undertaken aim at minimizing the losses incurred while retaining an operable flight schedule. In this paper, we represent two network models for aiding flight controllers in this complex decision environment. The models represent an attempt at conceptualizing this important and relatively unstudied problem, and form the basis for an evolving decision support system at United Airlines.
Airline Scheduling and Routing in a Hub-and-Spoke System
Authors: Dobson Gregory , Lederer Phillip J.
Published: October 2008

This paper studies the competitive choice of flight schedules and route prices by airlines operating in a hub-and-spoke system. Airlines choose flight schedules and route prices to maximize profit, considering competitors' decisions. This research makes three contributions. First, an expression is derived calculating demand for each route as a function of the service quality and prices of all routes. Second, a mathematical programming heuristic is developed to find the schedule and prices that maximize an airline's profit against fixed schedules and prices for other airlines. Third, the heuristic is used to study competition by allowing each airline to optimize its schedule and prices against the others' choices and by searching for an equilibrium. The performance of the algorithm is evaluated against alternate heuristics and a five-city sample problem is presented. Finally, two competitive examples are presented and analyzed.
Variable-Depth Search for the Single-Vehicle Pickup and Delivery Problem with Time Windows
Authors: van der Bruggen L. J. J. , Lenstra J. K. , Schuur P. C.
Published: October 2008

We consider a single depot and a set of customers with known demands, each of which must be picked up and delivered at specified locations and within given time windows. We seek a route and a schedule for a single vehicle with known capacity, which minimizes the route duration, i.e., the difference between the arrival time and the departure time at the depot. We develop a local search method for this problem based on a variable-depth search, similar to the Lin-Kernighan algorithm for the traveling salesman problem. The method consists of two phases. In the first phase, a feasible route is constructed; in the second phase, it is iteratively improved. In both phases, we use a variable-depth search built up out of seven basic types of arc-exchange procedures. When tested on real-life problems, the method is shown to produce near-optimal solutions in a reasonable amount of computation time. In spite of this, there is the theoretical possibility that the method may end up with a poor or even infeasible solution. As a safeguard against such an emergency, we have developed an alternative algorithm based on simulated annealing. As a rule, it finds high quality solutions in a relatively large computation time.
A Routing Model for Pickups and Deliveries: No Capacity Restrictions on the Secondary Items
Authors: Daganzo Carlos F. , Hall Randolph W.
Published: October 2008

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.
Restricted Recourse Strategies for Dynamic Networks with Random Arc Capacities
Authors: Powell Warren B. , Frantzeskakis Linos F.
Published: October 2008

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.
Optimal Inspection and Repair Policies for Infrastructure Facilities
Authors: Madanat Samer , Ben-Akiva Moshe
Published: October 2008

State-of-the-art decision-making models in the area of infrastructure maintenance and rehabilitation (which are based on the Markov Decision Process) do not take into account the uncertainty in the measurement of facility condition. This paper presents a methodology, the Latent Markov Decision Process (LMDP), which explicitly recognizes the presence of random errors in the measurement of the condition of infrastructure facilities. Two versions of the LMDP are presented. In the first version, the inspection schedule is fixed, which is the usual assumption made in state-of-the-art models. The second version of the LMDP minimizes the sum of inspection and M & R costs. An empirical comparison of the two versions of the LMDP and the traditional MDP illustrates the importance of incorporating measurement uncertainty in decision-making and of optimizing the inspection schedule.
Exact Solution to a Location Problem with Stochastic Demands
Authors: Laporte Gilbert , Louveaux François V. , van Hamme Luc
Published: October 2008

This paper considers a class of Capacitated Facility Location Problems in which customer demands are stochastic. The problem is formulated as a stochastic integer linear program, with first stage binary variables and second stage continuous variables. It is solved to optimality by means of a branch and cut method. Computational results are reported for problems involving up to 40 customers and 10 potential facility locations.
Network Equilibrium Models with Combined Modes
Authors: Fernandez Enrique , de Cea Joaquin , Florian Michael , Cabrera Enrique
Published: October 2008

Many trips in urban areas are taken by using more than one mode, such as the so called “kiss'n ride” or “park'n ride” trips; the first part of the trip is taken by the private care and then completed by taking one or more transit modes. We present in this paper several approaches to formulating network equilibrium models with combined modes. One of these approaches results in a new network equilibrium model, where the combined mode is considered as a distinct alternative in a demand model, and the network flows are suitably modelled on different modal subnetworks. The mathematical structure of the model is analysed and solution algorithms are outlined.
Transit Equilibrium Assignment: A Model and Solution Algorithms
Authors: Wu Jia Hao , Florian Michael , Marcotte Patrice
Published: October 2008

In this paper we propose a model for the transit equilibrium assignment problem (TEAP) and develop two algorithms for its solution. The behavior of the transit users is modeled by using the concept of hyperpaths (strategies) on an appropriate network (general network) which is obtained from the road network and the transit lines by a transformation which makes explicit the walk, wait, in-vehicle, transfer and alight arcs. The waiting (generalized) cost is a function of both frequency of the transit lines and congestion effects due to queues at stops. The TEAP is stated and formulated as a variational inequality problem, in the space of hyperpath flows, and then solved by the linearized Jacobi method and the projection method. We prove the global convergence of these two algorithms for strongly monotone arc cost mappings. The implementation of the algorithms and computational experiments are presented as well.
Subgradient Methods for the Service Network Design Problem
Authors: Farvolden Judith M. , Powell Warren B.
Published: October 2008

We present local-improvement heuristics for a Service Network Design Problem encountered in the motor carrier industry. The scheduled set of vehicle departures determines the right hand side of the capacity constraints of the shipment routing subproblem which is modeled as a multicommodity network flow problem. The heuristics, one for dropping a scheduled service and another for introducing a new service, are based upon subgradients derived from the optimal dual variables of the shipment routing subproblem. The basis of the multicommodity network flow problem is partitioned to facilitate the calculation of the dual variables, reduced costs and subgradients. These are determined in large part by additive and network operations, and only in small part by matrix multiplication. The results of our computational experimentation are presented.
Efficient Algorithms for Solving the Shortest Covering Path Problem
Authors: Current John , Pirkul Hasan , Rolland Erik
Published: October 2008

The Shortest Covering Path Problem (SCPP) is one of identifying the least cost path from a pre-specified starting node to a pre-specified terminus node. The path is constrained by the condition that it must cover every node in the network. A node is considered to be covered if it is within some pre-specified covering distance of a node on the path. This SCPP has many potential applications, especially in hierarchical network design, and bi-modal routing problems. In this paper we introduce two efficient algorithms for solving the SCPP. The first is a heuristic based upon a Lagrangian relaxation of the problem. The second is an exact algorithm based upon a branch and bound procedure which utilizes the bounds generated by the Lagrangian relaxation scheme. Computational tests indicate that both procedures are very efficient. The heuristic identified and verified the optimal solution for 135 of the 160 test problems solved. The optimal solution to the remaining 25 problems was readily identified by the exact algorithm.
The General Pickup and Delivery Problem
Authors: Savelsbergh M. W. P. , Sol M.
Published: October 2008

In pickup and delivery problems vehicles have to transport loads from origins to destinations without transshipment at intermediate locations. In this paper, we discuss several characteristics that distinguish them from standard vehicle routing problems and present a survey of the problem types and solution methods found in the literature.
A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing
Authors: Fisher Marshall L. , Tang Baoxing , Zheng Zhang
Published: October 2008

We consider a problem in which a fleet of vehicles must be scheduled to pickup and deliver a set of orders in truckload quantities. We describe a new algorithm based on a network flow relaxation which imposes necessary conditions on the flow of empty vehicles from order delivery points to order pickup points. The network flow model provides a lower bound and a nearly feasible solution that can be made feasible with some simple heuristics. Our algorithm is fast and has performed well on a set of more than 430 test problems which include a number of real problems obtained from the Shanghai Truck Transportation Corporation. On real problems and on random problems generated using real pickup and delivery points, the algorithm consistently produces solutions within 1% of optimality.
The Economic Lot and Delivery Scheduling Problem: Powers of Two Policies
Authors: Hahm Juho , Yano Candace Arai
Published: October 2008

We investigate the problem of simultaneously scheduling the final production line of a captive supplier and the delivery of components produced on that line to an assembly facility that uses these components at a constant rate. The supplier incurs a sequence-independent setup cost and/or setup time each time the production line is changed over from one component to another. On the other hand, setup costs and times for the assembly facility are negligible. We consider two types of delivery costs: a fixed charge for each delivery, and a fixed-charge-per-truck cost. We develop a heuristic procedure to find a cyclic production and delivery schedule with the power-of-two property. That is, in each cycle, each component is produced 2μ times for some small integer μ, where the value of μ may differ across components. In addition, several equally-spaced deliveries occur in each cycle, where the number of deliveries is equal to the least common multiple of the component production frequencies. The objective is to find the schedule that minimizes the average cost per unit time of transportation, inventory at both the supplier and the assembly facility, and setup costs at the supplier. Computational results suggest that the heuristic performs well in an absolute sense, and that significant savings can be achieved by using coordinated production and delivery schedules rather than approaches in which they are decided sequentially. The results also indicate that in many situations, pure just-in-time policies (in which production and delivery frequencies are equal) are far from optimal. Our model provides a basis for determining the type and extent of improvements needed in the quest for just-in-time.
The m-Traveling Salesman Problem with Minmax Objective
Authors: França Paulo M. , Gendreau Michel , Laporte Gilbert , Müller Felipe M.
Published: October 2008

This article proposes algorithms for the Minmax version of the m-Traveling Salesman Problem in which the objective is to minimize the length of the longest route. A tabu search heuristic and two exact search schemes are developed. Problems involving up to 50 vertices are solved to optimality.
The Intermodal Trailer Assignment Problem
Authors: Feo Thomas A. , González-Velarde José Luis
Published: October 2008

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.
Letter to the Editor—On the Statistics of the Linear Car Following Model
Authors: Weiss George
Published: October 2008

In this paper we shall show the somewhat disappointing result that the Reuschel-Pipes model does not lead to reasonable results in determining a limiting headway distribution.
The Airline Crew Scheduling Problem: A Survey
Authors: Arabeyre J. P. , Fearnley J. , Steiger F. C. , Teather W.
Published: October 2008

This is a survey of the different approaches studied by a number of airlines in the past few years to attempt to optimize the allocation of crews to flights. The approach is usually one of integer programming with 0-1 variables, the matrix of coefficients having a very special form. The survey covers the generation, costing, reduction, and optimization of such matrices.
Erratum—Polar and Rectangular Road Networks for Circular Cities
Authors: Holroyd E. M.
Published: October 2008

Correction to Holroyd, E. M. Letter to the Editor—Polar and rectangular road networks for circular citites. Trans. Sci. 3 (1) 86–87.
Sherratt's Model and Commuter Travel
Authors: Wilkins C. A.
Published: October 2008

It is suggested that approaches based on Sherratt's model may be useful for dealing with lengths of commuter journeys in cities and a number of relevant p.d.f.'s and expectations are presented for the symmetric case.
Highway Merging Problem with Acceleration Area
Authors: Mine Hisashi , Mimura Takeshi
Published: October 2008

We study the highway merging problem with acceleration area. We suppose there is an acceleration area beside a highway and that a vehicle which arrives at an entrance from a rampway waits for a chance to merge as it accelerates on the acceleration area. The velocity of the merging vehicle at time t is a known function v(t), where the time origin is the moment when the merging vehicle arrives at the entrance. We derive the probability density function of the delay to the merging vehicle, i.e., the time between its arrival at the entrance and the moment it merges into the highway. We also discuss a property of the probability density function of the delay.
Rapid Transit Interstation Spacings for Maximum Number of Passengers
Authors: Vuchic Vukan R.
Published: October 2008

Two transportation systems, following the same alignment, serve an area from which population commutes to a central point. One system has a constant speed and can be taken at any point along the line; the other has a discrete movement and can be boarded at stations only. The study analyzes the optimal station locations of the latter system for which its patronage will be maximum, assuming that passengers select systems on the basis of shorter travel time. The optimal solution, derived analytically and shown graphically on a time-distance diagram, indicates that the interstation spacings for this objective should be increasing at a decreasing rate in the direction of cumulation. Compared with the optimal interstation spacings for minimum total passenger travel time, given in a recent paper by Vuchic and Newell, this solution has a greater density of stations and, naturally, larger travel times. Sensitivity of the two solutions to various parameters is examined. Several problems to which this model would be applicable are shown and the model's realistic validity is discussed. From the optimal solution and numerical examples, several conclusions are drawn that are directly relevant to the planning of station locations for discrete public transportation systems.