Search

With the recent boom of the gig economy, urban delivery systems have experienced substantial demand growth. In such systems, orders are delivered to customers from local distribution points respecting a delivery time promise. An important example is a restaurant meal delivery system, where delivery times are expected to be minutes after an order is placed. The system serves orders by making use of couriers that continuously perform pickups and deliveries. Operating such a rapid delivery system is very challenging, primarily because of the high service expectations and the considerable uncertainty in both demand and delivery capacity. Delivery providers typically plan courier shifts for an operating period based on a demand forecast. However, because of the high demand volatility, it may at times during the operating period be necessary to adjust and dynamically add couriers. We study the problem of dynamically adding courier capacity in a rapid delivery system and propose a deep reinforcement-learning approach to obtain a policy that balances the cost of adding couriers and the cost-of-service quality degradation because of insufficient delivery capacity. Specifically, we seek to ensure that a high fraction of orders is delivered on time with a small number of courier hours. A computational study in the meal delivery space shows that a learned policy outperforms policies representing current practice and demonstrates the potential of deep learning for solving operational problems in highly stochastic logistic settings. History: This paper has been accepted for the Transportation Science Special Issue on Machine-Learning Methods and Applications in Large-Scale Route Planning Problems. Funding: This work was supported by Agencia Nacional de Investigación y Desarrollo [72180404]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2022.0042. [ABSTRACT FROM AUTHOR]

We study the linked tactical design problems of fleet sizing and partitioning a service region into vehicle routing zones for same-day delivery (SDD) systems. Existing SDD studies focus primarily on operational dispatch problems and do not consider system design questions. Prior work on SDD system design has not considered the fleet sizing decision when a service region may be partitioned into zones dedicated to individual vehicles; such designs have been shown to improve system efficiency in related vehicle routing settings. Using continuous approximations to capture average-case operational behavior, we consider first the problem of independently maximizing the area of a single-vehicle delivery zone. We characterize area-maximizing dispatching policies and leverage these results to develop a procedure for calculating optimal areas as a function of a zone's distance from the depot, given a maximum number of daily dispatches per vehicle. We then demonstrate how to derive fleet sizes from optimal area functions and propose an associated Voronoi approach to partition the service region into single-vehicle zones. We test the fleet sizing and partitioning approach in a computational study that considers two different service regions and demonstrate its pragmatism and effectiveness via an operational simulation. Using minimal computation, the approach specifies fleet sizes and builds vehicle delivery zones that meet operational requirements, verified by simulation results. [ABSTRACT FROM AUTHOR]

We study tactical models for the design of same-day delivery (SDD) systems. Same-day fulfillment in e-commerce has seen substantial growth in recent years, and the underlying management of such services is complex. Although the literature includes operational models to study SDD, they tend to be detailed, complex, and computationally difficult to solve, and thus may not provide any insight into tactical SDD design variables and their impact on the average performance of the system. We propose a simplified vehicle-dispatching model that captures the "average" behavior of an SDD system from a single stocking location by utilizing continuous approximation techniques. We analyze the structure of optimal vehicle-dispatching policies given our model for two important instance families—the single-vehicle case and the case in which the delivery fleet is large—and develop techniques to find these policies that require only simple computations. We also leverage these results to analyze the case of a finite fleet, proposing a heuristic policy with a worst-case approximation guarantee. We then demonstrate with several example problem settings how this model and these policies can help answer various tactical design questions, including how to select a fleet size, determine an order cutoff time, and combine SDD and overnight order delivery operations. We validate model predictions empirically against a detailed operational model in a computational case study using geographic and Census data for the northeastern metro Atlanta region, and we demonstrate that our model predicts the average number of orders served and dispatch time to within 1%. This paper was accepted by Jay Swaminathan, operations management. [ABSTRACT FROM AUTHOR]

We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. There has been recent interest in dual bounds for such problems, of two types. One, known as expected group subproblem objective (EGSO) bounds, require solution of a group subproblem, which optimizes over a subset of the scenarios, for all subsets of the scenario set that have a given cardinality. Increasing the subset cardinality in the group subproblem improves bound quality, (EGSO bounds form a hierarchy), but the number of group subproblems required to compute the bound increases very rapidly. Another is based on partitions of the scenario set into subsets. Combining the values of the group subproblems for all subsets in a partition yields a partition bound. In this paper, we consider partitions into subsets of (nearly) equal cardinality. We show that the expected value of the partition bound over all such partitions also forms a hierarchy. To make use of these bounds in practice, we propose random sampling of partitions and suggest two enhancements to the approach: sampling partitions that align with the multistage scenario tree structure and use of an auxiliary optimization problem to discover new best bounds based on the values of group subproblems already computed. We establish the effectiveness of these ideas with computational experiments on benchmark problems. Finally, we give a heuristic to save computational effort by ceasing computation of a partition partway through if it appears unpromising. [ABSTRACT FROM AUTHOR]

Dynamic ride-sharing systems enable people to share rides and increase the efficiency of urban transportation by connecting riders and drivers on short notice. Automated systems that establish ride-share matches with minimal input from participants provide convenience and the most potential for system-wide performance improvement, such as reduction in total vehicle-miles traveled. Indeed, such systems may be designed to match riders and drivers to maximize system performance improvement. However, system-optimal matches may not provide the maximum benefit to each individual participant. In this paper, we consider a notion of stability for ride-share matches and present several mathematical programming methods to establish stable or nearly stable matches, where we note that ride-share matching optimization is performed over time with incomplete information. Our numerical experiments using travel demand data for the metropolitan Atlanta region show that we can significantly increase the stability of ride-share matching solutions at the cost of only a small degradation in system-wide performance. [ABSTRACT FROM AUTHOR]

We study same-day delivery systems by formulating the dynamic dispatch waves problem (DDWP), which models a depot where delivery requests arrive dynamically throughout a service day. At any dispatch epoch (wave), the information available to the decision maker is (1) a set of known, open requests that remain unfulfilled, and (2) a set of potential requests that may arrive later in the service day. At each wave, the decision maker decides whether or not to dispatch a vehicle, and if so, which subset of open requests to serve, with the objective of minimizing expected vehicle operating costs and penalties for unserved requests.We consider the DDWP with a single delivery vehicle and request destinations on a line, where vehicle operating times and costs depend only on the distance between points.We propose an efficient dynamic programming approach for the deterministic variant, and leverage it to design an optimal a priori policy with predetermined routes for the stochastic case. We then show that fully dynamic policies may perform arbitrarily better than a priori ones, and propose heuristics and dual bounds for this case. [ABSTRACT FROM AUTHOR]

Less-than-truckload (LTL) carriers operate networks of consolidation terminals, and route each customer shipment through a sequence of transfer terminals. At each terminal stop, a shipment is unloaded from an inbound trailer and reloaded onto an outbound trailer. A load plan determines the specific path of terminals to be used to transfer freight moving between each origin and destination. The design of the load plan determines the line-haul transportation and handling costs required to serve customers. This paper develops an effective neighborhood search heuristic for solving a natural integer programming model for LTL load plan design. During each iteration of the heuristic, a modified version of the integer programming model is solved to find improving changes freight transfer paths for a subset of the origin-destination terminal pairs. Unlike existing approaches in the literature, the modified model solved here allows the simultaneous rerouting of freight destined for multiple terminals during each neighborhood search iteration, yet remains computationally practical. Computational experiments using data from a large U.S. carrier show substantial cost improvements generated by increased freight consolidation, in the order of 6%-7%, accounting for over $300,000 per week. [ABSTRACT FROM AUTHOR]

We present integer programming models of the service network design problem faced by less-than-truckload (LTL) freight transportation carriers and a solution approach for the large-scale instances that result in practical applications. To accurately represent freight consolidation opportunities, the models use a fine discretization of time. Furthermore, the models simultaneously route freight and empty trailers and thus explicitly recognize the efficiencies presented by backhaul lanes. The solution approach can generate the traditional service network designs commonly used by LTL carriers but also enables the construction of designs that allow more flexibility, e.g., that allow freight routes to vary by day of week. An iterative improvement scheme is employed that searches a large neighborhood, each iteration using an integer program. Computational experiments using data from a large U.S. carrier demonstrate that the proposed modeling and solution approach has the potential to generate significant cost savings. [ABSTRACT FROM AUTHOR]

Ports-of-entry are critical components of the modern international supply chain infrastructure, particularly container seaports and airfreight hubs. The potential operational and economic impact resulting from their temporary closure is unknown but is widely believed to be very significant. This paper investigates one aspect of this potential impact, focusing specifically on the use of supply chain inventory as a risk mitigation strategy for a one supplier, one customer system in which goods are transported through a port-of-entry subject to temporary closures. Closure likelihood and duration are modeled using a completely observed, exogenous Markov chain. Order lead times are dependent on the status of the port-of-entry, including potential congestion backlogs of unprocessed work. An infinite-horizon, periodic-review inventory control model is developed to determine the optimal average cost ordering policies under linear ordering costs with backlogged demand. When congestion is negligible, the optimal policy is state invariant. In the more complex case of nonnegligible congestion, this result no longer holds. For studied scenarios, numerical results indicate that operating margins may decrease 10% for reasonable-length port-of-entry closures, that margins may be eliminated completely without contingency plans, and that expected holding and penalty costs may increase 20% for anticipated increases in port-of-entry utilization. [ABSTRACT FROM AUTHOR]

Time considerations have been largely ignored in the study of vehicle routing problems with stochastic demands, even though they are crucial in practice. We show that tour duration limits can effectively and efficiently be incorporated in solution approaches that build fixed, or a priori, tours for such problems. We do so by assuming that each tour must be duration feasible for all demand realizations, and determine the maximum duration of a given delivery tour by solving the optimization problem of an adversary. A computational study demonstrates the approach, and shows that enforcing tour duration limits impacts the structure of nearly-best solutions and may create the need for additional tours. However, for the instances considered, the price paid for robustness is small as the increase in total expected tour duration is modest. [ABSTRACT FROM AUTHOR]

We develop a robust optimization framework for dynamic empty repositioning problems modeled using time-space networks. In such problems, uncertainty arises primarily from forecasts of future supplies and demands for assets at different time epochs. The proposed approach models such uncertainty using intervals about nominal forecast values and a limit on the systemwide scaled deviation from the nominal forecast values. A robust repositioning plan is defined as one in which the typical flow balance constraints and flow bounds are satisfied for the nominal forecast values, and the plan is recoverable under a limited set of recovery actions. A plan is recoverable when feasibility can be reestablished for any outcome in a defined uncertainty set. We develop necessary and sufficient conditions for flows to be robust under this definition for three types of allowable recovery actions. When recovery actions allow only flow changes on inventory arcs, we show that the resulting problem is polynomially solvable. When recovery actions allow limited reactive repositioning flows, we develop feasibility conditions that are independent of the size of the uncertainty set. A computational study establishes the practical viability of the proposed framework. [ABSTRACT FROM AUTHOR]

This paper presents a paired-vehicle recourse strategy for the vehicle routing problem with stochastic demands (VRPSD). In the VRPSD, a fleet of homogeneous capacitated vehicles is dispatched from a terminal to serve single-period customer demands, which are known in distribution when planning, but only revealed with certainty upon vehicle arrival. While most existing research for this problem focuses on recourse strategies where each vehicle operates independently, this paper alternatively considers a strategy in which vehicles may be coordinated in pairs. A tabu search heuristic is developed to find good solutions to VRPSD instances with homogeneous customer demand distributions given this alternative recourse strategy. Finally, a computational study on a set of test problems with a variety of demand distributions reveals that the paired-recourse strategy may lead to expected travel cost savings of 3% to 25% on problems with 50 or more customers. [ABSTRACT FROM AUTHOR]

This paper is concerned with the performance of multicommodity capacitated networks in a deterministic but time-dependent environment. For a given time-dependent origin-destination table, this paper asks if it is easy to find a way of regulating the input flows into the network to avoid queues from growing internally, i.e., to avoid capacity violations. Problems of this type are conventionally approached in the traffic/transportation field with variational methods such as control theory (if time is continuous) and with mathematical programming (if time is discrete). However, these approaches can only be expected to work well if the set of feasible solutions is convex. Unfortunately, it is found in this paper that this is not the case. It is shown that continuous-time versions of the problem satisfying the smoothness conditions of control theory can have a finite but very large number of feasible solutions. The same happens for the discrete-time case. These difficulties arise even with the simplest version of the problem (with unique origin-destination paths, perfect information, and deterministic travel times). The paper also shows that the continuous-time feasibility problem is NP-hard, and that if we restrict our attention to (practical) problems whose data can be described with a finite number of bits (e.g., in discrete time), then the problem is N-complete. These results are established by showing that the problem instances of interest can be related to the Directed Hamiltonian Path problem by a polynomial transformation. [ABSTRACT FROM AUTHOR]

The competition for baseball play-off spots—the fabled pennant race—is one of the most closely watched American sports traditions. While play-off race statistics, such as games back and magic number, are informative, they are overly conservative and do not account for the remaining schedule of games. Using optimization techniques, one can model schedule effects explicitly and determine precisely when a team has secured a play-off spot or has been eliminated from contention. The RIOT Baseball Play-off Races Web site developed at the University of California, Berkeley, provides automatic updates of new, optimization-based play-off race statistics each day of the major league baseball season. In developing the site, we found that we could determine the first-place elimination status of all teams in a division using a single linear-programming formulation, since a minimum win threshold for teams finishing in first place applies to all teams in a division. We identified a similar (but weaker) result for the problem of play-off elimination with wildcard teams. [ABSTRACT FROM AUTHOR]