Kurly Reassigns Delivery Zones with OR-Tools-Based Combinatorial Optimization… Cuts Delivery Time by 5%

Kurly's Data Service Development Team defined the connection between Cluster Center (CC), Transfer Center (TC), and final delivery zones as a Combinatorial Optimization problem to improve delivery efficiency, and presented a solution. Existing allocation methods based on administrative districts or straight-line distance had limitations, as they did not match actual travel time and caused volume imbalances between TCs.

Optimization Model Structure

The problem was solved using Google OR-Tools's CP-SAT and SCIP solvers. The objective function aims to minimize the total time required to move from CC through TC to each zone, and includes constraints on the maximum volume capacity each TC can handle and the requirement that each zone be assigned to exactly one TC. This is a special form of the Generalized Assignment Problem (GAP), an NP-hard problem whose number of cases exceeds the number of atoms in the universe and is difficult to solve even with a supercomputer, but a practical solution is derived through the solver.

Data Calibration and Real-World Reflection

Data was calibrated to reflect actual delivery difficulty rather than simple distance calculation. For example, even with the same volume, delivery time differs between Gangnam and Namyangju depending on delivery density and road conditions, so delivery difficulty was applied as a weight to adjust volume ($d_j$). In addition, expected delivery time ($t_{ij}$) was calculated by considering each TC's departure time history and volume per round, and field constraints such as delivery driver conditions in specific zones or a limit of 40 minutes or more were added to the model.

Zone Reallocation and Management

To group together zones that were scattered in location in the solved assignment plan, a zone reallocation step was performed to minimize the maximum travel distance between zones within a TC. This is a variant of the Generalized Assignment Problem that simultaneously considers volume capacity and order volume. The final result was made into a tool so that the logistics team can update input data and repeatedly run the optimization, and it will be used to support decision-making such as reviewing candidate sites for new TCs or readjusting zones themselves in the future.