Search

The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of the sampled version of the fictitious play algorithm, familiar from game theory, for games with identical payoffs, and propose a heuristic based on fictitious play as a solution procedure for discrete optimization problems of the form max {u(y) y = (y1,…yn ∈ y1 x … x yn} i.e., in which the feasible region is a Cartesian product of finite sets y1 i ∈ N = (1, …, n). The contributions of this paper are twofold. In the first part of the paper, we broaden the existing results on convergence properties of the fictitious play algorithm on games with identical payoffs to include an approximate fictitious play algorithm that allows for errors in players 'best replies. Moreover, we introduce sampling-based approximate fictitious play that possesses the above convergence properties, and at the same time provides a computationally efficient method for implementing fictitious play. In the second part of the paper, we motivate the use of algorithms based on sampled fictitious play to solve optimization problems in the above form with particular focus on the problems in which the objective function u(·) comes from a "black box," such as a simulation model, where significant computational effort is required for each function evaluation. [ABSTRACT FROM AUTHOR]

Vehicle scheduling is the process of assigning vehicles to a set of predetermined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and computational aspects of the polynomially solvable case in which there is a single depot and vehicles are identical. A quasiassignment formulation is reviewed and an alternative asymmetric assignment formulation is given. The main contributions of the paper area new two-phase approach which is valid in the case of a special cost structure, an auction algorithm for the quasiassignment problem, a core-oriented approach, and an extensive computational study. New algorithms are compared with the most successful algorithms for the vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with respect to computation time. Such improvement can, for example, be very important when this particular vehicle-scheduling problem appears as a subproblem in more complex vehicle- and crew-scheduling problems. [ABSTRACT FROM AUTHOR]

This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]

In this paper we discuss three mean-variance location problems. Two of them are constrained problems where one performance measure--mean of the weighted distance, or variance, is minimized subject to an upper bound constraint on the value of the other. In the third problem the objective function minimized is given by the mean plus a constant times the variance. The paper includes polynomial time algorithms to solve the three problems. The solutions produced by these algorithms are Pareto optimum solutions (solutions that are strictly better than any other solution in at least one of the two measures: mean and variance). [ABSTRACT FROM AUTHOR]

The transportation planning forecasting process has been traditionally performed on a sequential, disconnected, heuristic basis, using different methodologies for each one of the stages. In an attempt to improve this situation, a first step toward developing a unified transportation forecasting methodology is described in this paper. This is done by showing how many, seemingly different, problems can be cast as analogous route choice problems on abstract networks and studied with the same methodology. As a consequence of this analogy, it is possible to perform equilibrium analyses and to study several problems simultaneously, by choosing an adequate topology for the abstract network. The bulk of this paper is devoted to presenting an algorithm within which many of these transportation equilibrium analyses can be carried out The conditions of equilibrium are identified and defined, and an efficient algorithm for the solution of the equilibration problem is introduced. The solution method, which uses the multinomial pro bit model for allocation of flow to routes, can increase the accuracy and reduce the cost of many transportation equilibrium analyses. [ABSTRACT FROM AUTHOR]

This paper describes a hybrid method for solving the multi-commodity transportation and transshipment spatial equilibrium models. The method is basically a specialization of the block successive overrelaxation method for solving a linear complementarity problem with certain block structure and consists of solving a sequence of subproblems of the single-commodity type. These subproblems are solved by a special-purpose principal pivoting algorithm developed in an earlier paper. Under some mild conditions, convergence of the proposed method is established. Finally, computational experience of solving some fairly large randomly generated problems by the proposed hybrid method is presented. [ABSTRACT FROM AUTHOR]

While the joint optimization of production and outbound distribution decisions in a manufacturing context have been intensively studied in the past decade, the integration of production, inventory, and inbound transportation from suppliers have received much less attention despite its practical relevance. This paper aims to fill the gap by introducing a general model for the assembly routing problem (ARP), which consists of simultaneously planning the assembly of a finished product at a plant and the routing of vehicles collecting materials from suppliers to meet the inventory requirements imposed by the production. We formulate the problem as a mixed-integer linear program and we propose a three-phase decomposition matheuristic that relies on the iterative solution of different subproblems. The first phase determines a setup schedule while the second phase optimizes production quantities, supplier visit schedules and shipment quantities. The third phase solves a vehicle routing problem for each period in the planning horizon. The algorithm is flexible, and we show how it can also be used to solve two well-known outbound distribution problems related to the ARP: the production routing problem and the inventory routing problem. Using the same parameter setting for all problems and instances, we obtain 781 new best-known solutions out of 2,628 standard IRP and PRP test instances. In particular, on large-scale multivehicle instances, the new algorithm outperforms specialized state-of-the-art heuristics for these two problems. The online appendix is available at https://doi.org/10.1287/ijoc.2018.0817. [ABSTRACT FROM AUTHOR]

The purpose of the present paper is to extend the loop-technique of the stepping-stone algorithm to the generalized transportation problem. The main result (Theorem and Corollary of §6) is, that passing from a basic feasible solution to another one may always be carried out by constructing a simple symmetrical or a double loop (as defined in §2) and computing new values for the variables only along this path. The amount of computations needed for this turns out to be substantially reduced as compared to the usual way of solving the system of equations relating the new basis to the old one. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of routing in-house transport vehicles that feed parts to workstations in assembly plants or workshops just in time. The capacitated vehicles, typically so-called tow trains, perform their assigned route cyclically without break and provide each station with the exact quantity of parts required until the next arrival of the vehicle. Hence, the demand of each station depends on the duration of the route serving the station: The longer the route duration, the less frequently the station is visited and the higher its demand. The goal is to minimize first the number of vehicles and second the total route duration, while respecting given minimum service frequencies at the stations. We provide a mathematical formulation of this novel problem and address it by means of a large neighborhood search. The algorithm is able to solve realistic instances in acceptable time and vastly outperforms a default solver. We discuss two variants of the problem, one in which split deliveries to stations are allowed and another assuming that all stations lie on a straight line. Finally, we investigate the extent to which assuming constant demand rates may lead to problems during the day-to-day operations of the part-feeding system, where demands are not necessarily constant. [ABSTRACT FROM AUTHOR]

This paper introduces the multiconstraint team orienteering problem with multiple time windows (MC-TOP-MTW). In the MC-TOP-MTW, a set of vertices is given, each with a service time, one or more time windows, and a score. The goal is to maximize the sum of the collected scores, by a fixed number of tours. The tours are limited in length and restricted by the time windows and additional constraints. Next to a mathematical formulation of the MC-TOP-MTW, the main contribution of this paper is a fast and effective algorithm for tackling this problem, by hybridizing iterated local search with a greedy randomized adaptive search procedure. On a large test set, an average run has a score gap of only 5.19% with known high quality solutions, using 1.5 seconds of computational time. For 32% of the test instances, the known high quality solution was found or improved. This solution method also performs well on test instances of the TOPTW, the selective vehicle routing problem with time windows, and the MC-TOP-TW. A sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in the parameter settings. [ABSTRACT FROM AUTHOR]

Long-haul carriers must comply with various safety rules which are rarely taken into account in models and algorithms for vehicle routing problems. In this paper, we consider the rules on truck driver safety during long-haul trips in the United States. The problem under study has two dominant features: a routing component that consists of determining the sequence of customers visited by each vehicle and a scheduling component that consists of planning the rest periods and the service time of each customer. We have developed different scheduling algorithms embedded within a tabu search heuristic. The overall solution methods were tested on modified Solomon instances, and the computational results confirm the benefits of using a sophisticated scheduling procedure when planning long-haul transportation. [ABSTRACT FROM AUTHOR]

The pickup and delivery problem with time windows (PDPTW) is a generalization of the vehicle routing problem with time windows. In the PDPTW, a set of identical vehicles located at a central depot must be optimally routed to service a set of transportation requests subject to capacity, time window, pairing, and precedence constraints. In this paper, we present a new exact algorithm for the PDPTW based on a set-partitioning-like integer formulation, and we describe a bounding procedure that finds a near-optimal dual solution of the LP-relaxation of the formulation by combining two dual ascent heuristics and a cut-and-column generation procedure. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between a known upper bound and the lower bound achieved. If the resulting problem has moderate size, it is solved by an integer programming solver; otherwise, a branch-and-cut-and-price algorithm is used to close the integrality gap. Extensive computational results over the main instances from the literature show the effectiveness of the proposed exact method. [ABSTRACT FROM AUTHOR]

This paper considers a dynamic and stochastic routing problem in which information about customer locations and probabilistic information about future service requests are used to maximize the expected number of customers served by a single uncapacitated vehicle. The problem is modeled as a Markov decision process, and analytical results on the structure of the optimal policy are derived. For the case of a single dynamic customer, we completely characterize the optimal policy. Using the analytical results, we propose a real-time heuristic and demonstrate its effectiveness compared with a series of other intuitively appealing heuristics. We also use computational tests to determine the heuristic value of knowing both customer locations and probabilistic information about future service requests. [ABSTRACT FROM AUTHOR]

In this paper we introduce the problem of shunting passenger train units in a railway station. Shunting occurs whenever train units are temporarily not needed to operate a given timetable. We discuss several aspects of this problem and focus on two subproblems. We propose mathematical models for the problem and both subproblems, one of which is solved with a solution method based on column generation. Furthermore, we introduce a new efficient and speedy solution technique for pricing problems in column generation algorithms. Finally, we present computational results based on real-life instances from Netherlands Railways. [ABSTRACT FROM AUTHOR]

This paper presents a survey of the research on the vehicle routing problem with time windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval, all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solomon's benchmark test problems are represented and analyzed. Moreover,we discuss how heuristic methods should be evaluated and propose using the concept of Pareto optimality in the comparison of different heuristic approaches. The metaheuristic methods are described in the second part of this article. [ABSTRACT FROM AUTHOR]

The vehicle routing problem with time windows is a hard combinatorial optimization problem that has received considerable attention in the last decades. This paper proposes a two-stage hybrid algorithm for this transportation problem. The algorithm first minimizes the number of vehicles, using simulated annealing. It then minimizes travel cost by using a large neighborhood search that may relocate a large number of customers. Experimental results demonstrate the effectiveness of the algorithm, which has improved 10 (17%) of the 56 best published solutions to the Solomon benchmarks, while matching or improving the best solutions in 46 problems (82%). More important perhaps,the algorithm is shown to be very robust. With a fixed configuration of its parameters, it returns either the best published solutions (or improvements thereof) or solutions very close in quality on all Solomon benchmarks. Very preliminary results on the extended Solomon benchmarks are also given. [ABSTRACT FROM AUTHOR]

We consider the problem of shipping several products from an origin to a destination when a discrete set of shipping frequencies is available, in such a way that the sum of the transportation and inventory costs is minimized. This problem, which is known to be NP-hard, has applications in transportation planning and in location analysis. In this paper we derive dominance rules for the problem solutions that allow a tightening of the bounds on the problem variables and improve the efficiency of a known branch-and-bound algorithm. Moreover, we present some heuristics and compare them with two different modifications of an EOQ-type algorithm for the solution of the problem with continuous frequencies. [ABSTRACT FROM AUTHOR]

The importance of historical travel demand has been well recognized by transportation researchers and practitioners. This paper presents a new nonlinear demand estimator that can be applied in both ground and air transportation. The estimator is formulated such that the distribution of the estimated demand follows a nested logit model. To solve the demand estimator, we develop an exact solution algorithm, which maximizes its dual problem sequentially along unit directions and keeps some of the first-order optimality conditions satisfied for the estimator. We investigate the convergence of the algorithm. We prove that all of the accumulation points produced by the solution algorithm satisfy some optimality conditions. A large example (a real U.S. network), which contains 66,767 origin-destination pairs, is presented. [ABSTRACT FROM AUTHOR]

This paper proposes a new mixed integer programming formulation and branch and cut (BC) algorithm to solve the dial-a-ride problem (DARP). The DARP is a route-planning problem where several vehicles must serve a set of customers, each of which has a pickup and delivery location, and includes time window and ride time constraints. We develop "restricted fragments," which are select segments of routes that can represent any DARP route. We show how to enumerate these restricted fragments and prove results on domination between them. The formulation we propose is solved with a BC algorithm, which includes new valid inequalities specific to our restricted fragment formulation. The algorithm is benchmarked on existing and new instances, solving nine existing instances to optimality for the first time. In comparison with current state-of-the-art methods, run times are reduced between one and two orders of magnitude on large instances. [ABSTRACT FROM AUTHOR]

The classic problem of finding the shortest path over a network has been the target of many research efforts over the years. These research efforts have resulted in a number of different algorithms and a considerable amount of empirical findings with respect to performance. Unfortunately, prior research does not provide a clear direction for choosing an algorithm when one faces the problem of computing shortest paths on real road networks. Most of the computational testing on shortest path algorithms has been based on randomly generated networks, which may not have the characteristics of real road networks. In this paper, we provide an objective evaluation of 15 shortest path algorithms using a variety of real road networks. Based on the evaluation, a set of recommended algorithms for computing shortest paths on real road networks is identified. This evaluation should be particularly useful to researchers and practitioners in operations research, management science, transportation, and Geographic Information Systems. [ABSTRACT FROM AUTHOR]

Network design problems have been widely investigated in the literature. In this paper, we study one such design problem, known as the Optimum Communication Spanning Tree (OCST) problem. We develop an exact algorithm based on the branch and bound approach and a heuristic algorithm to solve the problem. The branch and bound algorithm uses the lower planes recently developed by the authors. Reoptimization of subproblems is extensively used to reduce computation. The heuristic algorithm is a two-phase algorithm: tree-building algorithm and tree-improvement algorithm. These algorithms have been tested on randomly generated Euclidean and non-Euclidean problems and results of these investigations are described. The branch and bound algorithm is able to solve moderately large sized problems in reasonable time. The two-phase heuristic algorithm has produced excellent results by providing optimal solutions for all the problems tested. Further, it is capable of solving problems of size 100 nodes and 1,000 arcs in about 30 seconds on DEC 10. [ABSTRACT FROM AUTHOR]

This study reviews, in two parts, the formulation, interpretation, and solution methodology of the traffic assignment pro blem with elastic demands, originally described by Beckmann, McGuire and Winsten. This paper (Part I) defines the different possible modes of traffic assignment in a network and identifies the economic rationales of the associated extremism formulations. The accompanying paper (Part II) examines algorithmic approaches for calculating the resulting flow patterns. The assignment pro blem is characterized as an interaction between users and operators of the transportation system, analogous to the interaction between consumers and producers in the marketplace. The notions of "user-optimization" and "system-optimization" thus acquire congruent interpretations, expressed by a systemwide maximization objective. [ABSTRACT FROM AUTHOR]

This paper defines a problem type, called the transportation-location problem, that can be considered a generalization of the Hitchcock transportation problem in which, in addition to seeking the amounts to be shipped from origins to destinations, it is also necessary to find, at the same time, the optimal locations of these sources with respect to a fixed and known set of destinations. This new problem is characterized mathematically, and exact and approximate methods are presented for its solution. [ABSTRACT FROM AUTHOR]

This paper attempts to present the major methods, successful or interesting uses, and computational experience relating to integer or discrete programming problems. Included are descriptions of general algorithms for solving linear programs in integers, as well as some special purpose algorithms for use on highly structured problems. This reflects a belief, on the author's part, that various clever methods of enumeration and other specialized approaches are the most efficacious means existent by which to obtain solutions to practical problems. A serious try at gathering computational experience has been made—but facts are difficult to uncover. The paper is written with intent to enable readers to read selected sections without having to read the whole. [ABSTRACT FROM AUTHOR]

The topology of the Generalized Transportation Problem, at the end of each iteration of the stepping-stone method, is characterized by a variable number of loops to which are attached multiple branched side chains or trees. An efficient computer representation of this structure and methods for updating it are described in this paper. [ABSTRACT FROM AUTHOR]

In North America, thousands of locomotives operating in the railroad network require various types of mechanical work every day. This work may be unscheduled, periodic, or on demand and could be conducted at either a fixed facility or a movable facility. Each facility is characterized by the type of work it can provide. The long-term infrastructure planning of these facilities is vital to the efficiency of the railroad. In this paper, we develop a large-scale mixed-integer mathematical model for infrastructure planning. The model integrates and optimizes decisions about (1) Locations, capabilities, and capacities of fixed facilities, (2) Home locations and routing plans of movable facilities, and (3) Assignments of locomotive work demands to facilities. We propose a decomposition-based heuristic solution framework consisting of several underlying algorithms to solve this large-scale optimization model. Computational results on numerous scenario studies using field data from the railroad industry show that the proposed model and algorithms are capable of providing solutions that are significantly superior to the current practice. The successful application of our methodology to real-world railroad planning has clearly demonstrated the substantial cost-saving benefits of our models on infrastructure planning solutions. [ABSTRACT FROM AUTHOR]

In rail-based intermodal freight operations, full containers are moved by truck from shipper locations to rail ramps, transported via train to destination ramps, and then moved again by truck to consignee locations. We commonly refer to the roadway portions of this activity as dray operations. In a large metropolitan hub area, such as Chicago or Los Angeles, this drayage activity may involve several hundred drivers and up to 500 daily container moves to or from several distinct rail ramps. Both cost and environmental considerations drive the need to maximize driver productivity and minimize the time and miles not directly associated with moving loaded containers to or from rail ramps. In this paper, we describe a solution to this problem using a set-partitioning formulation and column-generation heuristic and report on a large-scale implementation. We focus on real-world implementation details that include (1) fast solve times to support near-real-time re-solving in the face of constantly changing data, (2) adjustments to account for traffic congestion and other operational considerations, and (3) integration with a commercial transportation management system to provide real-time data to the optimizer and to send solution recommendations to a driver-assignment process. [ABSTRACT FROM AUTHOR]

Air traffic management measures comprise tactical operating procedures to minimize delay costs and strategic scheduling interventions to control overcapacity scheduling. Although interdependent, these problems have been treated in isolation. This paper proposes an integrated model of scheduling and operations in airport networks that jointly optimizes scheduling interventions and ground-holding operations across airports networks under operating uncertainty. It is formulated as a two-stage stochastic program with integer recourse. To solve it, we develop an original decomposition algorithm with provable solution quality guarantees. The algorithm relies on new optimality cuts—dual integer cuts—that leverage the reduced costs of the dual linear programming relaxation of the second-stage problem. The algorithm also incorporates neighborhood constraints, which shift from exploration to exploitation at later stages. We also use a scenario generation approach to construct representative scenarios from historical records of operations—using integer programming. Computational experiments show that our algorithm yields near-optimal solutions for the entire U.S. National Airspace System network. Ultimately, the proposed approach enhances airport demand management models through scale integration (by capturing network-wide interdependencies) and scope integration (by capturing interdependencies between scheduling and operations). [ABSTRACT FROM AUTHOR]

Vehicle scheduling is a central problem in transportation. As railways and the airspace become increasingly congested, it is crucial to develop mathematical tools to better schedule trains and airplanes off-line (timetabling) and online (dispatching). These traffic-management problems can be modeled as job-shop scheduling problems, which, in turn, can be solved using mixed-integer linear programming (MILP). The two most successful and widespread formulations in the past decades are the big-M and the time-indexed methods, each with its strengths and weaknesses. However, there have been few advancements in either approach in recent years. In this paper, we introduce an alternative formulation, obtained by strengthening and lifting the Benders' reformulation of a natural initial formulation. This new approach improves performances on our real-life test bed and opens up interesting research directions. A central problem in traffic management is that of scheduling the movements of vehicles so as to minimize the cost of the schedule. It arises in important applications such as train timetabling, rescheduling, delay and disruption management, airplane surface routing, runway scheduling, air-traffic control, and more. This problem can be modeled as a job-shop scheduling problem. We introduce a new mixed-integer linear program (MILP) formulation for job-shop scheduling, which is an alternative to classical approaches, namely, big-M and time-indexed formulations. It does not make use of artificially large coefficients, and its constraints correspond to basic graph structures, such as paths, cycles, and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders' reformulation. Tests on a large set of real-life instances from train rescheduling show that the new approach performs on average better than our previous approaches based on big-M formulations and particularly better on a class of instances with nonconvex costs very common in the practice. [ABSTRACT FROM AUTHOR]

The pickup and delivery problem (PDP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the PDP where requests can change vehicle during their trip. The transfer is made at specific locations called "transfer points." The corresponding problem is called the pickup and delivery problem with transfers (PDPT). Solving the PDPT leads to new modeling and algorithmic difficulties. We propose new heuristics capable of efficiently inserting requests through transfer points. These heuristics are embedded into an adaptive large neighborhood search. We evaluate the method on generated instances and apply it to the transportation of people with disabilities. On these real-life instances we show that the introduction of transfer points can bring significant improvements (up to 9%) to the value of the objective function. [ABSTRACT FROM AUTHOR]

The cell-transmission model-based single-destination system optimal dynamic traffic assignment problem proposed by Ziliaskopoulos was mostly solved by standard linear programming (LP) methods, e.g., simplex and interior point methods, which produce link-based flows involving vehicle-holding phenomenon. In this paper we present a network flow algorithm for this problem. We show that the problem is equivalent to the earliest arrival flow and then solve the earliest arrival flow on a time-expanded network. In particular, a scaled flow scheme is proposed to deal with the situation in which the ratio of backward wave speed to forward wave speed is less than one. The proposed algorithm produces path-based flows exhibiting realistic nonvehicle-holding properties. Complexity and numerical analyses show that the algorithm runs more efficiently than LP. [ABSTRACT FROM AUTHOR]

This paper addresses the split-delivery vehicle routing problem with time windows (SDVRPTW) that consists of determining least-cost vehicle routes to service a set of customer demands while respecting vehicle capacity and customer time windows. The demand of each customer can be fulfilled by several vehicles. For solving this problem, we propose a new exact branch-and- price-and-cut method, where the column generation subproblem is a resource-constrained elementary shortest-path problem combined with the linear relaxation of a bounded knapsack problem. Each generated column is associated with a feasible route and a compatible delivery pattern. As opposed to existing branch-and-price methods for the SDVRPTW or its variant without time windows, integrality requirements in the integer master problem are not imposed on the variables generated dynamically, but rather on additional variables. An ad hoc label-setting algorithm is developed for solving the subproblem. Computational results show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Each major US railroad ships millions of cars over its network annually. To reduce the intermediate handlings of shipments as they travel over the railroad network, a set of shipments is classified (or grouped together) at a railroad yard to create a block. The railroad blocking problem is to identify this classification plan for all shipments at all yards in the network to minimize the total shipment cost, i.e., to create a blocking plan. The railroad blocking problem is a very large-scale, multicommodity, flow-network-design and routing problem with billions of decision variables. Its size and mathematical difficulty preclude solving it using any commercial software package. We developed an algorithm using an emerging technique known as very large-scale neighborhood (VLSN) search that is able to solve the problem to near optimality using one to two hours of computer time on a standard workstation computer. This algorithm can also handle a variety of practical and business constraints that are necessary for implementing a solution. When we applied this algorithm to the data that several railroads provided us, the computational results were excellent. Three Class I railroad companies (a Class I railroad, as defined by the Association of American Railroads, has an operating revenue exceeding $319.3 million) in the United States--CSX Transportation, Norfolk Southern Corporation, and Burlington Northern and Santa Fe Railway--used it in developing their operating plans. Two US Class I railroads have also licensed it for regular use in developing their operating plans, and other railroads are showing considerable interest. We expect this algorithm to become an industry standard for freight railroads worldwide. In this paper, we outline our algorithm, show the computational results we received using real data, and describe areas for future research. [ABSTRACT FROM AUTHOR]

This paper proposes an activity-based methodology for representing the allocation of time to discretionary activities during their programming and scheduling, based on the premise that both phases are to be considered contextually and two aspects of the same decision process. The aim of this work is to extend the treatment of utility maximization associated with carrying out two activities to J activities, so as to be able to segregate the time spent traveling from the total amount of time dedicated to out-of-home activities. The global structure of the model takes the form of a nested Tobit, particularly suited for reproducing a sequence of coupled choices. The first choice concerns dividing up overall discretionary time between activities inside and outside the home, then the second choice, subordinate to the first, involves rebudgeting the time between in- and out-of-home activities and trips. Thus the proposed model enables us to analyze the effects that each explicative variable exerts on trips segregated from activities outside the home and, last, during demand forecasting, the direct consequences of allocating discretionary time to trips following changes to an individual's time budget. A database created from a large-scale time-use survey (ISTAT 1988-1991) has been used for calibrating the model coefficients. [ABSTRACT FROM AUTHOR]

In the dial-a-ride problem, users formulate requests for transportation from a specific origin to a specific destination. Transportation is carried out by vehicles providing a shared service. The problem consists of designing a set of minimum cost vehicle routes satisfying capacity, duration, time window, pairing, precedence, and ride-time constraints. This paper introduces a mixed-integer programming formulation of the problem and a branch-and-cut algorithm. The algorithm uses new valid inequalities for the dial-a-ride problem as well as known valid inequalities for the traveling salesman, the vehicle routing, and the pick-up and delivery problems. Computational experiments performed on randomly generated instances show that the proposed approach can be used to solve small to medium-size instances. [ABSTRACT FROM AUTHOR]

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

The general routing problem (GRP) is the problem of finding a minimum length tour, visiting a number of specified vertices and edges in an undirected graph. In this paper, we describe how the well-known 2-opt and 3-opt local search procedures for node routing problems can be adapted to solve arc and general routing problems successfully. Two forms of the 2-opt and 3-opt approaches are applied to the GRP. The first version is similar to the conventional approach for the traveling salesman problem; the second version includes a dynamic programming procedure and explores a larger neighborhood at the expense of higher running times. Extensive computational tests, including ones on larger instances than previously reported in the arc routing literature, are performed with variants of both algorithms. In combination with the guided local search metaheuristic and the mechanisms of marking and neighbor lists, the procedures systematically detect optimal or high-quality solutions within limited computation time. [ABSTRACT FROM AUTHOR]

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

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

We analyze the problem faced by companies that rely on TL (Truckload) and LTL (Less than Truckload) carriers for the distribution of products across their supply chain. Our goal is to design simple inventory policies and transportation strategies to satisfy time- varying demands over a finite horizon, while minimizing systemwide cost by taking advantage of quantity discounts in the transportation cost structures. For this purpose, we study the cost effectiveness of restricting the inventory policies to the class of zero-inventory-ordering (ZIO) policies in a single-warehouse multiretailer scenario in which the warehouse serves as a cross-dock facility. In particular, we demonstrate that there exists a ZIO inventory policy whose total inventory and transportation cost is no more than 4/3 (5.6/4.6 if transportation costs are stationary)times the optimal cost. However, finding the best ZIO policy is an NP-hard problem as well.Thus, we propose two algorithms to find an effective ZIO policy: An exact algorithm whose running time is polynomial for any fixed number of retailers, and a linear-programming-based heuristic whose effectiveness is demonstrated in a series of computational experiments. Finally, we extend the worst-case results developed in this paper to systems in which the warehouse does hold inventory. [ABSTRACT FROM AUTHOR]

Placement of inspection stations is a common task in transportation and communication networks. In this paper, two categories of problems involving placement of inspection stations are studied. The first category deals with the selection of inspection stations along a given path from an origin to a destination. The second considers simultaneous selection of both a path and inspection stations along that path. We formulate these problems under a variety of minimization objectives such as the maximum gap between two consecutive inspection stations, the expected penalty cost of failure along the path, and the total inspection cost. Our results include efficient algorithms for many formulations and complexity results as well as fully polynomial approximation schemes for other formulations. When considering cost objectives, we identify a core problem and show that the complexity of many formulations is directly related to the complexity of the core problem. [ABSTRACT FROM AUTHOR]

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

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

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

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

This paper presents a theory of traffic equilibrium which involves responsive signal control policies; in this theory drivers' route choices and the control policy's choice of green times are treated in a symmetrical manner. The central theme of the paper is the iterative optimization assignment algorithm. This algorithm may be considered as a means of calculating equilibria which are consistent with a given responsive control policy. But it may also be regarded as a highly idealized model of the day to day dynamics of drivers' route choices when a responsive signal setting policy is employed; on "day" 1 the signals are held fixed and drivers settle down to an equilibrium flow pattern, on "day 2" the flow pattern is held fixed and the signals are updated according to the control policy for the fixed flow pattern, on "day" 3 the signals are held fixed and drivers settle down to an equilibrium flow pattern.... We state natural but strong conditions on the responsive control policy which guarantee that this algorithm is bound to converge to a convex set of (flow, control) pairs such that (i) the flow is a user equilibrium and (ii) the control parameters satisfy the responsive control policy; and we give a proof of convergence under these conditions--we do not seek to minimize total travel cost. Our conditions involve the delay or cost formula used; with the BPR cost formula, modified in a natural way to allow for green times, the traditional policy of choosing control parameters which minimize delay for the observed traffic pattern does satisfy these conditions in full. However, with Webster's delay formula traditional control policies are a long way... [ABSTRACT FROM AUTHOR]

Modeling of transportation systems must invariably balance behavioral richness and computational tractability. In this paper, we develop a transportation equilibrium model and an algorithm for the simultaneous prediction of trip generation, trip distribution, modal split, and trip assignment on large-scale networks. The model achieves a practical compromise between behavioral and computational aspects of modeling the problem. It is formulated as an equivalent convex optimization problem, yet it is behaviorally richer than other models that can be cast as equivalent convex programs. Although the model is not as behaviorally rich as the most general equilibrium models, it has computational advantages. The applications reported in this paper of the model to real systems, i.e., the intercity transport network of Egypt and the urban transportation network of Austin, Texas, illustrate the computational attractiveness of the approach. These results indicate that equivalent optimization formulations are not as restrictive as previously thought, and hence, the equivalent convex programming approach for modeling and predicting equilibrium on transportation systems remains a viable and fruitful avenue for future consideration. [ABSTRACT FROM AUTHOR]

Numerous transportation applications as diverse as capital investment decision- making, vehicle fleet planning, and traffic light signal setting all involve some form of (discrete choice) network design. In this paper, we review some of the uses and limitations of integer programming-based approaches to network design, and describe several discrete and continuous choice models and algorithms. Our objectives are threefold--to provide a unifying view for synthesizing many network design models, to propose a unifying framework for deriving many network design algorithms, and to summarize computational experience in solving design problems. We also show that many of the most celebrated combinatorial problems that arise in transportation planning are specializations and variations of a generic design model. Consequently, the network design concepts described in this paper have great potential application in a wide range of problem settings. [ABSTRACT FROM AUTHOR]

This paper discusses a family of general link cost functions that can be used to model multimodal transportation network equilibrium problems. The family includes as a special case the currently favored family of monotonically increasing functions but does not necessarily have to have a symmetric or semi-definite Jacobian. In this way multimodal networks can be modeled somewhat more realistically. The paper also allows stochastic link costs for some or all the links and modes. It is shown that under mild conditions the equilibrium exists and is unique, but more importantly, that there is a simple, single-equilibrium algorithm that is proven to converge for stochastic networks with the link cost family discussed in the paper. Finally, it is pointed out that many variable demand problems also exhibit unique equilibria, but that there are some which do not. An example which illustrates this fact is given. [ABSTRACT FROM AUTHOR]