TL;DR
This paper tackles the complex challenge of optimizing urban delivery routes by integrating "passing-by" drivers (gig economy workers) alongside traditional professional drivers. They introduce a novel memory-based variable neighborhood search (MVNS) algorithm to balance the diverse needs of all stakeholders, including platform owners, customers, drivers, and authorities, leading to more efficient and potentially greener logistics.
What Problem Does This Paper Address?
The rise of e-commerce has led to a surge in urban logistics, creating significant challenges like increased traffic, emissions, and the need for efficient last-mile delivery. Traditional delivery models struggle to keep up with demand, especially during peak times. This paper addresses this by exploring a "crowdsourcing logistics" model that leverages both professional drivers and occasional "passing-by" drivers. The core problem is how to effectively route and manage these diverse driver pools to satisfy multiple, often conflicting, objectives: minimizing costs for the platform, ensuring timely deliveries for customers, providing fair compensation for drivers (both professional and occasional), and considering environmental impact for authorities. Existing approaches often overlook the complexities of integrating these different driver types and balancing the needs of all involved parties.
Methods
The authors propose a multi-layer comprehensive model for this crowdsourcing logistics problem, which they call the Green Vehicle Routing Problem with Partial Crowdsourcing and Participants' Satisfaction (GVRP-PCPS). To solve this complex optimization problem, they introduce an enhanced algorithm called Memory-based Variable Neighborhood Search (MVNS). MVNS builds upon the classic Variable Neighborhood Search (VNS) by incorporating a "memory-based restart" mechanism. This memory component stores information about successful routes and edges from previous searches, guiding the algorithm to more promising areas of the solution space and preventing it from getting stuck in local optima. They also detail specific neighborhood operators (like Relocate, Swap, 2-OPT, and CrossExchange) used in the shaking and local search phases of MVNS.
Datasets
The paper evaluates their proposed algorithm on two types of datasets:
- Solomon's VRPTW benchmark: Standard instances for vehicle routing problems with time windows were adapted to create test cases for GVRP-PCPS by generating random origins and destinations for occasional drivers.
- Real-life city beer delivery instances: Data from a real-world scenario in Shanghai, including customer locations and road network distances, was used to create more practical test cases.
Key Insights and Ideas
- The Power of the "Passing-By" Driver: Integrating occasional drivers, even with their inherent uncertainties, can significantly improve delivery efficiency and potentially reduce costs for platform owners, especially when compensated appropriately.
- Balancing Conflicting Interests is Crucial: A successful crowdsourcing logistics model must go beyond just cost reduction. It needs to consider the satisfaction of all stakeholders, from customers receiving their goods to drivers earning a living and authorities concerned with environmental impact.
- Memory is Key for Optimization: Simply applying VNS isn't enough. The "memory-based restart" mechanism in MVNS is vital for guiding the search towards better solutions by learning from past successful routes and edges, preventing repetitive exploration of less promising areas.
- Differentiated Pricing Matters: The study highlights that a one-size-fits-all compensation strategy for occasional drivers is not optimal. Tailoring compensation based on driver characteristics (like minimal action cost and variable cost coefficient) can lead to better outcomes for both drivers and the platform.
Key Results
- The proposed MVNS algorithm, particularly the route-based restart version (MVNS-r), demonstrated superior performance compared to classic VNS (CVNS) and the edge-based restart version (MVNS-e) in terms of solution quality on benchmark instances, achieving better results in terms of the Uncovered Customer Rate (UCR).
- Experiments showed that increasing compensation for occasional drivers generally leads to a better UCR, indicating their positive impact on service.
- Analysis of real-life instances revealed that the "multi-delivery" mode for occasional drivers (allowing them to deliver multiple parcels) generally offers better satisfaction and is more acceptable than single-delivery modes, despite potentially having a slightly lower rate of ODs used.
- The study also found that while fuel price and carbon tax can influence the usage of occasional drivers, the impact of carbon tax on operating costs is not always straightforward, suggesting a need for more nuanced carbon pricing strategies.
Limitations and Future Work
The authors acknowledge several limitations:
- Static and Homogeneous Parameters: Many parameters in the model, such as customer characteristics, OD arrival times, and vehicle types, are treated as static and homogeneous. Future work could explore modeling these uncertainties using stochastic programming or behavioral science.
- Multi-Objective Optimization Complexity: The GVRP-PCPS involves multiple objectives that are sometimes conflicting, making optimization challenging. Future research could explore many-objective optimization techniques.
- Carbon Trading Integration: The paper touches upon carbon trading but suggests further research into integrating it more deeply into crowdsourcing logistics for more eco-friendly solutions.
- MVNS-e Performance: While MVNS-e showed promising directions, its performance on benchmark instances was not as strong as MVNS-r. Future work could focus on enhancing MVNS-e by adjusting memory size or exploring different operators.
Summary updated