ABSTRACT In response to the increasing volume of parcels, last‐mile delivery innovations are exploring the integration of multiple delivery modes. The most prominent examples are delivery vans that, next to being the base for the delivery tasks of their human drivers, also function as mobile launching platforms for drones or autonomous delivery robots. This paper investigates a novel approach involving the cooperation of a mobile parcel locker, which repositions continuously to facilitate self‐pickup by urban customers, alongside the parallel home‐delivery tasks of its human driver. For a predetermined set of customers, divided into home‐delivery and self‐service categories, we aim to identify a synchronized route for a locker‐driver tandem that minimizes the total delivery duration. Based on a comprehensive analysis of the problem's computational complexity, we develop efficient solution methods for the deterministic version of the problem. Additionally, we address the scenario with stochastic response times of self‐service customers. From a managerial perspective, we examine the service‐cost trade‐off: accommodating convenient pickup times for self‐service customers can disrupt route efficiency, and vice versa. Our findings indicate that effective synchronization of both delivery modes can provide a suitable balance between service quality and operational efficiency.

Many online retailers apply scattered (or mixed-shelves) storage in the picking areas of their warehouses. Instead of keeping unit loads together, individual pieces of stock keeping units (SKUs) are stored on various shelves throughout the warehouse. This storage strategy increases the probability that—whatever it is that customers order jointly—somewhere in the warehouse these products will be located in close proximity. Hence, a picker can retrieve them without excessive unproductive walking. The price for this advantage on the picking side, however, is additional effort for the replenishment workers (also denoted as stowers) when restocking the shelves. Instead of moving only a single homogeneous unit load toward an SKU’s designated storage position, each stower has to travel along multiple open shelf spaces until all products on the cart are stored on shelves. The resulting stower routing problem is equivalent to the well-known prize collecting traveling salesman problem (PCTSP). While the PCTSP for general graphs is known to be strongly [Formula: see text]-hard, we show that in a warehousing environment, where all open storage positions are located along parallel aisles, it is only binary [Formula: see text]-hard. The special parallel-aisle structure allows us to derive an exact solution algorithm with pseudo-polynomial runtime, which solves even instances with hundreds of open storage positions to proven optimality in just a few seconds. Our computational tests show that the performance gains of an optimized stowing process over the status quo, where stowers operate without decision support, are significant. Especially, when the fill level of a warehouse is high, directing stowers on optimized routes promises huge improvements. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the German Science Foundation/Deutsche Forschungsgemeinschaft (DFG) by the grant “Routing of human and automated order pickers in modern warehouses” (BO 3148/14-1 and BO 1972/2-1). Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0173 .

To reduce unproductive picker walking in traditional picker-to-parts warehousing systems, automated guided vehicles (AGVs) are used to support human order pickers. In an AGV-assisted order-picking system, each human order picker is accompanied by an AGV during the order-picking process. AGVs receive the picked items and, once a picking order is complete, autonomously bring the collected items to the shipping area. Meanwhile, a new AGV is requested to meet the picker at the first storage position of the next picking order. Thus, the picker does not have to return to a central depot and continuously picks order after order. This paper addresses both the routing of an AGV-assisted picker through a single-block, parallel-aisle warehouse and the sequencing of incoming orders. We present an exact polynomial time routing algorithm for the case of a given order sequence, which is an extension of the algorithm of Ratliff and Rosenthal [ Ratliff HD, Rosenthal AS (1983) Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem. Oper. Res. 1(3):507–521], and a heuristic for the case in which order sequencing is part of the problem. In addition, we investigate the use of highly effective traveling salesman problem (TSP) solvers that can be applied after a transformation of both problem types into a standard TSP. The numerical studies address the performance of these methods and study the impact of AGV usage on picker travel: by using AGVs to avoid returns to the depot and by sequencing in (near-) optimal fashion, picker walking can be reduced by about 20% compared with a traditional setting. Sharing AGVs among the picker workforce enables a pooling effect so that, in larger warehouses, only about 1.5 AGVs per picker are required to avoid picker waiting. Summary of Contribution: New technologies, such as automatic guided vehicles (AGVs) are currently considered as options to increase the efficiency of the order-picking process in warehouses, which is responsible for a large part of operational warehousing costs. In addition, picker-routing decisions are more and more often based on algorithmic decision support because of their relevance for decreasing unproductive picker walking time. This paper addresses both aspects and investigates routing algorithms for AGV-assisted order picking in parallel-aisle warehouses. We present a dynamic programming routine with polynomial runtime to solve the problem variant in which the sequence of picking orders is fixed. For the variant in which this sequence is a decision, we show that the problem becomes NP-hard, and we propose a greedy heuristic and investigate the use of state-of-the-art exact and heuristic traveling salesman problem solution methods to address the problem. The numerical studies demonstrate the effectiveness of the algorithms and indicate that AGV assistance promises strong improvements in the order-fulfillment process. Because of the practical relevance of AGV-assisted order picking and the presented algorithmic contributions, we believe that the paper is relevant for practitioners and researchers alike.

Last mile deliveries with unmanned aerial vehicles (also denoted as drones) are seen as one promising idea to reduce excessive road traffic. To overcome the difficulties caused by the comparatively short operating ranges of drones, an innovative concept suggests to apply trucks as mobile landing and take‐off platforms. In this context, the paper on hand schedules the delivery to customers by drones for given truck routes. Given a fixed sequence of stops constituting a truck route and a set of customers to be supplied, we aim at a drone schedule (i.e., a set of trips each defining a drone's take‐off and landing stop and the customer serviced), such that all customers are supplied and the total duration of the delivery tour is minimized. We differentiate whether multiple drones or just a single one are placed on a truck and whether or not take‐off and landing stops have to be identical. We provide an analysis of computational complexity for each resulting subproblem, introduce efficient mixed‐integer programs, and compare all cases with regard to their potential of reducing the delivery effort on the last mile.

Tariff design is among the most elementary decision problems to be solved in every public transportation network. This article focuses on alternative zone‐based tariffs, which vary in the way zones are cut (ring structure vs. connected zones) and fares are calculated (counting zones, cumulative pricing, and maximum pricing), and compares their ability to exploit the customers’ willingness to pay. For this purpose, we formulate six versions of the tariff design problem, investigate their computational complexity, and develop suited mixed‐integer models. Our comprehensive computational study reveals that tariffs based on cumulative pricing outperform traditional distance‐based tariffs and are best suited to exploit the customers’ willingness to pay. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(4), 349–366 2017