Exact solutions for the collaborative pickup and delivery problem

Area of Science:

• Operations Research
• Logistics Management
• Transportation Science

Background:

• Pickup and delivery services face complex routing and scheduling challenges.
• Collaborative models aim to improve efficiency and reduce costs in logistics.
• Uneven workload distribution can lead to inefficiencies in carrier collaborations.

Purpose of the Study:

• To investigate the central authority's decision problem in collaborative pickup and delivery.
• To formulate and solve the multi-depot traveling salesman problem with pickups and deliveries.
• To introduce and evaluate minimum workload constraints for balanced distribution.

Main Methods:

• Formulation as a multi-depot traveling salesman problem with pickups and deliveries.
• Application and comparison of three exact solution approaches: Benders decomposition and column generation.
• Introduction of minimum workload constraints to ensure equitable task distribution.

Main Results:

• Benders decomposition is effective for the original problem.
• Column generation significantly outperforms Benders decomposition for the problem with minimum workload constraints.
• Computational time analysis of different solution approaches.

Conclusions:

• Column generation is the preferred method for collaborative pickup and delivery problems with workload balancing.
• The study provides benchmark results for decentralized collaborative mechanisms.
• Optimized redistribution of customer requests minimizes total costs in carrier collaborations.