TL;DR
This paper tackles the complex problem of optimizing delivery routes for individual crowdsourced workers by developing an exact single-agent task selection algorithm. It introduces a novel branch-and-cut approach that efficiently considers the worker's pre-existing routine route, time windows, and task-specific delivery constraints, leading to significant improvements in computational efficiency and solution quality compared to traditional methods.
What Problem Does This Paper Address?
The booming e-commerce industry has placed immense pressure on logistics providers to deliver goods faster and more efficiently. While expanding traditional fleets is unsustainable due to fluctuating demand, crowdsourcing offers a promising solution by leveraging part-time workers. However, for these workers, selecting the most compatible delivery tasks that fit their existing routes and time windows is a significant challenge. Existing approaches often simplify this by ignoring routine routes or using heuristics that result in suboptimal task selections. This paper addresses the need for an exact algorithm that can precisely determine the best set of tasks for a single crowdsourced worker, considering their personal route, time constraints, and the specific delivery time windows of each task.
Methods
The authors formulate the problem as an Integer Linear Program (ILP). To overcome the scalability issues of a pure ILP approach, they develop a branch-and-cut (BnC) algorithm. This algorithm combines a branch-and-bound process with cutting-plane methods to tighten the bounds of the linear relaxation.
Key methodological innovations include:
- Novel Valid Inequalities: The paper introduces several new classes of valid inequalities (cuts) designed to tighten the ILP formulation. These include:
- Subtour-Elimination Constraints: Adapted for the specific problem structure.
- Capacity Constraints: Simultaneously considering volume and weight limits.
- Routine Sequence Constraints: Ensuring the worker adheres to their pre-defined route order.
- Infeasible Path Constraints: To prune fractional solutions that are invalid in the integer solution.
- Enforced Delivery Constraints: To manage aggregated pickup nodes.
- Efficient Separation Heuristics: Instead of solving separation problems exactly (which is computationally expensive), the authors devise heuristics to generate these cuts. These heuristics iteratively construct paths based on fractional flows from the LP solution to identify violated constraints and generate relevant cuts.
- Selective Cut Generation: To further improve efficiency, separation problems are only solved when a branch-and-bound node updates the LP bound, avoiding unnecessary computations.
Datasets
The paper does not use pre-existing datasets. Instead, it introduces a method for generating synthetic problem instances. These instances are characterized by parameters such as the number of routine nodes, pickup nodes, delivery nodes, agent capacity limits, and the allowed additional detour time. The generation process involves defining a fixed agent routine route and then randomly assigning pickup and delivery nodes, along with their associated time windows.
Key Insights and Ideas
- The Importance of Routine Routes: The paper strongly emphasizes that incorporating the worker's pre-existing routine route is crucial for both efficiency and sustainability. Ignoring it leads to significant inefficiencies.
- Heuristics Fall Short: A simple greedy heuristic, while fast, only achieves 40-60% of the optimal solution, highlighting the need for exact methods.
- BnC with Custom Cuts is Key: The branch-and-cut approach, especially when augmented with the newly developed valid inequalities, significantly outperforms a plain ILP formulation in terms of computational resources required to reach optimality.
- Synergy of Cuts: Combining different classes of valid inequalities (SE, CA, RS, IP, ED) leads to the most substantial improvements in both the number of explored branch-and-bound nodes and the CPU time.
- Sustainability Impact: The crowdsourcing paradigm, when planned optimally using this algorithm, can lead to substantial reductions in carbon footprint (around 70% saving in travel distance compared to a dedicated vehicle).
Key Results
- Optimality Achieved: The proposed branch-and-cut algorithm successfully reaches optimality for all tested numerical instances.
- Computational Efficiency: The BnC approach with all cuts implemented reduces the number of processed BnB nodes by nearly 50% and improves the median CPU time by approximately 60% compared to the plain ILP formulation.
- Greedy Heuristic Gap: The greedy heuristic exhibits optimality gaps of 40-60% compared to the optimal solution found by the ILP and BnC methods.
- Carbon Emission Reduction: The approach demonstrates the potential for significant carbon emission savings, with an average of around 70% reduction in travel distance for deliveries when compared to a dedicated vehicle.
Limitations and Future Work
- Single Agent Focus: The current algorithm is designed for a single crowdsourced worker. The authors acknowledge that a natural next step is to generalize the approach to handle multiple agents simultaneously.
- Scalability of ILP: While the BnC approach significantly improves scalability, the pure ILP formulation still struggles with larger problem instances, limiting its practical application without the proposed enhancements.
- Heuristic Separation: While effective, the separation heuristics are not exact. Future work could explore more sophisticated or exact separation methods if computational budgets allow.
Summary updated