Route generation for vehicle routing problem and variants thereof
According to an aspect of an embodiment, operations include receiving data associated with a vehicle routing problem, the data comprising first information about a plurality of vehicles in a geographical region and second information about a set of locations that the plurality of vehicles is required to serve. The operations further include determining a formulation of a multi-objective clustering problem based on the data and converting the formulation into a QUBO formulation. The operations further include generating a binary solution by solving the QUBO formulation on an optimization solver machine. The operations further include partitioning the set of locations into location clusters based on the binary solution and generating a set of candidate routes for the plurality of vehicles based on the location clusters. The operations further include controlling a device to render at least one route recommendation for the plurality of vehicles based on the set of candidate routes.
1. A method, executed by a processor, comprising:
receiving data associated with a vehicle routing problem, the data comprising first information about a plurality of vehicles in a geographical region and second information about a set of locations that the plurality of vehicles is required to serve;
determining a formulation of a multi-objective clustering problem based on the data;
converting the formulation into a Quadratic Unconstrained Binary Optimization (QUBO) formulation;
generating a binary solution by solving the QUBO formulation on an optimization solver machine;
partitioning the set of locations into a set of location clusters based on the binary solution;
generating a set of candidate routes for the plurality of vehicles based on the set of location clusters; and
controlling a user device to render at least one route recommendation for the plurality of vehicles based on the set of candidate routes.
2. The method according to claim 1 , wherein the data further comprises a first constraint associated with the plurality of vehicles and a second constraint associated with the set of locations.
3. The method according to claim 2 , wherein the first constraint is a capacity constraint, and the second constraint is a demand constraint.
4. The method according to claim 1 , wherein the multi-objective clustering problem comprises a plurality of objective functions and a set of constraints that is applicable on the plurality of objective functions, and
the plurality of objective functions is to be minimized to obtain an optimal partitioning of the set of locations into the set of location clusters.
5. The method according to claim 4 , wherein the plurality of objective functions comprises:
a distance-based objective function to minimize an intra-cluster pairwise distance between each pair of locations of the set of locations, and
an angle-based objective function to minimize an intra-cluster pairwise angle between each pair of locations of the set of locations.
6. The method according to claim 4 , wherein the set of constraints comprises:
a third constraint that requires that each location of the set of locations is uniquely assigned to a location cluster of the set of location clusters, and
a fourth constraint that requires that a difference in total demands between a pair of location clusters of the set of location clusters is below a demand threshold.
7. The method according to claim 1 , further comprising initializing values of weight parameters associated with the QUBO formulation, wherein the QUBO formulation is solved based on the values.
8. The method according to claim 7 , wherein the weight parameters correspond to weight coefficients associated with respective quadratic objective functions in the QUBO formulation.
9. The method according to claim 1 , further comprising:
determining an objective function of a route generation problem for each location cluster of the set of location clusters; and
solving the route generation problem based on a minimization of the objective function for each location cluster of the set of location clusters to generate a candidate route of the set of candidate routes for a corresponding location cluster of the set of location clusters.
10. The method according to claim 9 , wherein the route generation problem is a set partitioning problem.
11. The method according to claim 1 , wherein the binary solution of the QUBO is Pareto-optimal solution.
12. The method according to claim 1 , wherein the binary solution includes a set of binary values, each of which indicates whether a location of the set of locations belongs to a location cluster of the set of location clusters.
13. One or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed, cause a system to perform operations, the operations comprising:
receiving data associated with a vehicle routing problem, the data comprising first information about a plurality of vehicles in a geographical region and second information about a set of locations that the plurality of vehicles is required to serve;
determining a formulation of a multi-objective clustering problem based on the data;
converting the formulation into a Quadratic Unconstrained Binary Optimization (QUBO) formulation;
generating a binary solution by solving the QUBO formulation on an optimization solver machine;
partitioning the set of locations into a set of location clusters based on the binary solution;
generating a set of candidate routes for the plurality of vehicles based on the set of location clusters; and
controlling a user device to render at least one route recommendation for the plurality of vehicles based on the set of candidate routes.
14. The one or more non-transitory computer-readable storage media according to claim 13 , wherein the data further comprises a first constraint associated with the plurality of vehicles and a second constraint associated with the set of locations.
15. The one or more non-transitory computer-readable storage media according to claim 14 , wherein the first constraint is a capacity constraint, and the second constraint is a demand constraint.
16. The one or more non-transitory computer-readable storage media according to claim 13 , wherein the multi-objective clustering problem comprises a plurality of objective functions and a set of constraints that is applicable on the plurality of objective functions, and
the plurality of objective functions is to be minimized to obtain an optimal partitioning of the set of locations into the set of location clusters.
17. The one or more non-transitory computer-readable storage media according to claim 16 , wherein the plurality of objective functions comprises:
a distance-based objective function to minimize an intra-cluster pairwise distance between each pair of locations of the set of locations, and
an angle-based objective function to minimize an intra-cluster pairwise angle between each pair of locations of the set of locations.
18. The one or more non-transitory computer-readable storage media according to claim 16 , wherein the set of constraints comprises:
a third constraint that requires that each location of the set of locations is uniquely assigned to a location cluster of the set of location clusters, and
a fourth constraint that requires that a difference in total demands between a pair of location clusters of the set of location clusters is below a demand threshold.
19. The one or more non-transitory computer-readable storage media according to claim 13 , wherein the binary solution includes a set of binary values, each of which indicates whether a location of the set of locations belongs to a location cluster of the set of location clusters.
20. A system, comprising:
a memory storing instructions; and
a processor, coupled to the memory, that executes the instructions to perform a process comprising:
receiving data associated with a vehicle routing problem, the data comprising first information about a plurality of vehicles in a geographical region and second information about a set of locations that the plurality of vehicles is required to serve;
determining a formulation of a multi-objective clustering problem based on the data;
converting the formulation into a Quadratic Unconstrained Binary Optimization (QUBO) formulation;
generating a binary solution by solving the QUBO formulation on an optimization solver machine;
partitioning the set of locations into a set of location clusters based on the binary solution;
generating a set of candidate routes for the plurality of vehicles based on the set of location clusters; and
controlling a user device to render at least one route recommendation for the plurality of vehicles based on the set of candidate routes.