Planning and Operation of a Crowdsourced Package Delivery System: Models, Algorithms and Applications

Crowdsourced delivery, or crowd shipping, is a delivery service in which logistics service providers contract delivery services from the public (i.e., non-employees), instead of providing delivery services exclusively with an in-house logistics workforce. Studies in the literature formulate the crowdsourced delivery problem as a Vehicle Routing Problem (VRP) and propose a variety of solution approaches for small problem instances. Conversely, this dissertation focuses on large-scale crowdsourced systems and problem instances, which have significant promise and importance, respectively, for effective planning and efficient operation crowdsourced systems in the real-world.

This dissertation provides a taxonomy of urban last-mile crowdsourced delivery, defines the crowdsourced shared-trip delivery problem, presents two separate models for the crowdsourced shared-trip delivery problem, and develops a novel decomposition heuristic tailored to solve large-scale crowdsourced delivery problems. The taxonomy identifies three types of urban last-mile crowdsourced delivery—crowdsourced trip-based delivery, crowdsourced time-based delivery, and crowdsourced shared-trip delivery. This dissertation focuses on the crowdsourced shared-trip delivery problem in which crowdsourced drivers communicate their origin and destination of an upcoming trip to the logistics provider and, if the logistics provider can identify packages for the driver to pickup and deliver without significant detours, the logistics provider assigns packages to and compensates the driver. The dissertation models the crowdsourced delivery problem by adapting VRP formulations from the literature as well as using a set partitioning formulation. The set partitioning formulation leads to an alternative solution method for large-scale instances that involves decomposing the problem into several subproblems. The novel decomposition heuristic contains a series of subproblems that are solved in this dissertation using various solution algorithms, including, budgeted k-shortest path, large scale bi-partite matching, package switching and vehicle routing. The decomposition heuristic achieves high quality results and significantly shorter computational time in comparison to an exact solution method.

In the numerical case study, the dissertation analyzes various factors that may impact the effectiveness and efficiency of urban crowdsourced delivery. The results indicate that crowdsourced shared-trip delivery service can reduce total delivery cost by between 20% to 50%, compared to a delivery service that exclusively uses its own dedicated vehicles and drivers. Vehicle miles travelled (VMT) savings depend on the origin location (i.e., home locations or the store/depot) of crowdsourced drivers that participate in the service. In addition, the results show that dedicated vehicles are still required since even a considerably large set of candidates shared crowdsourced vehicles cannot usually serve all packages.