US-20260126296-A1 - LARGE-SCALE DISPATCHING UTILIZING LARGE NEIGHBORHOOD SEARCH

Abstract

An example operation may include one or more of receiving a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks, clustering the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location, executing a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks, updating the geographic map based on the plurality of modified subsets of routes, and dispatching the tasks to the plurality of vehicles via a communication channel based on the updated geographic map.

Inventors

• Dung Tien Phan
• Ali Koc
• Francisco Barahona

Assignees

• INTERNATIONAL BUSINESS MACHINES CORPORATION

Dates

Publication Date

20260507

Application Date

20241104

Claims (20)

1. 1 . A computer system for optimizing scheduling and dispatching of tasks, the computer system comprising: a memory; and at least one processor communicatively coupled to the memory, the at least one processor configured to: receive a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks; cluster the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location; execute a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks; update the geographic map based on the plurality of modified subsets of routes; and dispatch the tasks to the plurality of vehicles via a communication channel based on the updated geographic map.
2. 2 . The computer system of claim 1 , wherein the at least one processor is configured to identify geographic centers of the routes based on geographic coordinates of the routes calculated from drive time, and cluster the routes into the plurality of subsets of routes based on the geographic centers of the routes.
3. 3 . The computer system of claim 1 , wherein the at least one processor is configured to remove one or more tasks from a first position of a route and anneal the one or more tasks to a second position of the route to generate a modified route based on execution of the LNS.
4. 4 . The computer system of claim 3 , wherein the at least one processor is configured to determine that the modified route is more efficient than the route based on at least one of a travel time difference and a number of overall tasks difference between the route and the modified route, and in response, generate the updated geographic map to include the modified route.
5. 5 . The computer system of claim 3 , wherein the at least one processor is configured to insert the one or more tasks at the second position of the route based on execution of at least one of a greedy algorithm and a regret algorithm.
6. 6 . The computer system of claim 1 , wherein the at least one processor is configured to simultaneously execute a plurality of instances of the LNS on the plurality of subsets of routes using a plurality of different processing cores, respectively, to generate the plurality of modified subsets of routes.
7. 7 . The computer system of claim 1 , wherein the at least one processor is further configured to retrieve attributes of the tasks from a database, and execute the LNS on the attributes to generate the plurality of modified subsets of routes.
8. 8 . A computer-implemented method for optimizing scheduling and dispatching of tasks, the computer-implemented method comprising: receiving a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks; clustering the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location; executing a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks; updating the geographic map based on the plurality of modified subsets of routes; and dispatching the tasks to the plurality of vehicles via a communication channel based on the updated geographic map.
9. 9 . The computer-implemented method of claim 8 , wherein the clustering comprises identifying geographic centers of the routes based on geographic coordinates of the routes calculated from drive time, and clustering the routes into the plurality of subsets of routes based on the geographic centers of the routes.
10. 10 . The computer-implemented method of claim 8 , wherein the executing comprises removing one or more tasks from a first position of a route and annealing the one or more tasks to a second position of the route to generate a modified route based on execution of the LNS.
11. 11 . The computer-implemented method of claim 10 , further comprising determining that the modified route is more efficient than the route based on at least one of a travel time difference and a number of overall tasks difference between the route and the modified route, and in response, generating the updated geographic map to include the modified route.
12. 12 . The computer-implemented method of claim 10 , wherein the annealing comprises inserting the one or more tasks at the second position of the route based on execution of at least one of a greedy algorithm and a regret algorithm.
13. 13 . The computer-implemented method of claim 8 , wherein the executing comprises simultaneously executing a plurality of instances of the LNS on the plurality of subsets of routes using a plurality of different processing cores, respectively, to generate the plurality of modified subsets of routes.
14. 14 . The computer-implemented method of claim 8 , further comprising retrieving attributes of the tasks from a database, wherein the executing further comprises executing the LNS on the attributes to generate the plurality of modified subsets of routes.
15. 15 . A computer program product for optimizing scheduling and dispatching of tasks, the computer program product comprising a computer-readable storage medium and program instructions stored on the computer-readable storage medium, wherein the program instructions are executable by a computer processor causing the computer processor to perform one or more functions, the program instructions comprising: program instructions to receive a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks; program instructions to cluster the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location; program instructions to execute a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks; program instructions to update the geographic map based on the plurality of modified subsets of routes; and program instructions to dispatch the tasks to the plurality of vehicles via a communication channel based on the updated geographic map.
16. 16 . The computer program product of claim 15 , wherein the clustering comprises identifying geographic centers of the routes based on geographic coordinates of the routes calculated from drive time, and clustering the routes into the plurality of subsets of routes based on the geographic centers of the routes.
17. 17 . The computer program product of claim 15 , wherein the executing comprises removing one or more tasks from a first position of a route and annealing the one or more tasks to a second position of the route to generate a modified route based on execution of the LNS.
18. 18 . The computer program product of claim 17 , wherein the program instructions further comprise program instructions to perform determining that the modified route is more efficient than the route based on at least one of a travel time difference and a number of overall tasks difference between the route and the modified route, and in response, generating the updated geographic map to include the modified route.
19. 19 . The computer program product of claim 17 , wherein the annealing comprises inserting the one or more tasks at the second position of the route based on execution of at least one of a greedy algorithm and a regret algorithm.
20. 20 . The computer program product of claim 15 , wherein the executing comprises simultaneously executing a plurality of instances of the LNS on the plurality of subsets of routes using a plurality of different processing cores, respectively, to generate the plurality of modified subsets of routes.

Description

BACKGROUND Scheduling software, such as workforce management software, can schedule tasks. For example, the software may determine an optimal set of routes for a group of vehicles and associated crews to serve a given set of customers, each with specific demands, while minimizing the total cost. The software often considers various constraints such as different time windows, multiple depots with heterogeneous vehicles, multiple commodities, synchronized shifts, crew availability, and the like. Current scheduling software can take a long time to properly provide a set of routes for the group of vehicles/crews when the problem involves a large number of tasks. SUMMARY One example embodiment provides a computer system for optimizing scheduling and dispatching of tasks, the computer system includes a memory, and at least one processor communicatively coupled to the memory, and the at least one processor configured to at least one of receive a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks, cluster the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location, execute a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks, update the geographic map based on the plurality of modified subsets of routes, and dispatch the tasks to the plurality of vehicles via a communication channel based on the updated geographic map. Another example embodiment provides a computer-implemented method for optimizing scheduling and dispatching of tasks, the computer-implemented method including at least one of receiving a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks, clustering the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location, executing a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks, updating the geographic map based on the plurality of modified subsets of routes, and dispatching the tasks to the plurality of vehicles via a communication channel based on the updated geographic map. A further example embodiment provides a computer program product for optimizing scheduling and dispatching of tasks, the computer program product includes a computer-readable storage medium and program instructions stored on the computer-readable storage medium, wherein the program instructions are executable by a computer processor causing the computer processor to perform one or more functions, the program instructions include at least one of program instructions to receive a geographic map that comprises tasks assigned to a plurality of vehicles, and routes for the plurality of vehicles to follow to perform the tasks, program instructions to cluster the routes into a plurality of subsets of routes based on travel times from geographic locations of the routes in the geographic map, wherein each subset of routes corresponds to a different geographic location, program instructions to execute a large neighborhood search (LNS) on the plurality of subsets of routes to generate a plurality of modified subsets of routes for the plurality of vehicles to follow to perform the tasks, program instructions to update the geographic map based on the plurality of modified subsets of routes, and program instructions to dispatch the tasks to the plurality of vehicles via a communication channel based on the updated geographic map. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a diagram illustrating a computing environment according to an embodiment of the instant solution. FIG. 2A is a diagram illustrating a process of generating modified dispatch instructions for a set of tasks according to the examples and features of the instant solution. FIG. 2B is a diagram illustrating a process of generating modified dispatch instructions using parallel processing according to the examples and features of the instant solution. FIG. 2C is a diagram illustrating a process of dispatching the tasks to a group of vehicles (crews) based on the modified dispatch instructions according to the examples and features of the instant solution. FIG. 3A is a diagram illustrating a geographic map showing a plurality of routes for a plurality of vehicles according to the examples and features of the instant solution. FIG. 3B is a diagram illustrating a process of decomposing a group of tasks by clustering routes together among the pl