Back to results
US 10,948,926 B2Granted
Systems and methods for scalable multi-vehicle task allocation
AssigneeTata Consultancy Services Limited
InventorsChayan Sarkar, Himadri Sekhar Paul, Arindam Pal, Arijit Mukherjee
Life of this patent
Estimating the term…
Abstract
Systems and methods of the present disclosure address the capacity constrained vehicle routing (CVRP) problem that may be applied to a warehouse scenario wherein multi-robot task allocation is required. Conventional methods can solve CVRP instances up to 100 nodes. In the present disclosure, a nearest-neighbor based Clustering And Routing (nCAR) approach is provided that makes the systems and methods of the present disclosure scalable wherein the number of nodes can be in the range of several hundreds to several thousands within an order wave.
Claims6
A processor implemented method (200) comprising:
- obtaining input parameters comprising:
- a number of nodes representative of tasks to be allocated to one or more vehicles, distances between each of the number of nodes as a metric that satisfies triangle inequality, demands associated with each of the number of nodes representative of a quantity associated with the tasks, and maximum capacities of each of the one or more vehicles representative of a weight carrying capacity of the one or more vehicles, wherein each of the one or more vehicles fetch multiple objects on a single run such that the total weight of the tasks is within the maximum capacity of the each vehicle;
- determining a plurality of clusters of the number of nodes based on a heuristic nearest neighbor node based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle meeting criteria of a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle;
- and the plurality of clusters leads to a lowest total cost, wherein the lowest total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks, wherein the heuristic nCAR approach creates a subset of cluster combination by splitting all the tasks which results in a low cost solution and achieves scalability, wherein the subset comprises a plurality of clusters of disjoint sets of nodes except for a depot node representative of a node where a cluster starts and ends;
- and
- determining an optimum route within each of the plurality of clusters such that the total length travelled by the associated vehicle is minimized, wherein a number of clusters comprising the plurality of nodes determine a number of vehicles required to complete all the tasks, wherein when the number of vehicles is less than a number of routes, then the vehicle from the number of vehicles starts a new route after completing a previously assigned route;
- wherein, based on the determining of the optimum route within each of the plurality of clusters, the vehicle from the number of vehicles completes one optimum route within one of the plurality of clusters.
4 more elements
A system comprising:
- one or more data storage devices operatively coupled to one or more hardware processors and configured to store instructions configured for execution by the one or more hardware processors to:
- obtain input parameters comprising:
- a number of nodes representative of tasks to be allocated to one or more vehicles, distances between each of the number of nodes as a metric that satisfies triangle inequality, demands associated with each of the number of nodes representative of a quantity associated with the tasks, and maximum capacities of each of the one or more vehicles representative of a weight carrying capacity of the one or more vehicles, wherein each of the one or more vehicles fetch multiple objects on a single run such that the total weight of the tasks is within the maximum capacity of the each vehicle;
- determine a plurality of clusters of the number of nodes based on a heuristic nearest neighbor node based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle meeting criteria of a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle;
- and the plurality of clusters leads to a lowest total cost, wherein the lowest total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks, wherein the heuristic nCAR approach creates a subset of cluster combination by splitting all the tasks which results in a low cost solution and achieves scalability, wherein the subset comprises a plurality of clusters of disjoint sets of nodes except for a depot node representative of a node where a cluster starts and ends;
- and
- determine an optimum route within each of the plurality of clusters such that the total length travelled by the associated vehicle is minimized, wherein a number of clusters comprising the plurality of nodes determine a number of vehicles required to complete all the tasks, wherein when the number of vehicles is less than a number of routes, then the vehicle from the number of vehicles starts a new route after completing a previously assigned route;
- wherein, based on the determining of the optimum route within each of the plurality of clusters, the vehicle from the number of vehicles completes one optimum route within one of the plurality of clusters.
5 more elements
A computer program product comprising a non-transitory computer readable medium having a computer readable program embodied therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:
- obtain input parameters comprising:
- a number of nodes representative of tasks to be allocated to one or more vehicles, distances between each of the number of nodes as a metric that satisfies triangle inequality, demands associated with each of the number of nodes representative of a quantity associated with the tasks, and maximum capacities of each of the one or more vehicles representative of a weight carrying capacity of the one or more vehicles, wherein each of the one or more vehicles fetch multiple objects on a single run such that the total weight of the tasks is within the maximum capacity of the each vehicle;
- determine a plurality of clusters of the number of nodes based on a heuristic nearest neighbor node based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle meeting criteria of a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle;
- and the plurality of clusters leads to a lowest total cost, wherein the lowest total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks, wherein the heuristic nCAR approach creates a subset of cluster combination by splitting all the tasks which results in a low cost solution and achieves scalability, wherein the subset comprises a plurality of clusters of disjoint sets of nodes except for a depot node representative of a node where a cluster starts and ends;
- and
- determine an optimum route within each of the plurality of clusters such that the total length travelled by the associated vehicle is minimized, wherein a number of clusters comprising the plurality of nodes determine a number of vehicles required to complete all the tasks, wherein when the number of vehicles is less than a number of routes, then the vehicle from the number of vehicles starts a new route after completing a previously assigned route;
- wherein, based on the determining of the optimum route within each of the plurality of clusters, the vehicle from the number of vehicles completes one optimum route within one of the plurality of clusters.
4 more elements
Dependencies are inferred from the claim text.