Search

In this paper, we study the pickup and delivery problem with time windows and multiple compartments (PDPTWMC). The PDPTWMC generalizes the pickup and delivery problem with time windows to vehicles with multiple compartments. In particular, we consider three compartment-related attributes: (1) compartment capacity flexibility that allows the capacities of the compartments to be fixed or flexible, (2) item-to-compartment flexibility that specifies which items are compatible with which compartments, and (3) item-to-item compatibility that considers that incompatible items cannot be simultaneously in the same compartment. To solve the PDPTWMC, we propose an exact branch-price-and-cut algorithm in which the pricing problem is solved by means of a unified bidirectional labeling algorithm. The labeling algorithm can tackle all possible combinations of the studied compartment-related attributes of the PDPTWMC. Furthermore, we implement several acceleration techniques that allow to, among others, reduce the symmetry in the label extensions with empty compartments, the symmetry in the dominance between compartments with similar attributes, and the complexity of the algorithm with fixed compartment capacity. Finally, we introduce benchmark instances for the PDPTWMC and conduct an extensive computational campaign to test the limits of our algorithm and to derive relevant managerial insights in order to highlight the applicability of considering the studied compartment-related attributes. Funding: This work was supported by Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 439.18.459] and the Natural Sciences and Engineering Research Council of Canada [Grant 2017-06106]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0252. [ABSTRACT FROM AUTHOR]

Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of "basic supply" and "augmented supply" vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are 1 / p 2 and (e − 1) / (2 e + o (1)) p ln p , where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications. 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 National Science Foundation [Grants CCF-2006778 and FW-HTF-P 2222806], the Ford Motor Company, and the Division of Civil, Mechanical, and Manufacturing Innovation [Grants CMMI-1854684, CMMI-1904575, and CMMI-1940766]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0349. [ABSTRACT FROM AUTHOR]

This paper integrates, from a tactical perspective, berth allocation and quay-crane assignment, two important, closely related decisions in container terminal operations in a single model. To obtain optimal solutions, a branch-and-price algorithm is sought in this paper under the framework of Dantzig–Wolfe decomposition. The algorithm decomposes the original problem to a master problem that links all vessels competing for the shared resources of berths and quay cranes and multiple per-vessel pricing subproblems that can be solved efficiently in polynomial time. Specifically, in the stage of generating promising initial feasible columns, three heuristics are adopted; during the column-updating stage, the subgradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon; the branching strategy is implemented in the pricing subproblem rather than in the master problem as reported in the literature with the benefit of avoiding incurring new dual prices, simplifying the branching process; and both breadth- and depth-first searching policies are tested to select the next node to explore. With real-life data, extensive numerical experiments are conducted to select the best choice for each stage with the strengths and drawbacks of each choice provided. And then the superiority of the branch-and-price algorithm configured with the selected combination of strategies is verified by comparing it with both CPLEX, a general-purpose solver, and a set-partitioning model, a dedicated algorithm reported in the literature. In addition, the decomposition by vessels adopted in this paper is also verified numerically by comparing it with the decomposition by berths reported in the literature, and the performance of the algorithm for other problem settings has also been tested. In conclusion, the numerical experiments show that our method outperforms the commercial solver and state-of-the-art solution methods reported in the literature in terms of both solution quality and computational time. [ABSTRACT FROM AUTHOR]

This paper studies the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to intermediate facilities (i.e., satellites), whereas the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We propose two path-based mathematical formulations for our problem: (1) in one formulation, paths are defined over both first- and second-echelon tours, and (2) in the other one, the first- and second-echelon paths are decomposed. Branch-and-price–based algorithms are developed for both formulations. We compare both formulations and solution methods on a comprehensive set of instances and are able to solve instances up to five satellites and 100 customers to optimality. This paper is the first paper in the literature that solves such large instance sizes. The online appendix is available at https://doi.org/10.1287/trsc.2018.0844. [ABSTRACT FROM AUTHOR]

This paper reviews the literature on vehicle routing problems and location routing problems with intermediate stops. We classify publications into different categories from both an application-based perspective and a methodological perspective. In addition, we analyze the papers with respect to the algorithms and benchmark instances they present. Furthermore, we provide an overview of trends in the literature and identify promising areas for further research. [ABSTRACT FROM AUTHOR]

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

A dry port system consists of a dry port and a number of shippers, where shippers enjoy the public logistics and auxiliary services provided by the dry port. This paper studies the shared transportation services in this system. The interaction between a dry port and shippers is modeled as a bi-level program. The optimal properties of the model are analyzed analytically and an enumeration algorithm is proposed to solve the model. Furthermore, a bi-level model is developed for the direct transportation system. Carbon dioxide (CO2) emissions in transportation are calculated under two scenarios: with and without sharing transportation. Numerical studies are conducted to investigate the sensitivity of the economic and environmental value of sharing with respect to various system parameters. The studies show that sharing transportation service could bring significant profit improvement to the dry port and cost savings to shippers in most circumstances. It is found that carbon emissions are not always mitigated when the distance between shippers is too long, or the dry port is located too close to shippers. When the total distance traveled in the direct transportation system is longer than that in the shared one, the analysis reveals that carrying lighter cargoes could generate more significant CO2 emissions savings. [ABSTRACT FROM AUTHOR]

This paper presents a branch-and-price-and-cut algorithm for the exact solution of the active-passive vehicle-routing problem (APVRP). The APVRP covers a range of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers or swap bodies). The objective is to minimize aweighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: First, we present an exact branch-and-price-and-cut algorithm for this class of routing problems with synchronization constraints. To our knowledge, this algorithm is the first such approach that considers explicitly the temporal interdependencies between active and passive vehicles. The algorithm is based on a nontrivial network representation that models the logical relationships between the different transport tasks necessary to fulfill a request as well as the synchronization of the movements of active and passive vehicles. Second, we contribute to the development of branch-and-price methods in general, in that we solve, for the first time, an ng-path relaxation of a pricing problem with linear vertex costs by means of a bidirectional labeling algorithm. Computational experiments show that the proposed algorithm delivers improved bounds and solutions for a number of APVRP benchmark instances. It is able to solve instances with up to 76 tasks, four active, and eight passive vehicles to optimality within two hours of CPU time. [ABSTRACT FROM AUTHOR]

This paper reviews studies from the past 30 years that use operations research methods to tackle containership routing and scheduling problems at the strategic, tactical, and operational planning levels. These problems are first classified and summarized, with a focus on model formulations, assumptions, and algorithm design. The paper then gives an overview of studies on containership fleet size and mix, alliance strategy, and network design (at the strategic level); frequency determination, fleet deployment, speed optimization, and schedule design (at the tactical level); and container booking and routing and ship rescheduling (at the operational level). The paper further elaborates on the needs of the liner container shipping industry and notes the gap between existing academic studies and industrial practices. Research on containership routing and scheduling lags behind practice, especially in the face of the fast growth of the container shipping industry and the advancement of operations research and computer technology. The purpose of this paper is to stimulate more practically relevant research in this emerging area. [ABSTRACT FROM AUTHOR]

Parking pressure has been steadily increasing in cities as well as on university and corporate campuses. To relieve this pressure, this paper studies a carpooling platform that would match riders and drivers while guaranteeing a ride back and exploiting spatial and temporal locality. In particular, the paper formalizes the commute trip-sharing problem (CTSP) to find a routing plan that maximizes ride sharing for a set of commute trips. The CTSP is a generalization of the vehicle routing problem with routes that satisfy time-window, capacity, pairing, precedence, ride-duration, and driver constraints. The paper introduces two exact algorithms for the CTSP: a route-enumeration algorithm and a branch-and-price algorithm. Experimental results show that on a high-fidelity real-world data set of commute trips from a midsize city, both algorithms optimally solve small and medium-sized problems and produce high-quality solutions for larger problem instances. The results show that carpooling, if widely adopted, has the potential to reduce vehicle usage by up to 57% and decrease vehicle miles traveled by up to 46% while incurring only a 22% increase in average ride time per commuter for the trips considered. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm that automatically translates the "continuum approximation" (CA) recipes for location problems into discrete designs. It applies to terminal systems, but can also be used for other logistics problems. The study also systematically compares the logistics costs predicted by the CA approach with the actual costs for discrete designs obtained with the automated procedure. The predictions are quite accurate. The paper also gives conditions under which the discrete solution has a small optimality gap. [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]

In this paper, a sanitation routing problem called the Rollon-Rolloff Vehicle Routing Problem (RRVRP) is defined. In the RRVRP, tractors move large trailers between locations and a disposal facility. The trailers are so large that the tractor can only transport one trailer at a time. In this paper, the RRVRP is defined, a mathematical programming formulation is presented, and two lower bounds and four heuristic algorithms are developed and tested on 20 different problems. Conclusions are derived and recommendations for further research are presented. [ABSTRACT FROM AUTHOR]

In this paper we introduce the time window assignment vehicle routing problem (TWAVRP). In this problem, I time windows have to be assigned before demand is known. Next, a realization of demand is revealed, and a vehicle routing schedule is made that satisfies the assigned time windows. The objective is to minimize the expected traveling costs. We propose a branch-price-and-cut algorithm to solve the TWAVRP to optimality. We provide results of computational experiments performed using this algorithm. Finally, we offer insight on the value of an exact approach for the TWAVRP by comparing the optimal solution to the solution found by assigning time windows based on solving a vehicle routing problem with time windows with average demand. [ABSTRACT FROM AUTHOR]

Federal aviation regulations require that all aircraft undergo maintenance after flying a certain number of hours. Most major U.S. airlines observe the maintenance regulations by requiring that aircraft spend a night at a maintenance station after at most three or four days of flying. In addition, some airlines require that every aircraft goes through a special maintenance station for what is commonly called a balance check. Airlines usually schedule routine maintenance only at night so as not to cut into aircraft utilization. The maintenance routing problem is to find a routing of the aircraft that satisfies the short-term routine maintenance requirements. In Gopalan, R. and Talluri, K T. ("The Aircraft Maintenance Routing Problem," Opns. Res. in press) we modeled this problem as one of generating an appropriate directed graph (called a line-of-flight-graph), and of finding a special Euler Tour called the k-day Maintenance Euler Tour (k-MET, for k = 3, 4, ...) in that directed graph-for finding a maintenance routing in which the aircraft would spend at most k days of flying before overnighting at a maintenance station and have an opportunity for a balance-check. In the same paper we gave a polynomial-time algorithm for finding a 3-MET, if one exists, in the directed graph. In this paper we consider the routing problem when the requirement is to overnight at a maintenance station after at most four days of flying and to undergo the balance check every n days, where n is the number of planes in the fleet of the equipment type under consideration. We show that this problem is NP-complete; in fact, that the k-MET problem is NP-complete for all k ⩾ 4. When the number of maintenance stations is exactly one, we show that the 4-MET problem can be solved by solving an appropriate bipartite matching problem; and hence in polynomial time. As a corollary to this result, we show that when there is no balance check station visit requirement, the four-day routing problem, in a given LOF-graph, can be solved (without any restrictions on the number of maintenance stations) in polynomial time. We show how our polynomial-time algorithms for the 3-MET problem and the restricted 4-MET problem can be used to design effective heuristics for the 4-MET problem. [ABSTRACT FROM AUTHOR]

In this paper we consider minimum and minimax single facility location problems where the effective service distance becomes a constant when the actual distance attains or exceeds a certain value. Properties of these problems are studied, and algorithms for their solution are presented. [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]

This paper shows how distribution problems with delivery time constraints can be modeled approximately with just a few variables. Its objective is neither to develop a scheduling algorithm nor an exact predictive method; rather, it is to illustrate some trade-offs and principles that can be used for planning and algorithm development. A workday is divided into time periods. Time windows are modeled by specifying the period in which a vehicle should visit each customer. (The companion paper explores scenarios where many customers do not specify a time window, and thus, it is advantageous not to allocate all the customers to periods.) Travel distance expressions are provided for a "cluster-first, route-second" strategy, similar to some routing methods currently in use. Travel distance expressions are also provided for refinements of the strategy, including one in which tours are systematically staggered, overlapping. The consequent reductions in travel distance can be quite significant. We suggest here that more attention should be paid to the clustering part of algorithm construction, and point to ways in which the customers served by one vehicle should be selected. This paper shows how distribution problems with delivery time constraints can be modeled approximately with just a few variables. Its objective is neither to develop a scheduling algorithm nor an exact predictive method; rather, it is to illustrate some trade-offs and principles that can be used for planning and algorithm development. A workday is divided into time periods. Time windows are modeled by specifying the period in which a vehicle should visit each customer. (The companion paper explores scenarios where many customers do not specify a time window, and thus, it is advantageous not to allocate all the customers to periods.) Travel distance expressions are provided for a "cluster-first, route-second" strategy, similar to some routing methods currently in use. Travel distance expressions are... [ABSTRACT FROM AUTHOR]

This paper introduces the problem of finding the least expected travel time path between two nodes in a network with travel times that are both random and time-dependent (e.g., a truck, rail, air or bus network). It first shows that standard shortest path algorithms (such as the Dijkstra algorithm) do not find the minimum expected travel time path on such a network, then proposes a method which does find the minimum path. Next, this paper shows that the optimal "route choice" is not a simple path but an adaptive decision rule. The best route from any given node to the final destination depends on the arrival time at that node. Because the arrival time is not known before departing the origin, a better route can be selected by deferring the final choice until later nodes are reached. A method for finding the optimal adaptive decision rule is proposed. [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]

Strategy-based equilibrium traffic assignment (SETA) problems define travel choice broadly as a strategy rather than a simple path. Travelers navigating through a network based on a strategy end up following a hyperpath. SETA is well suited to represent a rich set of travel choices that take place en route at nodes, such as transit passengers' transfer decisions, truckers' bidding decisions, and taxi drivers' reposition decisions. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within the same modeling framework, built on the concept of a hypergraph. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignments to them, HBA promises to obtain more precise solutions to larger instances of SETA problems at a lower computational cost, both in terms of CPU time and memory consumption. To demonstrate its generality and efficiency, we tailor HBA to solve two SETA problems. The results confirm that HBA consistently outperforms the benchmark algorithms in the literature, including two state-of-the-art hyperpath-based algorithms. To obtain high-quality equilibrium solutions for SETA instances of practical size, HBA runs up to five times faster than the best competitor with a fraction of its memory consumption. [ABSTRACT FROM AUTHOR]

We address the network maintenance scheduling problem, which consists of finding the optimal schedule for the coordination of road maintenance projects in a transport network over a planning period. Road works and maintenance operations that require partial or total road closures over a period of time may considerably impact network performance and result in significant delays. In addition, the effects of conducting multiple maintenance projects simultaneously may be nonadditive, hence increasing the difficulty to anticipate congestion effects. In this paper, we propose a new bilevel mixed integer programming formulation for the network maintenance scheduling problem, which relies on the enumeration of maintenance project combinations—patterns—to incorporate congestion effects within the scheduling process. We present a new branch-and-price algorithm that relies on customized branching and bounding rules, and a tailored column generation framework to price patterns. In addition, a statistical regression model is introduced to approximate congestion effects and provide approximate lower bounds on the formulations therein. The proposed branch-and-price algorithm is implemented on instances derived from realistic transport networks and is shown to be able to solve the network maintenance scheduling problem in a reasonable time using only a fraction of the patterns. [ABSTRACT FROM AUTHOR]

This paper proposes a novel algorithm to determine the path flow solution that satisfies the proportionality condition from a given origin-based user equilibrium (UE) link flow solution. The algorithm iteratively refines the origin-based bush representation of the UE solution through constructing a list of "node-based arrival bushes" and solving the entropy maximization subproblems defined on them. Thanks to the special structure of bushes, these subproblems can be solved efficiently. The proposed algorithm thus obviates the known hurdles to efficient implementation, such as enumerating all UE paths or collecting a set of paired alternative segments to cover them. We prove that the algorithm ensures convergence to a solution that perfectly satisfies the proportionality condition in general networks. Numerical experiments indicate that the proposed algorithm converges much faster than the known alternative, with a three- to eightfold speed-up on large networks. The online appendices are available at https://doi.org/10.1287/trsc.2018.0845. [ABSTRACT FROM AUTHOR]

The split delivery vehicle routing problem with time windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find a useful compact mixed-integer programming (MIP) formulation for the SDVRPTW. Standard modeling approaches either suffer from inherent symmetries (mixed-integer programs with a vehicle index) or cannot exactly capture all aspects of feasibility. Because of the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW have been branch-and-price-and-cut approaches using path-based formulations. In this paper, we propose a new and tailored branch-and-cut algorithm to solve the SDVRPTW. It is based on a new, relaxed compact model, in which some integer solutions are infeasible for the SDVRPTW. We use known and introduce some new classes of valid inequalities to cut off such infeasible solutions. One new class is path-matching constraints that generalize infeasible-path constraints. However, even with the valid inequalities, some integer solutions to the new compact formulation remain to be tested for feasibility. For a given integer solution, we build a generally sparse subnetwork of the original instance. On this subnetwork, all time-window-feasible routes can be enumerated, and a path-based residual problem then solved to decide on the selection of routes, the delivery quantities, and thereby the overall feasibility. All infeasible solutions need to be cut off. For this reason, we derive some strengthened feasibility cuts exploiting the fact that solutions often decompose into clusters. Computational experiments show that the new approach is able to prove optimality for several previously unsolved instances from the literature. The e-companion is available at https://doi.org/10.1287/trsc.2018.0825. [ABSTRACT FROM AUTHOR]

This paper addresses the dispatching problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process and dispatches them in batches for the last-mile distribution. The operator of the center aims to find the cost-minimizing consolidation policy, depending on the orders at hand, preannounced orders, and stochastic arrivals. We present this problem as a variant of the delivery dispatching problem that includes dispatch windows and define a corresponding Markov decision model. Larger instances of the problem suffer from intractably large state-, outcome-, and action spaces. We propose an approximate dynamic programming (ADP) algorithm that can handle such instances, using a linear value function approximation to estimate the downstream costs. To design the value function approximation, we construct various sets of basis functions, numerically evaluate their suitability, and discuss the properties of good basis functions for the dispatching problem. Numerical experiments on toy-sized instances show that the best set of basis functions approximates the optimal values with an error of less than 3%. To cope with large action spaces, we formulate an integer linear program to be used within our ADP algorithm. We evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. We test the performance of ADP on a variety of networks. ADP consistently outperforms the benchmark policies, performing particularly well when there is sufficient flexibility in dispatch times. The online appendix is available at https://doi.org/10.1287/trsc.2017.0773. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an extension of the R-DARP recently proposed by [Liu M, Luo Z, Lim A (2015) A branch-and-cut algorithm for a realistic dial-a-ride problem. Transporation Res. Part B: Methodological 81(1):267–288.]. The R-DARP, as a variant of the classic dial-a-ride problem (DARP), consists of determining a set of minimum-distance trips for vehicles to transport a set of clients from their origins to their destinations, subject to side constraints, such as capacity constraints, time window constraints, maximum riding time constraints, and manpower planning constraints. Our problem extends the R-DARP by (1) changing its objective to first maximizing the number of requests satisfied and then minimizing the total travel distance of the vehicles, and (2) generalizing the lunch break constraints of staff members. To solve this problem, we propose a two-phase branch-and-price-and-cut algorithm based on a strong trip-based model. The trip-based model is built on a set of nondominated trips, which are enumerated by an ad hoc label-setting algorithm in the first phase. Then we decompose the trip-based model by Benders decomposition and propose a branch-and-price-and-cut algorithm to solve the decomposed model in the second phase. Our two-phase exact algorithm is tested on the R-DARP benchmark instances and a set of new instances generated according to the same real-world data set as the R-DARP instances. Our algorithm quickly solves all of the R-DARP instances to optimality and outperforms the branch-and-cut proposed by Liu, Luo, and Lim. On the 42 new test instances, our algorithm solves 27 instances to optimality in four hours with the largest instance consisting of 36 requests. The online appendix is available at https://doi.org/10.1287/trsc.2017.0772. [ABSTRACT FROM AUTHOR]

China has recently developed a large-scale high-speed railway (HSR) network that not only revolutionizes the perception of long-haul transport but also fundamentally improves the emergency response capability of the country. This gives rise to a problem of scheduling a set of emergency trains within the predefined HSR timetable. According to different degrees of disturbance of the timetable, this paper identifies three kinds of solutions, named, ideal, quasi-ideal, and feasible solutions, to the problem. We define a "headroom" function for computing the maximum number of emergency trains that can be inserted between two adjacent regular trains without any disturbance, from which a linear algorithm for finding ideal solutions is derived. By identifying the scope of changes to each regular train, quasi-ideal and feasible solutions can be found based on the ideal solutions on a set of alternative timetables. Numerical experiments demonstrate that our method is very efficient for supporting near-immediate emergency responses. We have used the solution method to evaluate the emergency capacity of most HSR lines in China. In particular, we successfully applied the method to schedule emergency trains in the rescue operation of the 2015 Tianjin chemical explosion. The online appendix is available at https://doi.org/10.1287/trsc.2017.0794. [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]

The Inventory Routing Problem (IRP) involves the distribution of one or more products from a supplier to a set of clients over a discrete planning horizon. Each client has a known demand to be met in each period and can only hold a limited amount of stock. The product is shipped through a distribution network by one or more vehicles of limited capacity. The objective is to find replenishment decisions minimizing the sum of the storage and distribution costs. In this paper, we present IRP reformulations under the Maximum Level replenishment policy, derived from a single-period substructure. We define a generic family of valid inequalities, and then introduce two specific subclasses for which the separation problem of generating violated inequalities can be effectively solved. A basic Branch-and-Cut algorithm has been implemented to demonstrate the strength of the single-period reformulations. We present computational results for the benchmark instances with 50 clients and 3 periods and 30 clients and 6 periods. [ABSTRACT FROM AUTHOR]

Recent research on location-routing problems has been focusing on locating facilities as the starting and end point of routes. In this paper, we investigate a new type of location-routing problem. In the location-routing problem with intra-route facilities, the location of depots is known, whereas the location of facilities for intermediate stops has to be determined to keep vehicles operational. We present an adaptive large neighborhood search which is enhanced by local search and dynamic programming components, and derive new penalty functions for time-efficient neighborhood evaluation. We show that this algorithm is suitable for solving various problems with intra-route facilities by deriving new best known solutions for the recently published electric location-routing problem with time windows and partial recharging, as well as for the battery swap station electric vehicle location-routing problem. Additionally, we create new real-world benchmark instances and show results as well. Furthermore, we assess the competitiveness of our algorithm on the electric vehicle routing problem with time windows for full and partial recharging, and derive new best known solutions for both problem variants. [ABSTRACT FROM AUTHOR]

The planning of outbound baggage handling at international airports is challenging. Outgoing flights have to be assigned and scheduled to handling facilities at which the outgoing baggage is loaded into containers. To avoid disruptions of the system the objective is to minimize workload peaks over the entire system. The resource demand of the jobs that have to be scheduled depends on the arrival process of the baggage. In this paper we present a time-indexed mathematical programming formulation for planning the outbound baggage. We propose an innovative decomposition procedure in combination with a column generation scheme to solve practical problem instances. The decomposition significantly reduces the symmetry effect in the time-indexed formulation and also speeds up the computational time of the corresponding Dantzig-Wolfe formulation. To further improve our column generation algorithm we propose state-of-the-art acceleration techniques for the primal problem and the pricing problem. Computational results based on real data from a major European airport show that the proposed procedure reduces the maximal workloads by more than 60% compared to the current assignment procedure used. The online appendix is available at . [ABSTRACT FROM AUTHOR]

In this paper, we propose an exact branch-price-and-cut (BPC) algorithm for the two-echelon vehicle routing problem with time windows. This problem arises in city logistics when high-capacity and low-capacity vehicles are used to transport items from depots to satellites (first echelon) and from satellites to customers (second echelon), respectively. The aim is to determine a set of least-cost first- and second-echelon routes such that the load on the routes respect the capacity of the vehicles, each second-echelon route is supplied by exactly one first-echelon route, and each customer is visited by exactly one second-echelon route within its time window. We model the problem with a route-based formulation where first-echelon routes are enumerated a priori, and second-echelon routes are generated using column generation. The problem is solved using BPC. To generate second-echelon routes, one pricing problem per satellite is solved using a labeling algorithm which keeps track of the first-echelon route associated with each (partial) second-echelon route considered. Furthermore, to speed up the solution process, we introduce effective deep dual-optimal inequalities and apply known valid inequalities. We perform extensive computational experiments on benchmark instances and show that our method outperforms a state-of-the-art algorithm. We also conduct sensitivity analyses on the different components of our algorithm and derive managerial insights related to the structure of the first-echelon routes. [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]

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

In this paper, we study a warehouse-retailer network design (WRND) model that simultaneously makes the location, distribution, and warehouse-retailer echelon inventory replenishment decisions. Although a column generation algorithm was proposed recently in the literature, it remains a challenge to solve large size instances of this NP-hard problem efficiently and effectively. The purpose of this paper is to present a greedy algorithm. Computational results demonstrate that our greedy algorithm can solve large-scale WRND problems efficiently with errors within 3%-4% on average. [ABSTRACT FROM AUTHOR]

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

This paper focuses on a generic model for service network design, which includes asset positioning and utilization through constraints on asset availability at terminals. We denote these relations as "design-balance constraints" and focus on the design-balanced capacitated multicommodity network design model, a generalization of the capacitated multicommodity network design model generally used in service network design applications. Both arc- and cycle-based formulations for the new model are presented. The paper also proposes a tabu search metaheuristic framework for the arc-based formulation. Results on a wide range of network design problem instances from the literature indicate the proposed method behaves very well in terms of computational efficiency and solution quality. [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]

We consider online versions of the traveling salesman problem (TSP) and traveling repairman problem (TRP) where instances are not known in advance. Cities (points) to be visited are revealed over time, while the server is en route serving previously released requests. These problems are known in the literature as the online TSP (TRP, respectively). The corresponding offline problems are the TSP (TRP) with release dates, problems where each point has to be visited at or after a given release date. In the current literature, the assumption is that a request becomes known at the time of its release date. In this paper we introduce the notion of a request's disclosure date, the time when a city's location and release date are revealed to the server. In a variety of disclosure date scenarios and metric spaces, we give new online algorithms and quantify the value of this advanced information in the form of improved competitive ratios. We also provide a general result on polynomial-time online algorithms for the online TSP. [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]

The crew-pairing problem (CPP) is solved in the first step of the crew-scheduling process. It consists of creating a set of pairings (sequence of flights, connections, and rests forming one or multiple days of work for an anonymous crew member) that covers a given set of flights at minimum cost. Those pairings are assigned to crew members in a subsequent crew-rostering step. In this paper, we propose a new integral column-generation algorithm for the CPP, called improved integral column generation with prediction ( I 2 C G p ), which leaps from one integer solution to another until a near-optimal solution is found. Our algorithm improves on previous integral column-generation algorithms by introducing a set of reduced subproblems. Those subproblems only contain flight connections that have a high probability of being selected in a near-optimal solution and are, therefore, solved faster. We predict flight-connection probabilities using a deep neural network trained in a supervised framework. We test I 2 C G p on several real-life instances and show that it outperforms a state-of-the-art integral column-generation algorithm as well as a branch-and-price heuristic commonly used in commercial airline planning software, in terms of both solution costs and computing times. We highlight the contributions of the neural network to I 2 C G p . [ABSTRACT FROM AUTHOR]

Collaborative decision making (CDM) is a joint Federal Aviation Administration (FAA)/ industry initiative aimed at improving traffic flow management when inclement weather reduces an airport's arrival capacity. CDM replaces the present Ground Delay Program and is expected to be fully implemented by or around the year 2000. Under CDM, during periods of undersupply, the FAA's role shifts from centralized decision-maker to information gatherer and resource arbiter. Filling the decision-making void are the airlines, now given the freedom to make rescheduling decisions according to their own priorities and objectives. In this paper, we present an integer model and a real-time solution algorithm that assist an airline in making these rescheduling decisions at its hub airport, the location with the largest number of operations and therefore the greatest opportunity for improvement. Our research improves the existing state-of-the-art by representing the real world more thoroughly and intuitively than existing models (a modeling contribution) and by exploiting the structure of our model to achieve optimal solutions to large-scale scenarios in real time (an algorithmic contribution). Furthermore, we present four different formulations of the model. Although the different formulations are equivalent in that they have identical integer feasible solution sets and optimal objective function values, they exhibit widely-varying optimization times when tested on large-scale scenarios, allowing us to compare the characteristics and desirability of the alternative formulation techniques. [ABSTRACT FROM AUTHOR]

In this paper, a stochastic vehicle routing problem is considered. In particular, customer demand is assumed to be uncertain, and actual demand is revealed only upon the visit to the customer. Instead of adopting the simple recourse action of returning to the depot whenever the vehicle runs out of stock, the points along the route at which restocking is to occur are designed into the route. The restocking points may be before a stockout actually occurs. Two heuristic algorithms are developed to construct both single and multiple routes that minimize total travel cost. The computational results show that the heuristic procedures produce quality solutions and are efficient. [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]

The single source Weber problem with limited distances (SSWPLD) is a continuous optimization problem in location theory. The SSWPLD algorithms proposed so far are based on the enumeration of all regions of ℜ 2 defined by a given set of n intersecting circumferences. Early algorithms require O (n 3) time for the enumeration, but they were recently shown to be incorrect in case of degenerate intersections, that is, when three or more circumferences pass through the same intersection point. This problem was fixed by a modified enumeration algorithm with complexity O (n 4) , based on the construction of neighborhoods of degenerate intersection points. In this paper, it is shown that the complexity for correctly dealing with degenerate intersections can be reduced to O (n 2 log n) so that existing enumeration algorithms can be fixed without increasing their O (n 3) time complexity, which is due to some preliminary computations unrelated to intersection degeneracy. Furthermore, a new algorithm for enumerating all regions to solve the SSWPLD is described: its worst-case time complexity is O (n 2 log n). The new algorithm also guarantees that the regions are enumerated only once. [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]

In this paper, we propose a fast and scalable, yet effective, metaheuristic called FILO to solve large-scale instances of the Capacitated Vehicle Routing Problem. Our approach consists of a main iterative part, based on the Iterated Local Search paradigm, which employs a carefully designed combination of existing acceleration techniques, as well as novel strategies to keep the optimization localized, controlled, and tailored to the current instance and solution. A Simulated Annealing-based neighbor acceptance criterion is used to obtain a continuous diversification, to ensure the exploration of different regions of the search space. Results on extensively studied benchmark instances from the literature, supported by a thorough analysis of the algorithm's main components, show the effectiveness of the proposed design choices, making FILO highly competitive with existing state-of-the-art algorithms, both in terms of computing time and solution quality. Finally, guidelines for possible efficient implementations, algorithm source code, and a library of reusable components are open-sourced to allow reproduction of our results and promote further investigations. [ABSTRACT FROM AUTHOR]