A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm.

Area of Science:

• Operations Research
• Logistics Management
• Computational Optimization

Background:

• Online food delivery platforms face complex logistical challenges.
• Coordinating pickups from multiple restaurants and deliveries to customers requires efficient routing.
• Existing vehicle routing models struggle with time windows and capacity constraints for multi-restaurant orders.

Purpose of the Study:

• To develop an advanced mathematical formulation for the multi-restaurant food delivery vehicle routing problem.
• To minimize costs while adhering to customer time windows and vehicle capacity limits.
• To improve the efficiency of solving large-scale delivery routing instances.

Main Methods:

• An augmented two-index mathematical formulation was developed.
• A branch-and-cut algorithm was employed to solve the problem.
• Problem-specific valid inequalities were integrated to enhance solution performance.

Main Results:

• The proposed formulation significantly improves solution efficiency compared to existing methods.
• The approach successfully solved a majority of benchmark instances with 25, 35, and 50 nodes.
• Many previously unsolved instances were optimally solved using this new method.

Conclusions:

• The augmented two-index formulation offers a more effective approach to vehicle routing for multi-restaurant food delivery.
• This method enhances the ability to solve complex, real-world logistics problems.
• The research advances the field of combinatorial optimization in delivery logistics.