•We optimize warehouse order picking/collection via autonomous mobile robots.•We present a decomposition heuristic that solves the deterministic problem fast.•We provide a novel two-step ...multiple-scenario approach for the stochastic case.•We analyze the value of optimization on real-world order data.•We derive important insights on system setup and method performance.
To meet the expectations of demanding customers, there is a trend toward warehouse automation, especially in large e-commerce distribution centers. In this context, this paper considers robotized sorting systems, where autonomous mobile robots are applied to automatically sort products after picking. The robots load individual pieces of stock keeping units (SKUs) at a loading station, drive to the collection points temporarily associated with customer orders, and autonomously release them, e.g., by tilting a tray mounted on top of each robot. In these systems, a huge number of products approach the loading station with an interarrival time of very few seconds. Hence, we have a very challenging real-time environment for the following decisions: First, since pieces of the same SKU are interchangeable among orders with a demand for this specific SKU, we must assign pieces to suitable orders. Furthermore, each order must be temporarily assigned to a collection point. Finally, we must assign robots to transport jobs. These interdependent decisions become even more involved, since we (typically) do not possess complete knowledge on the arrival sequence but have merely a restricted lookahead of the next approaching products. We show that even in such a fierce environment sophisticated optimization, based on a novel two-step multiple-scenario approach applied under real-time conditions, can be a serviceable tool to significantly improve the sortation throughput. With our approach a limited-lookahead system is shown to almost reach the performance of a (hypothetical) system with complete knowledge on the approaching products.
Same-day delivery has become a very important challenge for e-commerce providers. However, effective delivery concepts are still not established. In this paper, we analyze the potential of combining ...parcel pickup stations and autonomous vehicles for same-day delivery. This combination may allow for consolidation of goods, automated delivery processes, and reduced operation costs. We consider the problem on the operational planning level. A depot, a set of pickup stations, and an autonomous delivery fleet are given. Customers dynamically order goods to a preferred pickup station and expect fast service. The goods need to be delivered from the depot to the preferred pickup station or another pickup station in the close neighborhood. Autonomous vehicles are directly dispatched between the depot and the stations. To decide where and when to dispatch a vehicle and about the corresponding goods to load, we present a policy function approximation (PFA). Our intuitive PFA allows real-time decision making while balancing the tradeoff between fast delivery and consolidation. We conduct an extensive computational study for the pickup station network of the city of Braunschweig. We show how our delivery concept allows fast delivery for up to 100 delivered goods per vehicle and day. We further pair the PFA with a value function approximation to account for heterogeneity in demand. We finally derive important managerial insights for strategical and tactical planning and present an extensive outlook on promising future research directions.
•Embeds stochastic dynamic vehicle routing (SDVR) in the prescriptive analytics (PA) framework.•Presents comprehensive overview on SDVR models and their components.•State of the art literature review ...for SDVR.•Recommendation on how to approach SDVR-problems with PA-methods.
Stochastic dynamic vehicle routing problems have become an essential part of logistics and mobility services. In such problems, a sequence of vehicle routing decisions has to be made in reaction and anticipation of newly revealed stochastic information. To this end, a variety of computational operations research methods has emerged in the literature, increasingly integrating potential future information in their decision making. The integration of information models into decision models via computational methods is known as prescriptive analytics, the most recent advance of business analytics. In this paper, we explore the existing work and future potential of prescriptive analytics for stochastic dynamic vehicle routing. We identify the characteristics of decision models and information models unique in stochastic dynamic vehicle routing and analyze how different methodology meets the characteristics' requirements. We use the insights to derive recommendations about promising methodology when approaching specific stochastic dynamic vehicle routing problems.
•We address the dynamic same-day delivery problem with fleets of drones and vehicles.•We present a deep Q-learning approach exploiting both state and action space information.•We provide a detailed ...analysis in the functionality of our method and the resulting policies.
In this paper, we consider same-day delivery with vehicles and drones. Customers make delivery requests over the course of the day, and the dispatcher dynamically dispatches vehicles and drones to deliver the goods to customers before their delivery deadline. Vehicles can deliver multiple packages in one route but travel relatively slowly due to the urban traffic. Drones travel faster, but they have limited capacity and require charging or battery swaps. To exploit the different strengths of the fleets, we propose a deep Q-learning approach. Our method learns the value of assigning a new customer to either drones or vehicles as well as the option to not offer service at all. In a systematic computational analysis, we show the superiority of our policy compared to benchmark policies and the effectiveness of our deep Q-learning approach. We also show that the combination of state and action features is very valuable and that our policy can maintain effectiveness when demand data and the fleet size change moderately.
In this paper, we analyze how drones can be combined with regular delivery vehicles to improve same‐day delivery performance. To this end, we present a dynamic vehicle routing problem with ...heterogeneous fleets. Customers order goods over the course of the day. These goods are delivered either by a drone or by a regular transportation vehicle within a delivery deadline. Drones are faster, but have a limited capacity as well as require charging after use. In the same‐day context, vehicle capacity is not a constraint, but vehicles are slow due to urban traffic. To decide whether an order is delivered by a drone or by a vehicle, we present a policy function approximation based on geographical districting. Our computational study reveals two major implications. First, geographical districting is highly effective increasing the expected number of same‐day deliveries. Second, a combination of drone and vehicle fleets may significantly reduce the required delivery resources.
•First paper presenting anticipatory methods for dynamic control in bike sharing.•Comprehensive computational study based on real-world data of Minneapolis.•Approximate dynamic programming method ...allows autonomous adaption to instance data.•New and generic method using value function approximation for policy search.
We present the stochastic-dynamic inventory routing problem for bike sharing systems (SDIRP). The objective of the SDIRP is to avoid unsatisfied demand by dynamically relocating bikes during the day. To anticipate potential future demands in the current inventory decisions, we present a dynamic lookahead policy (DLA). The policy simulates future demand over a predefined horizon. Because the heterogeneous demand patterns over the course of the day, the DLA horizons are time-dependent and autonomously parametrized by means of value function approximation, a method of approximate dynamic programming. We compare the DLA with conventional relocation strategies from the literature and lookahead policies with static horizons. Our study based on real-world data by the bike sharing system of Minneapolis (Minnesota, USA) reveals the benefits of both anticipation by lookaheads as well as the time-dependent horizons of the DLA. We additionally show how the DLA is able to autonomously adapt to the demand patterns.
Although increasing amounts of transaction data make it possible to characterize uncertainties surrounding customer service requests, few methods integrate predictive tools with prescriptive ...optimization procedures to meet growing demand for small-volume urban transport services. We incorporate temporal and spatial anticipation of service requests into approximate dynamic programming (ADP) procedures to yield dynamic routing policies for the single-vehicle routing problem with stochastic service requests, an important problem in city-based logistics. We contribute to the routing literature as well as to the field of ADP. We combine offline value function approximation (VFA) with online rollout algorithms resulting in a high-quality, computationally tractable policy. Our offline–online policy enhances the anticipation of the VFA policy, yielding spatial and temporal anticipation of requests and routing developments. Our combination of VFA with rollout algorithms demonstrates the potential benefit of using offline and online methods in tandem as a hybrid ADP procedure, making possible higher-quality policies with reduced computational requirements for real-time decision making. Finally, we identify a policy improvement guarantee applicable to VFA-based rollout algorithms, showing that base policies composed of deterministic decision rules lead to rollout policies with performance at least as strong as that of their base policy.
Same-day delivery with fair customer service Chen, Xinwei; Wang, Tong; Thomas, Barrett W. ...
European journal of operational research,
07/2023, Volume:
308, Issue:
2
Journal Article
Peer reviewed
•We introduce the concept of customer fairness to urban delivery.•We provide a multi-objective Markov decision process model that maximizes both business utility and customer fairness.•We propose a ...deep Q-learning solution approach that improves fairness with a small loss of utility.•We provide a comprehensive analysis of how considering fairness changes customer experience.
The demand for same-day delivery (SDD) has increased rapidly in the last few years and has particularly boomed during the COVID-19 pandemic. The fast growth is not without its challenge. In 2016, due to low concentrations of memberships and far distance from the depot, certain minority neighborhoods were excluded from receiving Amazon’s SDD service, raising concerns about fairness. In this paper, we study the problem of offering fair SDD service to customers. The service area is partitioned into different regions. Over the course of a day, customers request for SDD service, and the timing of requests and delivery locations are not known in advance. The dispatcher dynamically assigns vehicles to make deliveries to accepted customers before their delivery deadline. In addition to overall service rate (utility), we maximize the minimal regional service rate across all regions (fairness). We model the problem as a multi-objective Markov decision process and develop a deep Q-learning solution approach. We introduce a novel transformation of learning from rates to actual services, which creates a stable and efficient learning process. Computational results demonstrate the effectiveness of our approach in alleviating unfairness both spatially and temporally in different customer geographies. We show this effectiveness is valid with different depot locations, providing businesses with an opportunity to achieve better fairness from any location. We also show that the proposed approach performs efficiently when serving heterogeneously wealthy districts in the city.
•This paper introduces a new dynamic multi-period vehicle routing problem.•We develop an anticipatory policy based on offline value function approximation.•Our policy achieves significant ...improvements compared to benchmark policies.•A detailed analysis highlights how multi-periodicity impacts decision making.
In practical applications like parcel or technician services, customers request service during the day. Service providers decide whether to accept a customer for same-day service or to defer a customer due to resource limitations. Some requests are therefore postponed to the following day. To satisfy customer expectations, service providers aim on a high number of same-day services. Still, acceptance decisions not only affect the performance on the current, but also on the following day. Suitable acceptance, postponement, and routing decisions therefore should anticipate future routing and requests in both the current and the next day(s). The resulting decision problem is a dynamic multi-period vehicle routing problem with stochastic service requests. To approximately solve the Markov decision process of the presented problem, we present an anticipatory dynamic policy based on approximate dynamic programming. This policy estimates the potential of problem states with respect to future same-period services within and over the periods. Our policy draws on value function approximation, state space aggregation, and on a classification of the periods. We compare our policy to several policies from the literature. We analyze how and when multi-period anticipation improves the solution quality significantly and how the newly developed state space classification is essential to achieve anticipation. We finally show how multi-period anticipation changes the acceptance behavior to less discrimination of rural customers and to a fairer geographical distribution of same-day services in comparison to single-period anticipation.
Parcel services route vehicles to pick up parcels in the service area. Pickup requests occur dynamically during the day and are unknown before their actual request. Because of working hour ...restrictions, service vehicles only have a limited time to serve dynamic requests. As a result, not all requests can be confirmed. To achieve an overall high number of confirmed requests, dispatchers have to budget their time effectively by anticipating future requests. To determine the value of a decision, i.e., the expected number of future confirmations given a point of time and remaining free time budget, we present an anticipatory time budgeting heuristic (ATB) drawing on methods of approximate dynamic programming. ATB frequently simulates a problem’s realization to subsequently approximate the values for every vector of point of time and free time budget to achieve an approximation of an optimal decision policy. Since the number of vectors is vast, we introduce the dynamic lookup table (DLT), a general approach adaptively partitioning the vector space to the approximation process. Compared with state-of-the-art benchmark heuristics, ATB allows an effective use of the time budget resulting in anticipatory decision making and high solution quality. Additionally, the DLT significantly strengthens and accelerates the approximation process.
The online appendix is available at
https://doi.org/10.1287/trsc.2016.0719
.
PDF
