UC Irvine

Online shopping has increased steadily over the past decade that has led to a dramatic increase in the demand for urban package deliveries. Crowdsourced delivery, or crowd shipping, has been proposed and implemented by logistics companies in response to the growth in package delivery business. Crowdsourced delivery 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. This dissertation studies different types of urban last-mile crowdsourced delivery services and provides a taxonomy for crowdsourced package delivery. Urban package crowdsourced delivery can be categorized in terms of the way packages are delivered and the role/tasks of crowdsourced drivers. Given these two dimensions, this study identifies three types of urban package crowdsourced delivery, namely, crowdsourced time-based delivery, crowdsourced trip-based delivery, and crowdsourced shared-trip delivery. Crowdsourced time-based delivery drivers are paid for their idle time and work as sub-contractors. Crowdsourced trip-based delivery matches drivers with individual tasks and utilizes the drivers for specific delivery trips. The last type, crowdsourced shared-trip delivery utilizes the common segments of a crowdsourced personal vehicle trip to deliver packages. In this type, the package shares part of the driver trip. The literature formulates the crowdsourced delivery problem as a Vehicle Routing Problem (VRP) and proposes a variety of solution approaches. However, all the solution algorithms are limited to relatively small-scale problems. In addition, the factors that impact the efficiency and effectiveness of crowdsourced delivery have not been thoroughly analyzed. To bridge the gap in crowdsourced delivery and urban freight logistics, this dissertation provides an alternative formulation for the static crowdsourced shared-trip delivery problem and proposes a novel decomposition heuristic to solve the problem. The alternative formulation is based on the set partitioning problem. The novel decomposition heuristic handles packages that are served by shared personal vehicles (SPVs) and dedicated vehicles (DVs), separately. After that, the algorithm deploys a package switch procedure, which rearranges packages between SPVs and DVs. The dissertation discusses various algorithms employed to solve different sub-problems, such as the budgeted k-shortest path, large scale bi-partite matching, decision of package switching and vehicle routing. To validate the models and algorithms, this dissertation presents a numerical case study that uses the network of the City of Irvine, CA, USA. The results of the numerical study unveil interesting results that are valuable to both researchers and industrial practitioners. The results indicate that crowdsourced shared-trip delivery service can reduce total cost by between 20% to 50%, compared to a delivery service that exclusively uses its own dedicated vehicles and drivers. However, the results show that dedicated vehicles are still required since the shared vehicles are not able to serve all packages even with a considerably large set of candidate shared vehicles. Vehicle Miles Traveled (VMT) savings depend on the crowdsourced driver selection and their trip origins. The dissertation also analyzes and discusses important factors that impact the effectiveness of crowdsourced delivery. In particular, the dissertation includes sensitivity analysis results with respect to changes in the depot location and the willingness of shared vehicles to detour.