Tackling the Crowdsourced Shared-Trip Delivery Problem at Scale with a Novel Decomposition Heuristic
0
🛠️
Sign in to get full access
Overview
- This paper presents a novel algorithm called the Decomposition Heuristic (D-H) to solve large-scale instances of the urban crowdsourced shared-trip delivery (CSD) problem.
- The CSD problem involves dedicated delivery vehicles (DVs) and shared personal vehicles (SPVs) fulfilling package delivery orders, where the SPVs have their own trip origins and destinations.
- The D-H algorithm first assigns as many package delivery orders (PDOs) to SPVs as possible, then solves a multi-vehicle routing problem for the remaining PDOs assigned to DVs.
- The paper also analyzes the impact of factors like the number of participating SPVs and their willingness to detour on the performance of city-scale CSD systems.
Plain English Explanation
The paper describes a new approach to solve a complex logistics problem called the crowdsourced shared-trip delivery (CSD) problem. In this problem, there are two types of vehicles involved in delivering packages: dedicated delivery vehicles (DVs) and shared personal vehicles (SPVs).
The key idea is to use SPVs, which are regular people's personal cars, to help deliver some of the packages. This can potentially save costs and reduce the number of delivery vehicles needed. However, the challenge is that the SPVs have their own trip origins and destinations, so their routes need to be coordinated with the package deliveries.
The researchers developed a new algorithm called the Decomposition Heuristic (D-H) to solve this problem. The D-H first tries to assign as many package delivery orders (PDOs) as possible to the SPVs, by figuring out the best routes for each SPV to take. Then, it solves a separate routing problem for the remaining PDOs that need to be delivered by the dedicated delivery vehicles (DVs).
The paper also analyzes how factors like the number of participating SPVs and their willingness to detour from their usual routes can impact the overall performance of the CSD system. The results suggest that while CSD can reduce delivery costs, it may also increase the total distance traveled by the vehicles.
Technical Explanation
The Decomposition Heuristic (D-H) algorithm proposed in the paper works as follows:
- SPV Assignment: The D-H first enumerates the set of feasible routes each SPV can take and solves a package delivery order (PDO)-SPV-route assignment problem to assign as many PDOs to SPVs as possible.
- DV Routing: For the remaining PDOs that need to be delivered by dedicated delivery vehicles (DVs), the D-H solves a multi-vehicle routing problem with time-window, tour duration, and capacity constraints using an insertion heuristic.
- Route Improvement: Finally, the D-H seeks potential solution improvements by switching PDOs between SPV and DV routes through a simulated annealing (SA)-inspired procedure.
The paper compares the performance of the D-H algorithm to a commercial solver and a large neighborhood search algorithm. The results show that the D-H outperforms the commercial solver in terms of computational efficiency while obtaining near-optimal solutions for small problem instances. The SA-inspired switching procedure also outperforms the large neighborhood search algorithm in terms of run time, with comparable solution quality.
The paper then uses the D-H algorithm to analyze the impact of several factors on the performance of city-scale CSD systems, such as the number of participating SPVs and the maximum willingness to detour of SPVs. The findings suggest that while CSD can substantially reduce delivery costs, it may also increase the total vehicle miles traveled.
Critical Analysis
The paper provides a comprehensive Transformer-based stagewise decomposition approach to solve the large-scale CSD problem, which is a significant contribution to the field. The authors have carefully designed the D-H algorithm and conducted thorough experiments to evaluate its performance.
However, the paper does not delve into the potential limitations or drawbacks of the CSD model. For instance, the impact on traffic congestion, emissions, and the willingness of private vehicle owners to participate in such a system are not discussed in depth. Additionally, the paper does not consider the potential privacy and security concerns that may arise when using personal vehicles for commercial delivery purposes.
Furthermore, the analysis of the impact of various factors on CSD system performance is limited to a few specific parameters. It would be interesting to see a more comprehensive sensitivity analysis that examines the influence of other factors, such as the distribution of package sizes, the geographical layout of the city, and the availability of charging infrastructure for electric vehicles.
Despite these minor limitations, the paper presents a valuable contribution to the literature on crowdsourced delivery systems and provides a solid foundation for further research in this area.
Conclusion
This paper introduces a novel Decomposition Heuristic (D-H) algorithm to solve the large-scale crowdsourced shared-trip delivery (CSD) problem, which involves using both dedicated delivery vehicles (DVs) and shared personal vehicles (SPVs) to fulfill package delivery orders.
The D-H algorithm efficiently assigns PDOs to SPVs and solves a multi-vehicle routing problem for the remaining PDOs assigned to DVs. The paper also analyzes the impact of factors like the number of participating SPVs and their willingness to detour on the performance of city-scale CSD systems.
The findings suggest that while CSD can significantly reduce delivery costs, it may also increase the total vehicle miles traveled. The algorithms and insights presented in this paper provide valuable tools and information for logistics practitioners and researchers working on improving the efficiency and sustainability of urban delivery systems.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
🛠️
0
Tackling the Crowdsourced Shared-Trip Delivery Problem at Scale with a Novel Decomposition Heuristic
Dingtong Yang, Michael F. Hyland, R. Jayakrishnan
This paper presents a set-partitioning formulation and a novel decomposition heuristic (D-H) solution algorithm to solve large-scale instances of the urban crowdsourced shared-trip delivery (CSD) problem. The CSD problem involves dedicated vehicles (DVs) and shared personal vehicles (SPVs) fulfilling delivery orders, wherein the SPVs have their own trip origins and destinations. The D-H begins by assigning as many package delivery orders (PDOs) to SPVs as possible, where the D-H enumerates the set of routes each SPV can feasibly traverse and then solves a PDO-SPV-route assignment problem. For PDO-DV assignment and DV routing, the D-H solves a multi-vehicle routing problem with time-window, tour duration, and capacity constraints using an insertion heuristic. Finally, the D-H seeks potential solution improvements by switching PDOs between SPV and DV routes through a simulated annealing (SA)-inspired procedure. The D-H outperforms a commercial solver in terms of computational efficiency while obtaining near-optimal solutions for small problem instances. The SA-inspired switching procedure outperforms a large neighborhood search algorithm regarding run time, and the two are comparable regarding solution quality. Finally, the paper uses the D-H to analyze the impact of several relevant factors on city-scale CSD system performance, namely the number of participating SPVs and the maximum willingness to detour of SPVs. Consistent with the existing literature, we find that CSD can substantially reduce delivery costs. However, we find that CSD can increase vehicle miles traveled. Our findings provide meaningful insights for logistics practitioners, while the algorithms illustrate promise for large real-world systems.
Read more6/19/2024
0
CSDO: Enhancing Efficiency and Success in Large-Scale Multi-Vehicle Trajectory Planning
Yibin Yang, Shaobing Xu, Xintao Yan, Junkai Jiang, Jianqiang Wang, Heye Huang
This paper presents an efficient algorithm, naming Centralized Searching and Decentralized Optimization (CSDO), to find feasible solution for large-scale Multi-Vehicle Trajectory Planning (MVTP) problem. Due to the intractable growth of non-convex constraints with the number of agents, exploring various homotopy classes that imply different convex domains, is crucial for finding a feasible solution. However, existing methods struggle to explore various homotopy classes efficiently due to combining it with time-consuming precise trajectory solution finding. CSDO, addresses this limitation by separating them into different levels and integrating an efficient Multi-Agent Path Finding (MAPF) algorithm to search homotopy classes. It first searches for a coarse initial guess using a large search step, identifying a specific homotopy class. Subsequent decentralized Quadratic Programming (QP) refinement processes this guess, resolving minor collisions efficiently. Experimental results demonstrate that CSDO outperforms existing MVTP algorithms in large-scale, high-density scenarios, achieving up to 95% success rate in 50m $times$ 50m random scenarios around one second. Source codes are released in https://github.com/YangSVM/CSDOTrajectoryPlanning.
Read more8/1/2024
0
DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems
Zhi Zheng, Shunyu Yao, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, Ke Tang
The min-max vehicle routing problem (min-max VRP) traverses all given customers by assigning several routes and aims to minimize the length of the longest route. Recently, reinforcement learning (RL)-based sequential planning methods have exhibited advantages in solving efficiency and optimality. However, these methods fail to exploit the problem-specific properties in learning representations, resulting in less effective features for decoding optimal routes. This paper considers the sequential planning process of min-max VRPs as two coupled optimization tasks: customer partition for different routes and customer navigation in each route (i.e., partition and navigation). To effectively process min-max VRP instances, we present a novel attention-based Partition-and-Navigation encoder (P&N Encoder) that learns distinct embeddings for partition and navigation. Furthermore, we utilize an inherent symmetry in decoding routes and develop an effective agent-permutation-symmetric (APS) loss function. Experimental results demonstrate that the proposed Decoupling-Partition-Navigation (DPN) method significantly surpasses existing learning-based methods in both single-depot and multi-depot min-max VRPs. Our code is available at
Read more6/7/2024
0
VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions
Navid Imran, Myounggyu Won
The vehicle routing problem with drones (VRP-D) is to determine the optimal routes of trucks and drones such that the total operational cost is minimized in a scenario where the trucks work in tandem with the drones to deliver parcels to customers. While various heuristic algorithms have been developed to address the problem, existing solutions are built based on simplistic cost models, overlooking the temporal dynamics of the costs, which fluctuate depending on the dynamically changing traffic conditions. In this paper, we present a novel problem called the vehicle routing problem with drones under dynamically changing traffic conditions (VRPD-DT) to address the limitation of existing VRP-D solutions. We design a novel cost model that factors in the actual travel distance and projected travel time, computed using a machine learning-driven travel time prediction algorithm. A variable neighborhood descent (VND) algorithm is developed to find the optimal truck-drone routes under the dynamics of traffic conditions through incorporation of the travel time prediction model. A simulation study was performed to evaluate the performance compared with a state-of-the-art VRP-D heuristic solution. The results demonstrate that the proposed algorithm outperforms the state-of-the-art algorithm in various delivery scenarios.
Read more4/16/2024