1638. An LP-based local-search algorithm for the Online Food Delivery Platform Routing Problem
Invited abstract in session WA-58: Food delivery, stream Vehicle Routing and Logistics.
Wednesday, 8:30-10:00Room: Liberty 1.13
Authors (first author is the speaker)
| 1. | Ye Bin Park
|
| Industrial Engineering, Seoul National University | |
| 2. | Seyoung Oh
|
| Industrial engineering, Seoul National University | |
| 3. | Kyungsik Lee
|
| Industrial Engineering, Seoul National University |
Abstract
In this talk, we introduce the Online Food Delivery Platform Routing Problem (ORP), a novel variant of the Vehicle Routing Problem(VRP) with pickup and delivery. The ORP is distinguished by its operational policy requiring routes to first serve all pickup requests before handling deliveries. The problem can be shown to be NP-hard, but it presents significant computational challenges in practice, demanding solutions for large-scale instances with hundreds of orders within strict time constraints. To address this unique challenge, we develop an LP-based local-search algorithm for the ORP. Leveraging the classical result that the subtree packing problem on trees is efficiently solvable, we restrict the solution space of the ORP such that only orders forming a subtree of a certain spanning tree, whose nodes correspond to the given orders, can be routed together. We employ a two-level strategy: the low-level solves a restricted ORP under the given spanning tree, while the high-level iteratively modifies the spanning tree to improve solution quality. Extensive computational experiments on large-scale real-world instances demonstrate that our algorithm consistently produces high-quality solutions within the required time constraints.
Keywords
- Programming, Integer
- Large Scale Optimization
- Column Generation
Status: accepted
Back to the list of papers