Towards Urban Delivery Innovations: Macro- and Micro-Level Models of Crowdshipping

With rapid e-commerce growth, on-demand urban delivery is having a high time especially for food, grocery, and retail, often requiring delivery in a very short amount of time after an order is placed. This imposes significant financial and operational challenges for traditional vehicle-based delivery methods. Crowdshipping, which employs ordinary people with a low pay rate and limited time availability, has emerged as an attractive alternative. The first chapter proposes a multi-tier adaptive memory programming (M-TAMP) to tackle on-demand assignment of requests to crowdsourcees with spatially distributed request origins and destination and crowdsourcee starting points. M-TAMP starts with multiple initial solutions constructed based on different plausible contemplations in assigning requests to crowdsourcees, and organizes solution search through waves, phases, and steps, imitating both ocean waves and human memory functioning while seeking the best solution. The assignment is further enforced by proactively relocating idle crowdsourcees, for which a computationally efficient cluster- and job-based strategy is devised. Numerical experiments demonstrate the superiority of M-TAMP over a number of existing methods, and that relocation can greatly improve the efficiency of crowdsourcee-request assignment. The second chapter investigates the problem of assigning shipping requests to ad hoc couriers in the context of crowdsourced urban delivery. The shipping requests are spatially distributed each with a limited time window between the earliest time for pickup and latest time for delivery. The ad hoc couriers, termed crowdsourcees, also have limited time availability and carrying capacity. We propose a new deep reinforcement learning (DRL)-based approach to tackling this assignment problem. A deep Q network (DQN) algorithm is trained which entails two salient features of experience replay and target network that enhance the efficiency, convergence, and stability of DRL training. More importantly, this chapter makes three methodological contributions: 1) presenting a comprehensive and novel characterization of crowdshipping system states that encompasses spatial-temporal and capacity information of crowdsourcees and requests; 2) embedding heuristics that leverage information offered by the state representation and are based on intuitive reasonings to guide specific actions to take, to preserve tractability and enhance efficiency of training; and 3) integrating rule-interposing to prevent repeated visiting of the same routes and node sequences during routing improvement, thereby further enhancing the training efficiency by accelerating learning. The computational complexities of the heuristics and the overall DQN training are investigated. The effectiveness of the proposed approach is demonstrated through extensive numerical analysis. The results show the benefits brought by the heuristics-guided action choice, rule-interposing, and having time-related information in the state space in DRL training, the near-optimality of the solutions obtained, and the superiority of the proposed approach over existing methods in terms of solution quality, computation time, and scalability. The third chapter studies a two-echelon urban delivery system that substitutes traditional truck-based delivery by crowdsourcees for the first leg and autonomous delivery robots for the second leg. We consider that a delivery service provider (DSP) forms and assigns delivery jobs (a set of requests) at pickup stations, where a job is assigned to a crowdsourcee who carry the requests in the job to a micro-station, which is a temporary holding facility and located near end customers. From the micro-station, the job is resumed by a robot which completes the delivery. For the first time in the literature, this work proposes an analytical framework to characterize the aggregate performance of such a two-echelon system. The framework is useful in that it enables system-level analysis of delivery performance. By characterizing the first leg as a closed queueing network and the second leg using continuum approximation, we formulate a strategic system optimization model that seeks: 1) the optimal size of the crowdsourcee fleet while considering crowdsourcee rebalancing to balance the spatial distribution between crowdsourcees and jobs, and 2) the optimal size of the robot fleet at each micro-station. To solve the model, we develop a decomposition-based approach which leverages mean value analysis (MVA) to solve the queueing network steady state and a tailored iterative procedure to compute crowdsourcee routing probability matrix incorporating rebalancing. The model and solution algorithm are implemented through extensive numerical experiments, which validate their effectiveness and yield practical insights.