Efficient Heuristic for Solving Extremely Large-Scale Open Vehicle Routing Problems with Stringent Delivery Times

This paper introduces a deterministic heuristic method for solving large-scale open vehicle routing problems (OVRPs) with stringent delivery times. The proposed method is based on the sweep algorithm and aims to obtain approximate solutions for large-scale OVRPs. Initial testing on smaller OVRP instances, with up to 500 customers, demonstrated that the method produces quick approximate solutions, with deviations not exceeding 5% from the best-known solutions (BKS). Further testing on 10 sets of standard benchmark instances, each involving thousands of customers, confirmed that the heuristic provides efficient approximate solutions with minimal CPU time consumption and uses a minimal number of vehicles. This demonstrates the method's effectiveness in handling complex open vehicle routing problems efficiently.