Search

In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called no-split no-merge requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving the unsplittable network flow problems with standard mixed-integer programming formulations is computationally difficult due to the large number of binary variables needed to determine matching pairs between incoming and outgoing arcs of nodes with no-split no-merge constraint. In this paper, we study a stochastic variant of the unit train scheduling problem where the demand is uncertain. We develop a novel decision diagram (DD)-based framework that decomposes the underlying two-stage formulation into a master problem that contains the combinatorial requirements and a subproblem that models a continuous network flow problem. The master problem is modeled by a DD in a transformed space of variables with a smaller dimension, leading to a substantial improvement in solution time. Similar to the Benders decomposition technique, the subproblems output cutting planes that are used to refine the master DD. Computational experiments show a significant improvement in solution time of the DD framework compared with that of standard methods. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the Iowa Energy Center [Grant 20IEC005]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.1194. [ABSTRACT FROM AUTHOR]

This paper extends the dynamically formulated hidden Markov models to a high-order hidden Markov model (HO-HMM) formulation. In the HO-HMM, the Markovian assumption that the future states (interpreted as the states of preferences or attitudes) depend only on the current state has been relaxed. Instead, the HO-HMM generalizes that the future states will depend on a number of states occurring beforehand. This paper develops the theoretical formulation of a HO-HMM framework. A recursive algorithm of likelihood computation is derived for model estimation. The algorithm significantly reduces the complexity of estimation and ensures the applicability of high-order hidden Markov modeling. The proposed methodology is further demonstrated on a vehicle ownership choice application using Puget Sound Transportation Panel data coupled with a few supplementary data sources. Long-term life-cycle stage changes in households are used as proxies for the high-order Markov transitions in car ownership hidden states. Results indicate that the HO-HMM has superior explanatory power in fitting longitudinal data. [ABSTRACT FROM AUTHOR]

The article introduces the special issue of the periodical 'Transportation Science' which features aviation operations research, commemorating a hundred years of aviation. One hundred years ago, Orville Wright piloted a gasoline-powered aircraft down a single iron track in North Carolina. This flight represented the result of research and experiments by two bicycle makers, Wilbur and Orville Wright. The Wright brothers used the control of a bicycle as their model, noting that one must constantly adapt weight distribution, steering, and speed to keep the bike upright during travel. Therefore, in many respects the Wright brothers' achievement can be viewed as a success for systems engineering. Operations research has played a fundamental role in the development of these systems and transport systems have played a leading role in fostering the development of operations research. In particular, the airline industry pioneered the development of yield management. The strong link between operations research and aviation makes it very natural and perhaps mandatory to commemorate the Wright brothers' first flight with a special issue of 'Transportation Science.' The first paper in the issue provides an overview of research in aviation operations research. Another addresses schedule recovery in the event of the closure of a hub airport, while two papers solve problems faced by airlines.

Public transportation systems in metropolitan areas carry a high density of daily traffic, heterogeneously distributed, and exposed to the negative consequences derived from service disruptions. Breakdowns, accidents, strikes, etc., require on-line operation adjustments to address these incidents and thus reduce their side effects, such as passenger extra-waiting times, complaints, potential operational dangers, etc. The Vehicle Rescheduling Problem consists of defining a new schedule for a set of previously scheduled trips, given that one/several trips cannot be carried out. This paper addresses the rescheduling problem in a transit line that has suffered a fleet size reduction (also denoted as Reduced Fleet Rescheduling Problem). We present different modeling possibilities depending on the assumptions that must be included in the modelization and we show that the problem can be rapidly solved using a reformulation that will be proven to have the integrality property. We test our results in a testbed of random instances outperforming previous results in the literature. We also include a real-world case of the commuter trains of Madrid, Spain to illustrate our solutions. [ABSTRACT FROM AUTHOR]

A novel analysis framework for the spatial aspects of car travel, measured by vehicle miles traveled (VMT), is introduced in this paper. The specification of a dynamic spatial Durbin model enables the analysis of VMT spatial spillovers and diffusion between neighboring areas in the short and long run. The framework is further developed to capture and introduce to a spatial setting potential asymmetry and hysteresis that can reflect reference dependence and habits. A panel data set is compiled at the subregional level, based on official car mileage recordings in England and Wales. In addition to the inelastic long-run responses of VMT to fuel price (-0:124) and income (0.116) changes, the results illustrate asymmetries and hysteresis in price elasticities with a significant spatial component. The impact magnitude on VMT from a number of factors, such as alternative fuel use, fuel deserts in rural areas, and road network and car fleet characteristics, is also estimated. The results are consistent with the car use saturation hypothesis through the positive impact of motorization rate to VMT. The negative effect of public transport infrastructure on car travel is only significant in the spatial models. The paper demonstrates the applicability and importance of spatial econometrics in transport research. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of finding the optimal routing policies with only trajectory information in a stochastic time-dependent network where all link travel times are temporally and spatially correlated. Two equivalent definitions are given for trajectory-adaptive routing policy. The first definition follows the mapping definition in a series of previous studies, where the trajectory information is included in the state variable. With that definition, any subpolicy of an optimal routing policy must also be optimal, and the algorithm developed in previous studies could serve as an exact solution, but the nature of the definition that trajectory information is included in the state variable determines that the number of states is prohibitively huge. Therefore, a second definition is given as a recursive definition, where the trajectory information is not included in the state variable. It is shown that, with the second definition, a subpolicy of an optimal/nondominated routing policy is not necessarily optimal/nondominated, but any subpolicy of a pure routing policy must also be pure which is a new property defined based on nondominance. An exact algorithm is designed to find optimal trajectory-adaptive routing policies based on the aforementioned property of pure routing policy. A comparison is made between the optimal trajectory-adaptive routing policies and the optimal paths in the same test networks to investigate the benefit of being adaptive. The results show that the benefit of being adaptive to trajectory information is more significant with a higher risk aversion, a higher correlation, and/or a larger network. [ABSTRACT FROM AUTHOR]

Logistics is a cost sensitive industry with large and fast growing routing networks. In this paper we devise a computational, robust optimization method for the strategic routing decisions of a logistics' customer, i.e., a company that uses the services of different freight forwarders to meet its transportation demands between several sources, sinks, and hubs. The costs of such transports are determined by tariff systems that typically show economies of scale and reward the consolidation of goods that complement each other in properties relevant for transport, such as weight and volume. In the strategic planning phase, routes and hubs have to be chosen roughly one year ahead, in particular, before the actual demand is known. Our method anticipates the fluctuation of demands by minimizing the worst-case cost over a restricted scenario set. The combination of a realistic cost function, a robust modeling of uncertainty, and large-scale networks leads to highly intractable models. We show that the corresponding adversary problem is NP-hard. To nevertheless find solutions for real instances with very good worst-case cost we derive a carefully relaxed and simplified mixed-integer linear program that solves well for large instances because of its powerful linear programming relaxation. We test the method for real-world instances. The results show that robust optimization can significantly reduce worst-case cost. Furthermore, we derive from our method two heuristic techniques to solve even larger networks and report on the corresponding computational results. Neglecting the typical uncertainty about demand values can cause significant cost in logistic routing problems. This paper provides for a practical method to avoid such costs. [ABSTRACT FROM AUTHOR]

In this paper, we describe a computerized procedure for scheduling mass transit crews and vehicles. The procedure differs from previous methods in that rather than first scheduling vehicles and then crews, it schedules vehicles and crews simultaneously. Several of the subproblems are solved as matching problems on graphs. A computational test of this procedure using a database from the Baltimore Metropolitan Transit Authority has produced solutions of lower cost than those used by the transit authority. [ABSTRACT FROM AUTHOR]

The article offers information on International Workshop on Freight Transportation and Logistics that was held in Mykonos, Greece on May 2012. Topics discussed include contributions through methodological developments and innovative applications, passenger-oriented transportation systems and revenue management for freight transportation, and integer programming formulation and a heuristic approach method.

Transportation agencies often resort to the use of traffic simulation models to evaluate the impacts of changes in network design or network operations. They often have multiple traffic simulation tools that cover the network area where changes are to be made. These multiple simulators may differ in their modeling assumptions (e.g., macroscopic versus microscopic), in their reliability (e.g., quality of their calibration), as well as in their modeling scale (e.g., city-scale versus regional-scale). The choice of which simulation model to rely on, let alone of how to combine their use, is intricate. A larger-scale model may, for instance, capture more accurately the local-global interactions; yet may do so at a greater computational cost. This paper proposes an optimization framework that enables multiple simulation models to be jointly and efficiently used to address continuous urban transportation optimization problems. We propose a simulation-based optimization algorithm that embeds information from both a high-accuracy low-efficiency simulator and a low-accuracy high-efficiency simulator. At every iteration, the algorithm decides which simulator to evaluate. This decision is based on an analytical approximation of the accuracy loss as a result of running the lower-accuracy model. We formulate an analytical expression that is based on a differentiable and computationally efficient to evaluate traffic assignment model. We evaluate the performance of the algorithm with a traffic signal control problem on both a small network and a city network. We show that the proposed algorithm identifies signal plans with excellent performance, and can do so at a significantly lower computational cost than when systematically running the high-accuracy simulator. The proposed methodology contributes to enable large-scale high-resolution traffic simulation models to be used efficiently for simulation-based optimization. More broadly, it enables the use of multiple simulation models that may differ, for instance, in their scale, their resolution, or their computational costs, to be used jointly for optimization. [ABSTRACT FROM AUTHOR]

In the paper by Cominetti and Correa (2001) [Common-lines and passenger assignment in congested transit I networks. Transportation Sci. 35(3):250-267], an extension to the common-lines problem for general multidestination networks under congestion is analyzed. Their transit equilibrium assignment model allows for a full representation of congestion effects caused by the variation of effective frequencies experienced by passengers at transit stops. This model is the ?rst to address these characteristics consistently with the concept of strategies. In a subsequent paper by Cepeda, Cominetti, and Florian (2006) [A frequency-based assignment model for congested transit networks with strict capacity constraints: Characterization and computation of equilibria. Transportation Res. 40B(6):437-459], the computation of equilibrium is performed heuristically by the minimization of a gap function, using the method of successive averages. In this paper, a reformulation of this congested transit equilibrium assignment model is performed, demonstrating that the problem can be expressed as an equivalent variational inequality. The case of strictly capacitated transit networks is explored under the scope of this new reformulation, and new, broader conditions for the existence of solutions to this congested transit assignment model are determined. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of convergence to equilibrium in dynamic traffic assignment. Within-day time is considered to be a continuous variable, so that traffic flows and costs are functions of within-day time. Flow propagates along routes connecting origin-destination (OD) pairs with the demand for travel between each OD pair considered to be rigid (fixed from day to day although it can vary within day). Day-to-day time is also modelled as continuous with the day-to-day dynamical system derived naturally from the usual dynamical user equilibrium (DUE) condition. This paper focuses on the bottleneck model, which has deterministic vertical queueing at bottleneck link exits when flow exceeds capacity. A new property called decay monotonicity is introduced. The link delay (and hence link cost) function is shown to be a decay monotone function of link flow provided that the link capacity is continuously differentiable and positive. In a restricted version of the single bottleneck per route case, it is shown that link cost decay monotonicity implies route cost decay monotonicity. Decay monotonicity of the route cost function is shown to be sufficient for convergence to equilibrium of the dynamical system. [ABSTRACT FROM AUTHOR]

Railway rolling stock is one of the most significant cost components for operators of passenger trains. The efficient circulation of rolling stock is therefore one of the main objectives pursued in practice. This paper focuses on the determination of appropriate numbers of train units of different types together with their efficient circulation on a single line. To utilize the train units on this line in an efficient way, they are coupled to or uncoupled from the trains in certain stations according to the passengers' seat demand in peak and off-peak hours. Because coupling and uncoupling train units must respect specific rules related to the shunting possibilities in the stations, it is important to take into account the order of the train units in the trains. This aspect strongly increases the complexity of the rolling stock circulation problem. This paper presents a solution approach based on an integer multicommodity flow model with several additional constraints related to the shunting processes at the stations. The approach is applied to a real-life case study based on the timetable of NS Reizigers, the main Dutch operator of passenger trains. [ABSTRACT FROM AUTHOR]

With the increasing availability of real-time information and communication systems in logistics, the need for appropriate planning algorithms, which make use of this technology, arises. Customers in transport markets increasingly expect quicker and more flexible fulfillment of their orders, especially in the electronic marketplace. This paper considers a dynamic routing system that dispatches a fleet of vehicles according to customer orders arriving at random during the planning period. Each customer order requires a transport from a pickup location to a delivery location in a given time window. The system disposes of online communication with all drivers and customers and, in addition, disposes of online information on travel times from a traffic management center. This paper presents a planning framework for this situation which, to our knowledge, has not yet been addressed in the literature. It then describes three routing procedures for event-based dispatching, which differ in the length of the planning horizon per event. We focus on the use of dynamic travel time information, which requires dynamic shortest path calculations. The procedures are tested and compared using real-life data of an urban traffic management center and a logistics service provider. [ABSTRACT FROM AUTHOR]

In this paper, we consider empty freight car distribution in a scheduled railway system. We analyze the cost structure for the repositioning of empty cars, and conclude that the distribution cost shows an economy-of-scale behavior. In addition to the cost proportional to the number of cars sent from origin to destination, there is a cost related to car-handling operations at yards, which depends on the number of car groups that are handled. Thus, if we can find a transportation pattern in which fewer but larger groups of cars are built, the total distribution cost can be decreased. The objective of the paper is to propose an optimization model that explicitly takes this economy-of-scale effect into account. We use a time-dependent network to describe the possible car movements in time and space, and show how this network can be transformed into a network with fixed costs on links representing movements of cars with identical origin and destination terminals. The resulting optimization model is a capacitated network design model, where each capacity constraint limits the flow on several arcs. We describe a tabu heuristic for solving the model, and present computational results. [ABSTRACT FROM AUTHOR]

The objective of this paper is to review the current status of ship routing and scheduling. We focus on literature published during the last decade. Because routing and scheduling problems are closely related to many other fleet planning problems, we have divided this review into several parts. We start at the strategic fleet planning level and discuss the design of fleets and sea transport systems. We continue with the tactical and operational fleet planning level and consider problems that comprise various ship routing and scheduling aspects. Here, we separately discuss the different modes of operations: industrial, tramp, and liner shipping. Finally, we take a glimpse at naval applications and other related problems that do not naturally fall into these categories. The paper also presents some perspectives regarding future developments and use of optimization-based decision-support systems for ship routing and scheduling. Several of the trends indicate both accelerating needs for and benefits from such systems and, hopefully, this paper will stimulate further research in this area. [ABSTRACT FROM AUTHOR]

The inventory routing problem considered in this paper is concerned with the repeated distribution of a commodity, such as heating oil, over a long period of time to a large number of customers. The problem involves a central depot as well as various satellite facilities which the drivers can visit during their shift to refill their vehicles. The customers maintain a local inventory of the commodity. Their consumption varies daily and cannot be predicted deterministically. In case of a stockout, a direct delivery is made and a penalty cost is incurred. In this paper, we present incremental cost approximations to be used in a rolling horizon framework for the problem of minimizing the total expected annual delivery costs. [ABSTRACT FROM AUTHOR]

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

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 proposes a methodological framework to analyze the activity and travel pattern of workers during the evening commute. The framework uses a discrete-continuous econometric system to model jointly the decision to participate in an activity during the evening commute and the following attributes of the participation: activity type, activity duration, and travel time deviation to the activity location relative to the direct travel time from work to home. The model parameters are estimated using a sample of workers from the 1991 Boston Household Activity Survey. The paper also presents mathematical expressions to evaluate the effect of changes in sociodemographic variables and policy-relevant exogenous variables on the temporal pattern of trips and cold starts attributable to commute stops. The application of the model indicates that failure to accommodate the joint nature of the activity decisions during the evening commute can lead to misdirected policy actions for traffic congestion alleviation and for mobile-source emissions reduction. [ABSTRACT FROM AUTHOR]

The article presents abstracts of paper published in the August 1, 1993 issue of the Transportation Science. The air transportation industry continues to provide fertile ground for innovative, and exciting contributions to the transportation science. Airports are the critical bottleneck in the nation's air aviation network. It is therefore important to understand what factors affect the landing capacity of airports and how this capacity might be increased. Ground holding is the practice of delaying the departure of a flight due to anticipated congestion at destination airport because it is both less expensive and safer for aircraft to wait on the ground, prior to take-off, than in the air. Perishable-asset revenue management combines the traditional areas of yield management, overbooking, and pricing into one macro problem. Following deregulation, the U.S. airline industry has witnessed a period of intense competition. To remain profitable, most airlines have adopted some form of yield management system whereby an attempt is made to increase revenues by controlling the availability of seats in different fare classes.

In this paper a form of the stochastic shortest path problem is considered where the optimal path is one that maximizes the expected utility which is concave and quadratic. The principal contribution of this paper is the development of a relaxation based pruning technique which is incorporated into a label setting procedure. The basic label setting procedure solves the problem by generating all Pareto-optimal paths. However, the number of such paths can grow exponentially with the size of the problem. The relaxation based pruning technique developed here is able to recognize and discard most of the Pareto-optimal paths that do not contribute to the optimal path. Our computational results show that the label setting procedure that incorporates the pruning technique consistently outperforms the basic label setting procedure, and is able to solve large problems very quickly. [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]

We develop an optimization-based approach for a point-to-point route planning problem that arises in many large scale delivery systems (for example, less-than-truckload freight, rail, mail and package delivery, communications). In these settings, a firm which must ship goods between many origin and destination pairs on a network needs to specify a route for each origin-destination pair so as to minimize transportation costs and/or transit times. Typically, the cost structure is very complicated. The approach discussed in this paper exploits the structure of the problem to decompose it into two smaller subproblems, each amenable to solution by a combination of optimization and heuristic techniques. One subproblem is an "assignment" problem with capacity constraints. The other subproblem is a mixed-integer multicommodity flow problem. We propose solution methods based on Lagrangian relaxation for each subproblem. Computational remits with these methods and with a heuristic procedure for the multicommodity flow problem on a problem met in practice are encouraging and suggest that mathematical programming methods can be successfully applied to large-scale problems in delivery systems planning and other problems in logistical system design. [ABSTRACT FROM AUTHOR]

This paper examines a relaxed version of the generic vehicle routing problem. In this version, a delivery to a demand point can be split between any number of vehicles. In spite of this relaxation the problem remains computationally hard. The main contribution of this paper is in demonstrating the potential for cost savings through split deliveries. The solution scheme allowing for split deliveries is compared with a solution in which no split deliveries are allowed on a large set of 540 problems. Significant cost savings are realized both in terms of the total distance and the number of vehicles required. The. vehicle routes constructed by our procedure, tend to cover cohesive geographical. zones and retain some properties of optimal solutions. [ABSTRACT FROM AUTHOR]

In this paper we explicitly incorporate competitive markets for transportation services into the framework of spatial price equilibrium modeling. These markets can be purely local, purely global, or a combination thereof. We show that the existence of markets for transportation services is equivalent to the existence of congestion in a spatial price equilibrium model. In addition, we give general suggestions regarding the application of these models. [ABSTRACT FROM AUTHOR]

This paper extends the results of a previous study concerning distribution with time windows. It is recognized that customers who do not need to be allocated to a time window should receive different service than the rest. Three strategies were studied to accomplish that: stratified service, discriminating service, and staggered and discriminating service. Of these, the last strategy yields the lowest local distribution distance per customer, a distance which can be less than hall that for the strategy explained in the previous paper (joint service). Stratified service, however, can yield a lower line-haul distance per customer than staggered and discriminating service. In a specific case, a numerical comparison between stratified service and staggered and discriminating service should determine the overall best choice. This choice notwithstanding, the best strategy involves overlapping vehicle tours. The conventional wisdom of dividing customers into non-overlapping clusters for vehicle muting does not seem attractive for distribution problems with time windows. [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]

An introduction is presented in which the editor discusses various reports within the issue on topics including the capacitated location routing problem, long-haul transportation and rules on truck driver safety in the U.S.

The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) consists of routing and scheduling a set of vehicles, by integrating them with scheduled public transportation lines, to serve a set of freight requests within their time windows. This paper presents an exact solution approach based on a branch-and-price algorithm. A path-based set partitioning formulation is used as the master problem, and a variant of the elementary shortest path problem with resource constraints is solved as the pricing problem. In addition, the proposed algorithm can also be used to solve the PDPTW with transfers (PDPTW-T) as a special case. Results of extensive computational experiments confirm the efficiency of the algorithm: it is able to solve small- and medium-size instances to optimality within reasonable execution time. More specifically, our algorithm solves the PDPTW-SL with up to 50 requests and the PDPTW-T with up to 40 requests on the considered instances. The online appendix is available at https://doi.org/10.1287/trsc.2017.0798. [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]

We consider a single product maritime inventory routing problem in which the production and consumption rates are constant over the planning horizon. The problem involves a heterogeneous fleet and multiple production and consumption ports with limited storage capacity. Maritime transportation is characterized by high levels of uncertainty, and sailing times can be severely influenced by varying and unpredictable weather conditions. To deal with the uncertainty, this paper investigates the use of adaptable robust optimization where the sailing times are assumed to belong to the well-known budget polytope uncertainty set. In the recourse model, the routing, the order of port visits, and the quantities to load and unload are fixed before the uncertainty is revealed, while the visit time to ports and the stock levels can be adjusted to the scenario. We propose a decomposition algorithm that iterates between a master problem that considers a subset of scenarios and an adversarial separation problem that searches for scenarios that make the solution from the master problem infeasible. Several improvement strategies are proposed aiming at reducing the running time of the master problem and reducing the number of iterations of the decomposition algorithm. An iterated local search heuristic is also introduced to improve the decomposition algorithm. A computational study is reported based on a set of real instances. [ABSTRACT FROM AUTHOR]

An introduction is presented which discusess topics within the issue including uncertainty in planning logistics and transportation systems; robust strategic route planning in logistics; and aircraft routing.

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]

Advances in information technology and telecommunications, together with ever-growing amounts of data, offer opportunities for transportation companies to improve the quality of the service that they provide to their customers. This paper compares two methods motivated by the opportunity that the availability of data and technology gives to improve on current practice. In particular, the two solution approaches are explored in the context of a dynamic and stochastic routing problem in which a single, uncapacitated vehicle serves a set of known customers locations. One approach, sample-scenario planning, offers the potential for higher-quality solutions, but at the expense of greater computational effort. On the other hand, anticipatory insertion offers reduced computation and increased managerial ease, but with the potential for reduced solution quality due to restrictions on solution structure. Our results show that anticipatory insertion can often match the quality of sample-scenario planning, particularly when the degree of dynamism is low. [ABSTRACT FROM AUTHOR]

Aerodynamic efficiency of intermodal freight trains can be significantly improved by minimizing the adjusted gap lengths between adjacent loads. This paper first develops a static model to optimize load placement on a sequence of intermodal trains that have scheduled departure times. This model applies when full information on all trains and loads is available. Then, we develop a dynamic model to account for the more realistic situation in which there is incomplete or uncertain information on future trains and incoming loads. This paper develops methodology to balance between (i) the advantage from optimizing multiple trains together and (ii) the risk of making suboptimal decisions due to incomplete future information. We propose a rolling horizon scheme to address this challenge, where exponentially decreasing weights are assigned to the objective functions of future trains. Numerical results based on empirical data show significant aerodynamic efficiency benefits from these optimization models. [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]

The principal focus of this paper is to study carrier pricing decisions for a type of vehicle routing problems defined in a competitive and dynamic environment. This paper introduces the vehicle routing problem in a competitive environment (VRPCE) as an extension of the traveling-salesman problem with profits (TSPP) to a dynamic competitive auction environment. In the VRPCE, the carrier must estimate the incremental cost of servicing new service requests as they arrive dynamically. The paper presents a rigorous and precise treatment of the sequential pricing and costing problem that a carrier faces in such an environment. The sequential pricing problem presented here is an intrinsic feature of a sequential auction problem. In addition to introducing the formulation of this class of problems and discussing the main sources of difficulty in devising a solution, a simple example is constructed to show that carriers' prices under first-price auction payment rules do not necessarily reflect the cost of servicing transportation requests. An approximate solution approach with a finite rolling horizon is presented and illustrated through numerical experiments, in competition with a static approach with no look-ahead. [ABSTRACT FROM AUTHOR]

This paper shows how to coordinate the decisions on pricing and fleet management of a freight carrier. We consider a setting where the carrier announces its prices at the beginning of a certain time horizon and the load arrivals over this horizon depend on the announced prices. Assuming that the vehicle fleet is managed according to a particular class of fleet management models, we present a tractable method to obtain sample path-based directional derivatives of the objective function with respect to the prices. We use this information to search for a good set of prices. Numerical experiments show that our approach yields high-quality solutions. [ABSTRACT FROM AUTHOR]

In today's competitive environment, supply chain management is a major concern for a company. Two of the key issues in supply chain management are transportation and inventory management. To achieve significant savings, companies should integrate these two issues instead of treating them separately. This paper considers the problem of selecting the appropriate distribution strategy for delivering a family of products from a set of suppliers to a set of plants so that the total transportation, pipeline inventory, and plant inventory costs are minimized. With reasonable assumptions, a simple model is presented to provide a good solution that can serve as a guideline for the design and implementation of the distribution network. Due to the plant inventory cost, the problem is formulated as a nonlinear integer programming problem. The problem is difficult to solve because the objective function is highly nonlinear and neither convex nor concave. A greedy heuristic is proposed to find an initial solution and an upper bound. A heuristic and a branch-and-bound algorithm are developed based on the Lagrangian relaxation of the nonlinear program. Computational experiments are performed, and based on the results we can conclude that the performance of the algorithms are promising. [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 single-sink, fixed-charge transportation problem has a variety of applications, including supplier selection, product distribution/fleet selection, and process selection. In this paper we present a dynamic programming algorithm for solving this important problem that is very easy to implement and that improves considerably in terms of computational attractiveness on the best methods in the literature. [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]

In this paper we formally introduce a generic real-time multi-vehicle truck-load pick-up and delivery problem. The problem includes the consideration of various costs associated with trucks' empty travel distances, jobs' delayed completion times, and job rejections. Although very simple, the problem captures most features of the operational problem of a real-world trucking fleet that dynamically moves truckloads between different sites according to customer requests that arrive continuously. We propose a mixed-integer programming formulation for the off-line version of the problem. We then con- sider and compare five rolling horizon strategies for the real-time version. Two of the policies are based on a repeated reoptimization of various instances of the off-line problem, while the others use simpler local (heuristic) rules. One of the reoptimization strategies is new, while the other strategies have recently been tested for similar real-time fleet management problems. The comparison of the policies is done under a general simulation framework. The analysis is systematic and considers varying traffic intensities, varying degrees of advance information, and varying degrees of flexibility for job-rejection decisions. The new reoptimization policy is shown to systematically outperform the others under all these conditions. [ABSTRACT FROM AUTHOR]

The fast development of transport activities and the introduction of shipment consolidation have considerably changed the logistics context over the last three decades. Consolidation terminals, also called transshipment centers (TC) or hubs, have justified their presence by improving the loading of trucks in terms of both volume and weight. In addition, the possibility of using external carriers, exclusively or in coordination with a private fleet, can reduce costs and increase customer service. The right combination of these strategies can dramatically impact the cost of transport. However, the complexity of the decisions has also increased and existing models have to be improved to tackle these new challenges. In this paper, after discussing the different formulations for distribution networks with transshipment centers existing in the literature, we present a new model and an efficient metaheuristic that determines the number and the location of TCs as well as the best transportation alternative --LTL, FTL, Parcel, or own fleet--on each segment accounting for both weight and volume metrics. The ability of our heuristic to solve this complex problem comes from a judicious combination of tabu search and variable neighborhood search. The performance of this approach is evaluated on several test data problems generated with real cost structures published by a U.S.carrier. The heuristic solutions are compared to optimal ones obtained by an exact method for small-sized instances of the simpler problems. Finally, we address issues in carrier price structure to achieve efficient shipment practices. [ABSTRACT FROM AUTHOR]

In this paper, we study a cost-allocation problem that arises in a distribution-planning situation at the Logistics Department at Norsk Hydro Olje AB, Stockholm, Sweden. We consider the routes from one depot during one day. The total distribution cost for these routes is to be divided among the customers that are visited. This cost-allocation problem is formulated as a vehicle-routing game (VRG), allowing the use of vehicles with different capacities. Cost-allocation methods based on different concepts from cooperative game theory, such as the core and the nucleolus, are discussed. A procedure that can be used to investigate whether the core is empty or not is presented, as well as a procedure to compute the nucleolus. Computational results for the Norsk Hydro case are presented and discussed. [ABSTRACT FROM AUTHOR]

For a commercially operating railway company, providing a high level of service for the passengers is of utmost importance. The latter enquires high punctuality of the trains and an adequate rolling stock capacity. Unfortunately, the latter is currently (in 2002) one of the bottlenecks in the service provision by the main Dutch railway operator NS Reizigers. Especially during the morning rush hours, many passengers cannot be transported according to the usual service standards because of a shortage of the rolling stock capacity. On the other hand, a more effective allocation of the available rolling stock capacity seems to be feasible, because there are also several trains with some slack capacity. The effectiveness of the rolling stock capacity is determined mainly by the allocation of the train types and subtypes to the lines. Therefore, we describe in this paper a model that can be used to find an optimal allocation of train types and subtypes to the lines. This optimal allocation is more effective than the manually planned one, which is accomplished by minimizing the shortages of capacity during the rush hours. The model is implemented in the modeling language OPL Studio 3.1, solved by CPLEX 7.0, and tested on several scenarios based on the 2001-2002 timetable of NS Reizigers. The results of the model were received positively, both by the planners and by the management in practice, because these results showed that a significant service improvement over the manually planned allocation can be achieved within a shorter throughput time of the involved part of the planning process. [ABSTRACT FROM AUTHOR]