DETAILED ACTION
This communication is a Final Office Action rejection on the merits. Claims 1-20 are currently pending and have been addressed below.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Applicant's arguments filed on 01/21/2026 (related to the 103 Rejection) have been fully considered but are moot in view of new grounds of rejection. Applicant's amendments necessitated the new ground(s) of rejection presented in this Office action. Rejection based on a newly cited reference(s) follows.
Applicant's arguments filed on 01/21/2026 (related to the 101 Rejection) have been fully considered but they are not persuasive.
Applicant states, on pages 1-2, that the Office's stated mathematical concept is automated and employed to route a tangible autonomous vehicle through the nodes of the generated optimal route that addresses the routing problem. This avoids the need for a user to evaluate the nodes, generate and assign an optimal route, and route the vehicle through the nodes of an optimal route. Thus, the claims go beyond merely automating the abstract idea and employs the information obtained via the judicial exception to take corrective action by generating an optimal route and routing the autonomous vehicle through the nodes of the optimal route. Therefore, meaningful limitation is added because the information provided by the Office's stated judicial exception is used to route the autonomous vehicle through the nodes of the optimal routing resulting in improved vehicle routing. As such, the amendments add "other meaningful limitation" that integrates the Office's stated judicial exception into a practical application. and practically applies the exception, such that the claims are not directed to judicial exceptions.
Examiner respectfully disagrees with Applicant. Although claim 1 discloses an automated step of autonomously controlling a vehicle, Examiner notes that is not clear what is triggering the automated event (e.g. by obtaining a location of the vehicle from a sensor and computing the optimal route in real-time). Rather, the claim seems to extract the location information from a database. Also, the claim and specification do not provide any specific details of how the autonomous vehicle is controlled (see Applicant’s specification, Paragraph 0094). Therefore, the claim merely recites the idea of a solution or outcome (see MPEP 2106.05(f)). The claim is ineligible.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., an abstract idea) without reciting significantly more.
Independent Claim 1
Step One - First, pursuant to step 1 in the January 2019 Revised Patent Subject Matter Eligibility Guidance (“2019 PEG”) on 84 Fed. Reg. 53, the claim 1 is directed to a method which is a statutory category.
Step 2A, Prong One - Claim 1 recites: A method comprising: clustering nodes that represent locations such that each node is assigned to only one node cluster; determining potential solutions from the node clusters using a genetic algorithm; evolving the potential solutions by performing a simulated annealing process to output evolved solutions, each evolved solution comprising evolved node clusters, and each node being assigned to an evolved node cluster; invoking a quantum annealer to separately anneal each evolved node cluster of an evolved solution selected from the simulated annealing process to generate an optimal route through the nodes for each evolved node cluster of the selected evolved solution; and routing an vehicle by sending a signal that communicates the optimal route as routing instructions to the vehicle. These claim elements are considered to be abstract ideas because they are directed to “mathematical concepts” which include “mathematical calculations.” In this case, using a combination of multiple algorithms to generate an optimal route is considered a mathematical calculation (MPEP 2106.04(a)(2)). If a claim limitation, under its broadest reasonable interpretation, covers mathematical calculations, then it falls within the “mathematical concepts” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Step 2A Prong 2 - The judicial exception is not integrated into a practical application. Claim 1 includes additional elements: a computer; a genetic algorithm; a simulated annealing process; a quantum annealer; and an autonomous vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions.
The computer is merely used to execute instructions (Paragraph 0112). The genetic algorithm is merely used to determine potential solutions from the node clusters (Paragraph 0007). The simulated annealing process is merely used to evolve potential solutions. The evolved node clusters each include nodes, and each node is assigned to one evolved node cluster. The nodes of the evolved node clusters are also connected via a route. In this way, the system seeks to improve the routes determined through the nodes (Paragraph 0008). The quantum annealer is merely used to anneal one of the evolved solutions, which can be selected based on a minimum total route distance between the corresponding evolved node clusters. Using the quantum annealer, an optimal route through each of the nodes of the evolved node clusters is determined. For instance, the optimal route may include an order of nodes in each evolved node cluster that minimizes the overall distance or other variable of the route between the nodes. Each cluster can be assigned to a vehicle that traverses the routes (Paragraph 0009). The autonomous vehicle is merely used to receive information to navigate through the nodes of the respective optimal route (Paragraph 0094). Merely stating that the step is performed by a computer component results in “apply it” on a computer (MPEP 2106.05f). These elements of “computer,” “genetic algorithm,” “simulated annealing process,” “quantum annealer,” and “autonomous vehicle” are recited at a high level of generality such that it amounts no more than mere instructions to apply the exception using a generic computer element. Accordingly, alone and in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea. Therefore, the claim is directed to an abstract idea.
Step 2B - The claim does not include additional elements that are sufficient to amount significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the claims describe how to generally “apply” the concept of using a combination of multiple algorithms to generate an optimal route. The specification shows that the computer is merely used to execute instructions (Paragraph 0112). The genetic algorithm is merely used to determine potential solutions from the node clusters (Paragraph 0007). The simulated annealing process is merely used to evolve potential solutions. The evolved node clusters each include nodes, and each node is assigned to one evolved node cluster. The nodes of the evolved node clusters are also connected via a route. In this way, the system seeks to improve the routes determined through the nodes (Paragraph 0008). The quantum annealer is merely used to anneal one of the evolved solutions, which can be selected based on a minimum total route distance between the corresponding evolved node clusters. Using the quantum annealer, an optimal route through each of the nodes of the evolved node clusters is determined. For instance, the optimal route may include an order of nodes in each evolved node cluster that minimizes the overall distance or other variable of the route between the nodes. Each cluster can be assigned to a vehicle that traverses the routes (Paragraph 0009). The autonomous vehicle is merely used to receive information to navigate through the nodes of the respective optimal route (Paragraph 0094). Also, although the claim is using a simulated annealing to evolve potential solutions, the claim does not recite any specific details of how the potential solutions evolve over time (MPEP 2106.05(f)), claim fails to recites details of how a solution of a problem is accomplished). Also, the claim and specification do not provide any specific details of how the autonomous vehicle is controlled or what is triggering the autonomous vehicle to start navigating through the optimal route (MPEP 2106.05(f)). Thus, nothing in the claim adds significantly more to the abstract idea. The claim is ineligible.
Independent claim 7 is directed to a system at step 1, which is a statutory category. Claim 7 recites similar limitations as claim 1 and is rejected for the same reasons at step 2a, prong one; step 2a, prong 2; and step 2b. Claim 7 further recites “processor” and “computer storage media” – which are treated as just an explicit “processor/computer” for executing the operations and are treated under MPEP 2106.05f in the same manner as claim 1. Accordingly, these limitations are viewed as “apply it on a computer” at step 2a, prong 2 and step 2b. Thus, the claim is ineligible.
Independent claim 14 is directed to an article of manufacture at step 1, which is a statutory category. Claim 14 recites similar limitations as claim 1 and claim 13 and is rejected for the same reasons at step 2a, prong one; step 2a, prong 2; and step 2b. Claim 14 further recites “processor” and “computer storage media” – which are treated as just an explicit “processor/computer” for executing the operations and are treated under MPEP 2106.05f in the same manner as claim 1. Accordingly, these limitations are viewed as “apply it on a computer” at step 2a, prong 2 and step 2b. Thus, the claim is ineligible.
Dependent claims 2, 8, and 15 are not directed to any additional claim elements. Rather, these claims offer further descriptive limitations of elements found in the independent claims and addressed above - such as to: determine a number of node clusters from a total number of nodes and a constraint density threshold of the quantum annealer. Quantum annealer has a constraint density threshold, which is the maximum constraint density for a given problem that quantum annealer can solve, as determined, at least in primary part, by the number of qubits and their interactions of the quantum annealer (Paragraph 0052). These processes are similar to the abstract idea noted in the independent claim because they further the limitations of the independent claim which are directed to “mathematical concepts” which include “mathematical calculations.” In this case, calculating the number of node clusters based on a limit/threshold is still considered a mathematical calculation. In addition, no additional elements are integrated into the abstract idea. Therefore, the claims still recite an abstract idea that can be grouped into mathematical concepts.
Dependent claims 3-5, 9-11, and 16-18 are not directed to any additional claim elements. Rather, these claims offer further descriptive limitations of elements found in the independent claims and addressed above - such as to: combine at least a portion of the evolved node clusters for which optimal routes have been generated by the quantum annealer such that the combining of the evolved node clusters reduces a number of evolved node clusters of the selected evolved solution to match a number of vehicles available to traverse the optimal routes; determine cluster centroids for the evolved node clusters for which optimal routes have been generated, wherein combining the evolved node clusters is based on a distance between the cluster centroids; and determine an evolved solution having a minimum total route distance through nodes of the evolved node clusters. These processes are similar to the abstract idea noted in the independent claim because they further the limitations of the independent claim which are directed to “mathematical concepts” which include “mathematical calculations.” In this case, the new limitations are still considered mathematical calculations since they are merely used to generate additional node clusters based on other constraints (e.g., number of available vehicles and distance between the cluster centroids). In addition, no additional elements are integrated into the abstract idea. Therefore, the claims still recite an abstract idea that can be grouped into mathematical concepts.
Dependent claims 6, 12, and 19 are not directed to any additional claim elements. Rather, these claims offer further descriptive limitations of elements found in the independent claims and addressed above - such as wherein: the potential solutions are determined by the genetic algorithm over a first timeframe; the potential solutions are evolved by the simulated annealing process over a second timeframe; the evolved node clusters of the selected evolved solution are annealed by the quantum annealer over a third timeframe; and a number of iterations during which the genetic algorithm and the simulated annealing process are employed is determined from an average of the first timeframe and the second timeframe, the third timeframe, and a total time threshold. These processes are similar to the abstract idea noted in the independent claim because they further the limitations of the independent claim which are directed to “mathematical concepts” which include “mathematical calculations.” In this case, calculating an average of multiple timeframes is still considered a mathematical calculation. In addition, no additional elements are integrated into the abstract idea. Therefore, the claims still recite an abstract idea that can be grouped into mathematical concepts.
Dependent claims 13 and 20 are not directed to any additional claim elements. Rather, these claims offer further descriptive limitations of elements found in the independent claims and addressed above - such as: wherein the node clusters from which the potential solutions are defined using the genetic algorithm comprise prior evolved node clusters determined by the simulated annealing during a prior iteration. These processes are similar to the abstract idea noted in the independent claim because they further the limitations of the independent claim which are directed to “mathematical concepts” which include “mathematical calculations.” In this case, using previous calculated node clusters as potential solutions is still considered a mathematical calculation. In addition, no additional elements are integrated into the abstract idea. Therefore, the claims still recite an abstract idea that can be grouped into mathematical concepts.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1, 5, 7, 11, 14, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Ushijima-Mwesigwa et al. (US 2024/0183670 A1), in view of Wu (CN 116341783 A), in further view of Choi (US 2022/0357167 A1).
Regarding claim 1 (Currently Amended), Ushijima-Mwesigwa et al. discloses a method comprising (Paragraph 0014, Some embodiments described in the present disclosure relate to methods and systems for generation of routes for a Vehicle Routing Problem (VRP) and variants thereof. Herein, the vehicle routing problem may be a combinatorial optimization problem whose goal may be to determine a set of optimal routes between a central depot and a set of locations):
clustering nodes that represent locations such that each node is assigned to only one node cluster (Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters);
determining potential solutions from the node clusters using a [solver machine] (Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0090, The set of locations may be represented as nodes of an unconnected graph);
evolving the potential solutions by performing a simulated annealing process to output evolved solutions, each evolved solution comprising evolved node clusters, and each node being assigned to an evolved node cluster (Paragraph 0014, Some embodiments described in the present disclosure relate to methods and systems for generation of routes for a Vehicle Routing Problem (VRP) and variants thereof. Herein, the vehicle routing problem may be a combinatorial optimization problem whose goal may be to determine a set of optimal routes between a central depot and a set of locations; Paragraph 0015, VRP may have variants such as a Traveling Salesman Problem (TSP), a Capacitated Vehicle Routing Problem (CVRP), a Vehicle Routing Problem with Time-Windows (VRPTW), or a Pickup and Delivery Problem with Time-Windows (PDPTW). Each VRP variant may be bounded by a set of constraints. The set of constraints may vary amongst VRP variants based on application specific requirements associated with each VRP variant. The constraints may include, for example, a vehicle's capacity, a customer demand, a time window within which the delivery needs to be completed, and so on. Based on the constraints defining a VRP, hardware and/or software-based optimization solvers (for example, heuristics, meta-heuristics, exact algorithms, approximate algorithms, and so on) may be used for determination of a set of optimal routes as a solution of VRP; Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0026, In some embodiments, the optimization solver machine 106 may be a quantum annealing computer that may be specifically designed and hardware/software optimized to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing. Like the generalized quantum computing device, the quantum annealing computer may also use qubits and may require a carefully controlled cryogenic environment to function properly; As stated in Paragraph 0032 of Applicant’s specification, the evolved solution comprises breaking the CRVP problem into subproblems. Therefore, based on broadest reasonable interpretation in light of the specification, Ushijima-Mwesigwa et al. discloses “evolved node cluster” since it breaks the problem into subproblems by clustering/partitioning a set of locations);
invoking a quantum annealer to separately anneal each evolved node cluster of an evolved solution selected from the simulated annealing process to generate an optimal route through the nodes for each evolved node cluster of the selected evolved solution (Paragraph 0018, The optimization solver machine (for example, a quantum inspired hardware) may be used for minimization of the weighted summation based on a set of predefined constraints. The minimization may lead to the generation of a binary solution that may be used for the partitioning of the set of locations into the set of location clusters. The binary solutions may be generalized for all variants of VRP; Paragraph 0024, In one or more embodiments of the disclosure, the optimization solver machine 106 may be implemented as a generalized quantum computing device that may be hosted on a cloud optimization system. The cloud optimization system may be implemented as one of a private cloud, a public cloud, or a hybrid cloud. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a QUBO solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing to search for the solution of the QUBO formulation from a discrete solution space; Paragraph 0025, The generalized quantum computing device may be different from a digital bit-based computing device, such as digital devices that are based on transistor-based digital circuits. The generalized quantum computing device may include one or more quantum gates that use quantum bits (hereinafter referred to as “qubits”) to perform computations for different information processing applications, such as quantum annealing computations for solving the QUBO formulation. In general, a qubit can represent “0”, “1”, or a superposition of both “0” and “1”; Examiner interprets “solving a solution for each cluster using one or more qubits” as to “separately anneal each evolved node cluster of an evolved solution” since it’s known by an ordinary skill in the art that a quantum computing device uses each qubit to solve a subproblem (e.g., cluster));
and … sending a signal that communicates the optimal route as routing instructions to the [user device] and causes the [user using a vehicle] to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (Paragraph 0023, The user device 104 may include suitable logic, circuitry, and interfaces that may be configured to render on a display device a set of optimal routes or route recommendations for the plurality of vehicles. The set of optimal routes or the route recommendations may be rendered on an electronic user interface of the user device 104. The routes may be traversed by the plurality of vehicles for the delivery of goods or items; Paragraph 0043, Based on a solution of the set partition problem, the system 102 may control the user device 104 to render at least one optimal route of the set of optimal routes as a recommendation for each vehicle of the plurality of vehicles. For example, if the candidate route 124A is determined as an optimal route based on a solution of the set partition problem, then the system 102 may control the user device 104 to recommend the candidate route 124A for the transport vehicle 118A; Paragraph 0103, At 514, the user device 104 may be controlled to render at least one route recommendation for the plurality of vehicles 118A and 118B based on the set of candidate routes 124A and 124B. In an embodiment, the processor 204 may be configured to control the user device 104 to render at least one route recommendation for the plurality of vehicles 118A and 118B based on the set of candidate routes 124A and 124B. The set of candidate routes 124A and 124B may be rendered on a display of the user device 104 (or the display device 210A) as recommendations, based on a determination of the set of candidate routes 124A and 124B as optimal routes. The user 112 may view the optimal routes that may be used for transportation of items to the set of locations 120A . . . 120H).
Although Ushijima-Mwesigwa et al. discloses determining potential solutions from the node clusters using a solver machine, Ushijima-Mwesigwa et al. does not specifically disclose wherein the potential solutions from the node clusters are determined using a genetic algorithm.
However, Wu discloses determining potential solutions from the node clusters using a genetic algorithm (Page 2, Background, Paragraph 0002, At present, mainly using heurism algorithm to solve CVRP, comprising ant colony algorithm (Ant Colony Optimization, ACO), genetic algorithm (Genetic Algorithm, GA), Simulated Annealing Algorithm (SAA) and so on. However, the algorithm has respective disadvantages, ACO is easy to fall into local optimum GA convergence speed is slow, SAA is influenced by the parameter setting, therefore, the single heurism algorithm can not quickly and accurately solve CVRP, need to mix the algorithm; Page 2, Background, Paragraph 0003, K-means clustering algorithm is a clustering analysis algorithm of iterative solving, the step is randomly selecting K objects as initial clustering centre, then calculating the distance between each object and each clustering centre, distributing each object to the nearest clustering centre. K-means clustering algorithm convergence speed is fast, can improve the whole solving speed of the algorithm mixed with it, so the invention selects the K-means clustering algorithm to mix with the ACO. However, the K-means clustering algorithm is the clustering number K value of the selection is not easy to grasp, so for solving the heterogeneous vehicle problem CVRP, it needs to improve the one point and then mixed with the ACO to form a better performance of the hybrid algorithm; Examiner notes that Wu uses a K-means clustering algorithm with another heuristic algorithm (e.g., genetic algorithm) to determine potential solutions).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining potential solutions of an optimization routing problem, wherein the potential solutions are determined using a solver machine of the invention of Ushijima-Mwesigwa et al. to further specify wherein the algorithm used to generate the potential solutions is a genetic algorithm of the invention of Wu because doing so would allow the method to mix a k-means clustering algorithm with a genetic algorithm to quickly and accurately solve a CVRP optimization problem (see Wu, Page 2, Background, Paragraph 0003). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Ushijima-Mwesigwa et al. discloses routing instructions to a user device by sending a signal that communicates the optimal route, wherein the user views the optimal route to navigate through the nodes of the optimal route (see at least Paragraphs 0023 & 0103). Although Ushijima-Mwesigwa et al. wherein a vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (e.g., a vehicle controlled by a user), the combination of Ushijima-Mwesigwa et al. and Wu does not specifically disclose wherein the vehicle is an autonomous vehicle.
However, Choi discloses routing an autonomous vehicle by sending a signal that communicates the optimal route as routing instructions to the autonomous vehicle and causes the autonomous vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (Paragraph 0029, The cloud-based platform can further select one of the multiple routes as optimal, generate navigation instructions for that one route, and communicate the navigation instructions to the autonomous vehicle for performance, wherein the autonomous vehicle executes the instructions and is caused to traverse the one optimal route—without human oversight and/or intervention, and without any need or requirement to capture and process sensor data in real-time).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for generating an optimal route, wherein the optimal route is transmitted to a user to navigate through the nodes of the optimal route of the invention of Ushijima-Mwesigwa et al. and Wu to further specify wherein the optimal route is transmitted to an autonomous vehicle of the invention of Choi because doing so would allow the method to generate navigation instructions for the optimal route and communicate the navigation instructions to the autonomous vehicle for performance (see Choi, Paragraph 0029). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 7 (Currently Amended), Ushijima-Mwesigwa et al. discloses a system comprising: a quantum annealer (Paragraph 0024, In one or more embodiments of the disclosure, the optimization solver machine 106 may be implemented as a generalized quantum computing device that may be hosted on a cloud optimization system. The cloud optimization system may be implemented as one of a private cloud, a public cloud, or a hybrid cloud. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a QUBO solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing to search for the solution of the QUBO formulation from a discrete solution space); at least one processor; and one or more computer storage media storing computer-readable instructions thereon that when executed by the at least one processor cause the at least one processor to perform operations comprising (Paragraph 0047, The processor 204 may include suitable logic, circuitry, and interfaces that may be configured to execute a set of instructions stored in the memory 206. The processor 204 may be configured to execute program instructions associated with different operations to be executed by the system 102 or the electronic device 202; Paragraph 0050, Exemplary implementations of the memory 206 may include, but may not be limited to, Random Access Memory (RAM), Read Only Memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Hard Disk Drive (HDD), a Solid-State Drive (SSD), a CPU cache, and/or a Secure Digital (SD) card):
determining potential solutions from node clusters having nodes that represent locations using a [solver machine] (Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0090, The set of locations may be represented as nodes of an unconnected graph);
evolving the potential solutions by performing a simulated annealing process to output evolved solutions, each evolved solution comprising evolved node clusters, and each node being assigned to an evolved node cluster (Paragraph 0014, Some embodiments described in the present disclosure relate to methods and systems for generation of routes for a Vehicle Routing Problem (VRP) and variants thereof. Herein, the vehicle routing problem may be a combinatorial optimization problem whose goal may be to determine a set of optimal routes between a central depot and a set of locations; Paragraph 0015, VRP may have variants such as a Traveling Salesman Problem (TSP), a Capacitated Vehicle Routing Problem (CVRP), a Vehicle Routing Problem with Time-Windows (VRPTW), or a Pickup and Delivery Problem with Time-Windows (PDPTW). Each VRP variant may be bounded by a set of constraints. The set of constraints may vary amongst VRP variants based on application specific requirements associated with each VRP variant. The constraints may include, for example, a vehicle's capacity, a customer demand, a time window within which the delivery needs to be completed, and so on. Based on the constraints defining a VRP, hardware and/or software-based optimization solvers (for example, heuristics, meta-heuristics, exact algorithms, approximate algorithms, and so on) may be used for determination of a set of optimal routes as a solution of VRP; Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0026, In some embodiments, the optimization solver machine 106 may be a quantum annealing computer that may be specifically designed and hardware/software optimized to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing. Like the generalized quantum computing device, the quantum annealing computer may also use qubits and may require a carefully controlled cryogenic environment to function properly; As stated in Paragraph 0032 of Applicant’s specification, the evolved solution comprises breaking the CRVP problem into subproblems. Therefore, based on broadest reasonable interpretation in light of the specification, Ushijima-Mwesigwa et al. discloses “evolved node cluster” since it breaks the problem into subproblems by clustering/partitioning a set of locations);
invoking the quantum annealer to separately anneal each evolved node cluster of an evolved solution selected from the simulated annealing process to generate an optimal route through the nodes for each evolved node cluster of the selected evolved solution (Paragraph 0018, The optimization solver machine (for example, a quantum inspired hardware) may be used for minimization of the weighted summation based on a set of predefined constraints. The minimization may lead to the generation of a binary solution that may be used for the partitioning of the set of locations into the set of location clusters. The binary solutions may be generalized for all variants of VRP; Paragraph 0024, In one or more embodiments of the disclosure, the optimization solver machine 106 may be implemented as a generalized quantum computing device that may be hosted on a cloud optimization system. The cloud optimization system may be implemented as one of a private cloud, a public cloud, or a hybrid cloud. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a QUBO solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing to search for the solution of the QUBO formulation from a discrete solution space; Paragraph 0025, The generalized quantum computing device may be different from a digital bit-based computing device, such as digital devices that are based on transistor-based digital circuits. The generalized quantum computing device may include one or more quantum gates that use quantum bits (hereinafter referred to as “qubits”) to perform computations for different information processing applications, such as quantum annealing computations for solving the QUBO formulation. In general, a qubit can represent “0”, “1”, or a superposition of both “0” and “1”; Examiner interprets “solving a solution for each cluster using one or more qubits” as to “separately anneal each evolved node cluster of an evolved solution” since it’s known by an ordinary skill in the art that a quantum computing device uses each qubit to solve a subproblem (e.g., cluster));
and … sending a signal that communicates the optimal route as routing instructions to the [user device] and causes the [user using a vehicle] to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (Paragraph 0023, The user device 104 may include suitable logic, circuitry, and interfaces that may be configured to render on a display device a set of optimal routes or route recommendations for the plurality of vehicles. The set of optimal routes or the route recommendations may be rendered on an electronic user interface of the user device 104. The routes may be traversed by the plurality of vehicles for the delivery of goods or items; Paragraph 0043, Based on a solution of the set partition problem, the system 102 may control the user device 104 to render at least one optimal route of the set of optimal routes as a recommendation for each vehicle of the plurality of vehicles. For example, if the candidate route 124A is determined as an optimal route based on a solution of the set partition problem, then the system 102 may control the user device 104 to recommend the candidate route 124A for the transport vehicle 118A; Paragraph 0103, At 514, the user device 104 may be controlled to render at least one route recommendation for the plurality of vehicles 118A and 118B based on the set of candidate routes 124A and 124B. In an embodiment, the processor 204 may be configured to control the user device 104 to render at least one route recommendation for the plurality of vehicles 118A and 118B based on the set of candidate routes 124A and 124B. The set of candidate routes 124A and 124B may be rendered on a display of the user device 104 (or the display device 210A) as recommendations, based on a determination of the set of candidate routes 124A and 124B as optimal routes. The user 112 may view the optimal routes that may be used for transportation of items to the set of locations 120A . . . 120H).
Although Ushijima-Mwesigwa et al. discloses determining potential solutions from the node clusters using a solver machine, Ushijima-Mwesigwa et al. does not specifically disclose wherein the potential solutions from the node clusters are determined using a genetic algorithm.
However, Wu discloses determining potential solutions from node clusters having nodes that represent locations using a genetic algorithm (Page 2, Background, Paragraph 0002, At present, mainly using heurism algorithm to solve CVRP, comprising ant colony algorithm (Ant Colony Optimization, ACO), genetic algorithm (Genetic Algorithm, GA), Simulated Annealing Algorithm (SAA) and so on. However, the algorithm has respective disadvantages, ACO is easy to fall into local optimum GA convergence speed is slow, SAA is influenced by the parameter setting, therefore, the single heurism algorithm can not quickly and accurately solve CVRP, need to mix the algorithm; Page 2, Background, Paragraph 0003, K-means clustering algorithm is a clustering analysis algorithm of iterative solving, the step is randomly selecting K objects as initial clustering centre, then calculating the distance between each object and each clustering centre, distributing each object to the nearest clustering centre. K-means clustering algorithm convergence speed is fast, can improve the whole solving speed of the algorithm mixed with it, so the invention selects the K-means clustering algorithm to mix with the ACO. However, the K-means clustering algorithm is the clustering number K value of the selection is not easy to grasp, so for solving the heterogeneous vehicle problem CVRP, it needs to improve the one point and then mixed with the ACO to form a better performance of the hybrid algorithm).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining potential solutions of an optimization routing problem, wherein the potential solutions are determined using a solver machine of the invention of Ushijima-Mwesigwa et al. to further specify wherein the algorithm used to generate the potential solutions is a genetic algorithm of the invention of Wu because doing so would allow the method to mix a k-means clustering algorithm with a genetic algorithm to quickly and accurately solve a CVRP optimization problem (see Wu, Page 2, Background, Paragraph 0003). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Ushijima-Mwesigwa et al. discloses routing instructions to a user device by sending a signal that communicates the optimal route, wherein the user views the optimal route to navigate through the nodes of the optimal route (see at least Paragraphs 0023 & 0103). Although Ushijima-Mwesigwa et al. wherein a vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (e.g., a vehicle controlled by a user), the combination of Ushijima-Mwesigwa et al. and Wu does not specifically disclose wherein the vehicle is an autonomous vehicle.
However, Choi discloses routing an autonomous vehicle by sending a signal that communicates the optimal route as routing instructions to the autonomous vehicle and causes the autonomous vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (Paragraph 0029, The cloud-based platform can further select one of the multiple routes as optimal, generate navigation instructions for that one route, and communicate the navigation instructions to the autonomous vehicle for performance, wherein the autonomous vehicle executes the instructions and is caused to traverse the one optimal route—without human oversight and/or intervention, and without any need or requirement to capture and process sensor data in real-time).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for generating an optimal route, wherein the optimal route is transmitted to a user to navigate through the nodes of the optimal route of the invention of Ushijima-Mwesigwa et al. and Wu to further specify wherein the optimal route is transmitted to an autonomous vehicle of the invention of Choi because doing so would allow the method to generate navigation instructions for the optimal route and communicate the navigation instructions to the autonomous vehicle for performance (see Choi, Paragraph 0029). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 14 (Currently Amended), Ushijima-Mwesigwa et al. discloses one or more computer storage media storing computer-readable instructions thereon that when executed by a processor cause the processor to perform operations comprising (Paragraph 0047, The processor 204 may include suitable logic, circuitry, and interfaces that may be configured to execute a set of instructions stored in the memory 206. The processor 204 may be configured to execute program instructions associated with different operations to be executed by the system 102 or the electronic device 202; Paragraph 0050, Exemplary implementations of the memory 206 may include, but may not be limited to, Random Access Memory (RAM), Read Only Memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Hard Disk Drive (HDD), a Solid-State Drive (SSD), a CPU cache, and/or a Secure Digital (SD) card):
determining potential solutions from the node clusters using a [solver machine] (Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0090, The set of locations may be represented as nodes of an unconnected graph);
evolving the potential solutions by performing a simulated annealing process to output evolved solutions, each evolved solution comprising evolved node clusters, and each node being assigned to an evolved node cluster (Paragraph 0014, Some embodiments described in the present disclosure relate to methods and systems for generation of routes for a Vehicle Routing Problem (VRP) and variants thereof. Herein, the vehicle routing problem may be a combinatorial optimization problem whose goal may be to determine a set of optimal routes between a central depot and a set of locations; Paragraph 0015, VRP may have variants such as a Traveling Salesman Problem (TSP), a Capacitated Vehicle Routing Problem (CVRP), a Vehicle Routing Problem with Time-Windows (VRPTW), or a Pickup and Delivery Problem with Time-Windows (PDPTW). Each VRP variant may be bounded by a set of constraints. The set of constraints may vary amongst VRP variants based on application specific requirements associated with each VRP variant. The constraints may include, for example, a vehicle's capacity, a customer demand, a time window within which the delivery needs to be completed, and so on. Based on the constraints defining a VRP, hardware and/or software-based optimization solvers (for example, heuristics, meta-heuristics, exact algorithms, approximate algorithms, and so on) may be used for determination of a set of optimal routes as a solution of VRP; Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0026, In some embodiments, the optimization solver machine 106 may be a quantum annealing computer that may be specifically designed and hardware/software optimized to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing. Like the generalized quantum computing device, the quantum annealing computer may also use qubits and may require a carefully controlled cryogenic environment to function properly; As stated in Paragraph 0032 of Applicant’s specification, the evolved solution comprises breaking the CRVP problem into subproblems. Therefore, based on broadest reasonable interpretation in light of the specification, Ushijima-Mwesigwa et al. discloses “evolved node cluster” since it breaks the problem into subproblems by clustering/partitioning a set of locations);
invoking a quantum annealer to separately anneal each evolved node cluster of an evolved solution selected from the simulated annealing process to generate an optimal route through the nodes for each evolved node cluster of the selected evolved solution (Paragraph 0018, The optimization solver machine (for example, a quantum inspired hardware) may be used for minimization of the weighted summation based on a set of predefined constraints. The minimization may lead to the generation of a binary solution that may be used for the partitioning of the set of locations into the set of location clusters. The binary solutions may be generalized for all variants of VRP; Paragraph 0024, In one or more embodiments of the disclosure, the optimization solver machine 106 may be implemented as a generalized quantum computing device that may be hosted on a cloud optimization system. The cloud optimization system may be implemented as one of a private cloud, a public cloud, or a hybrid cloud. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a QUBO solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing to search for the solution of the QUBO formulation from a discrete solution space; Paragraph 0025, The generalized quantum computing device may be different from a digital bit-based computing device, such as digital devices that are based on transistor-based digital circuits. The generalized quantum computing device may include one or more quantum gates that use quantum bits (hereinafter referred to as “qubits”) to perform computations for different information processing applications, such as quantum annealing computations for solving the QUBO formulation. In general, a qubit can represent “0”, “1”, or a superposition of both “0” and “1”; Examiner interprets “solving a solution for each cluster using one or more qubits” as to “separately anneal each evolved node cluster of an evolved solution” since it’s known by an ordinary skill in the art that a quantum computing device uses each qubit to solve a subproblem (e.g., cluster));
and … sending a signal that communicates the optimal route as routing instructions to the [user device] and causes the [user using a vehicle] to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (Paragraph 0023, The user device 104 may include suitable logic, circuitry, and interfaces that may be configured to render on a display device a set of optimal routes or route recommendations for the plurality of vehicles. The set of optimal routes or the route recommendations may be rendered on an electronic user interface of the user device 104. The routes may be traversed by the plurality of vehicles for the delivery of goods or items; Paragraph 0043, Based on a solution of the set partition problem, the system 102 may control the user device 104 to render at least one optimal route of the set of optimal routes as a recommendation for each vehicle of the plurality of vehicles. For example, if the candidate route 124A is determined as an optimal route based on a solution of the set partition problem, then the system 102 may control the user device 104 to recommend the candidate route 124A for the transport vehicle 118A; Paragraph 0103, At 514, the user device 104 may be controlled to render at least one route recommendation for the plurality of vehicles 118A and 118B based on the set of candidate routes 124A and 124B. In an embodiment, the processor 204 may be configured to control the user device 104 to render at least one route recommendation for the plurality of vehicles 118A and 118B based on the set of candidate routes 124A and 124B. The set of candidate routes 124A and 124B may be rendered on a display of the user device 104 (or the display device 210A) as recommendations, based on a determination of the set of candidate routes 124A and 124B as optimal routes. The user 112 may view the optimal routes that may be used for transportation of items to the set of locations 120A . . . 120H).
Although Ushijima-Mwesigwa et al. discloses determining potential solutions from the node clusters using a solver machine, Ushijima-Mwesigwa et al. does not specifically disclose wherein the potential solutions from the node clusters are determined using a genetic algorithm.
However, Wu discloses determining potential solutions from the node clusters using a genetic algorithm (Page 2, Background, Paragraph 0002, At present, mainly using heurism algorithm to solve CVRP, comprising ant colony algorithm (Ant Colony Optimization, ACO), genetic algorithm (Genetic Algorithm, GA), Simulated Annealing Algorithm (SAA) and so on. However, the algorithm has respective disadvantages, ACO is easy to fall into local optimum GA convergence speed is slow, SAA is influenced by the parameter setting, therefore, the single heurism algorithm can not quickly and accurately solve CVRP, need to mix the algorithm; Page 2, Background, Paragraph 0003, K-means clustering algorithm is a clustering analysis algorithm of iterative solving, the step is randomly selecting K objects as initial clustering centre, then calculating the distance between each object and each clustering centre, distributing each object to the nearest clustering centre. K-means clustering algorithm convergence speed is fast, can improve the whole solving speed of the algorithm mixed with it, so the invention selects the K-means clustering algorithm to mix with the ACO. However, the K-means clustering algorithm is the clustering number K value of the selection is not easy to grasp, so for solving the heterogeneous vehicle problem CVRP, it needs to improve the one point and then mixed with the ACO to form a better performance of the hybrid algorithm).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining potential solutions of an optimization routing problem, wherein the potential solutions are determined using a solver machine of the invention of Ushijima-Mwesigwa et al. to further specify wherein the algorithm used to generate the potential solutions is a genetic algorithm of the invention of Wu because doing so would allow the method to mix a k-means clustering algorithm with a genetic algorithm to quickly and accurately solve a CVRP optimization problem (see Wu, Page 2, Background, Paragraph 0003). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Ushijima-Mwesigwa et al. discloses routing instructions to a user device by sending a signal that communicates the optimal route, wherein the user views the optimal route to navigate through the nodes of the optimal route (see at least Paragraphs 0023 & 0103). Although Ushijima-Mwesigwa et al. wherein a vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (e.g., a vehicle controlled by a user), the combination of Ushijima-Mwesigwa et al. and Wu does not specifically disclose wherein the vehicle is an autonomous vehicle.
However, Choi discloses routing an autonomous vehicle by sending a signal that communicates the optimal route as routing instructions to the autonomous vehicle and causes the autonomous vehicle to navigate through the nodes of the optimal route in accordance with the communicated routing instructions (Paragraph 0029, The cloud-based platform can further select one of the multiple routes as optimal, generate navigation instructions for that one route, and communicate the navigation instructions to the autonomous vehicle for performance, wherein the autonomous vehicle executes the instructions and is caused to traverse the one optimal route—without human oversight and/or intervention, and without any need or requirement to capture and process sensor data in real-time).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for generating an optimal route, wherein the optimal route is transmitted to a user to navigate through the nodes of the optimal route of the invention of Ushijima-Mwesigwa et al. and Wu to further specify wherein the optimal route is transmitted to an autonomous vehicle of the invention of Choi because doing so would allow the method to generate navigation instructions for the optimal route and communicate the navigation instructions to the autonomous vehicle for performance (see Choi, Paragraph 0029). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claims 5, 11, and 18 (Original), which are dependent of claims 1, 7, and 14, the combination of Ushijima-Mwesigwa et al., Wu, and Choi discloses all the limitations in claims 1, 7, and 14. Ushijima-Mwesigwa et al. further discloses determining an evolved solution having a minimum total route distance through nodes of the evolved node clusters (Paragraph 0014, Some embodiments described in the present disclosure relate to methods and systems for generation of routes for a Vehicle Routing Problem (VRP) and variants thereof. Herein, the vehicle routing problem may be a combinatorial optimization problem whose goal may be to determine a set of optimal routes between a central depot and a set of locations. The set of optimal routes may be used by a plurality of vehicles to transport items to the set of locations. The usage of the optimal routes by the vehicles may allow minimization of cost involved in the transportation of items using the plurality of vehicles. For example, a cost may be defined based on a distance that may be covered by the plurality of vehicles to deliver items to the set of locations, or a time spent in delivering the items to the set of locations; Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; As stated in Paragraph 0032 of Applicant’s specification, the evolved solution comprises breaking the CRVP problem into subproblems. Therefore, based on broadest reasonable interpretation in light of the specification, Ushijima-Mwesigwa et al. discloses “evolved node cluster” since it breaks the problem into subproblems by clustering/partitioning a set of locations), wherein the evolved solution selected for the quantum annealer comprises the minimum total route distance (Paragraph 0018, The optimization solver machine (for example, a quantum inspired hardware) may be used for minimization of the weighted summation based on a set of predefined constraints. The minimization may lead to the generation of a binary solution that may be used for the partitioning of the set of locations into the set of location clusters. The binary solutions may be generalized for all variants of VRP; Paragraph 0024, In one or more embodiments of the disclosure, the optimization solver machine 106 may be implemented as a generalized quantum computing device that may be hosted on a cloud optimization system. The cloud optimization system may be implemented as one of a private cloud, a public cloud, or a hybrid cloud. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a QUBO solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing to search for the solution of the QUBO formulation from a discrete solution space).
Claims 2, 8, and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Ushijima-Mwesigwa et al. (US 2024/0183670 A1), in view of Wu (CN 116341783 A), in further view of Choi (US 2022/0357167 A1) and Dridi et al. (US 11436519 B1).
Regarding claims 2, 8, and 15 (Original), which are dependent of claims 1, 7, and 14, the combination of Ushijima-Mwesigwa et al., Wu, and Choi discloses all the limitations in claims 1, 7, and 14. Although Ushijima-Mwesigwa et al. discloses using a quantum computer for generating an optimal route for each subproblem (see at least Paragraphs 0018 & 0025, the partitioning of the set of locations into the set of location clusters), Ushijima-Mwesigwa et al. does not specifically disclose adjusting the number of subproblems (e.g., clusters) based on the number of qubits that the quantum computer has available (e.g., threshold).
However, Dridi et al. discloses determining a number of [subproblems] into which each of the [variables] is assigned, the number of [subproblems] determined from a total number of [variables] and a constraint density threshold of the quantum annealer (Column 8, lines 11-32, Objective function configuration subsystem 104 may identify that this objective function, Q, includes four variables: x.sub.0, x.sub.1, x.sub.2, x.sub.3. In some embodiments, objective function configuration subsystem 104 is configured to determine a number of qubits that quantum computing system 120 includes. Based on the number of qubits, objective function configuration subsystem 104 may be configured to determine how to decompose the objective function into a set of subproblems, where each subproblem includes a subset of variables from the objective function. For example, if quantum computing system 120 included two qubits, objective function configuration subsystem 104 may form two sets of variables for objective function Q, such as a first set of variables {x.sub.0, x.sub.1} and a second set of variables {x.sub.2, x.sub.3}. In some embodiments, each set of variables may include a same number of variables. However, alternatively, some or all of the sets of variables may include different numbers of variables. For example, if the objective function includes five variables and the quantum computing system includes two qubits, then objective function configuration subsystem 104 may form three sets of variables, two of which include two variables and a third set including a single variable).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for generating an optimal routing solution using a quantum computer, wherein the solution is generated for each subproblem (e.g., cluster) based on the number of qubits of the invention of Ushijima-Mwesigwa et al. to further specify adjusting the number of subproblems based on the number of qubits that the quantum computer has available (e.g., threshold) of the invention of Dridi et al. because doing so would allow the method to determine how to decompose the objective function into a set of subproblems based on the number of qubits (see Dridi et al., Column 8, lines 11-32). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Claims 3-4, 9-10, and 16-17 are rejected under 35 U.S.C. 103 as being unpatentable over Ushijima-Mwesigwa et al. (US 2024/0183670 A1), in view of Wu (CN 116341783 A), in further view of Choi (US 2022/0357167 A1) and Kumar et al. (US 2023/0177415 A1).
Regarding claims 3, 9, and 16 (Original), which are dependent of claims 1, 7, and 14, the combination of Ushijima-Mwesigwa et al., Wu, and Choi discloses all the limitations in claims 1, 7, and 14. Although Ushijima-Mwesigwa et al. discloses evolved node clusters (e.g., clustering/partitioning a set of locations based on a distance), the combination of Ushijima-Mwesigwa et al. and Wu does not specifically disclose wherein the evolved node clusters match a number of vehicles available to traverse the optimal routes.
However, Kumar et al. further discloses combining at least a portion of the evolved node clusters for which optimal routes have been generated by the quantum annealer such that the combining of the evolved node clusters reduces a number of evolved node clusters of the selected evolved solution to match a number of vehicles available to traverse the optimal routes (Paragraph 0032, Accordingly, the teachings herein provide a hybrid quantum-classical computing platform that facilitates the processing of relatively large (e.g., over 5000) routing problems of practical magnitude efficiently and accurately. The inventors have recognized that to solve the traditional formulation of the routing problem having a significant size, using quantum computers, may overwhelm such platform (e.g., require millions of qubits). The teachings herein provide a technical solution to this problem by facilitating compatibility with quantum computers having various number of qubits. The routing optimization problem is decomposed to a feasible routing problem and an optimal route selection problem presented as exact set covering problem which is also NP-hard. A novel decomposition approach, such as “bagging,” can be used to solve the set cover problem, which further reduces the qubit requirements, but at the same time guarantees minimal loss of quality under the performance bounds; Paragraph 0035, A Vehicle routing problem with time windows (VRPTW) in the context of FIG. 3 can be defined as choosing the number of vehicles to use out of a set of available vehicles to serve a cluster of nodes (e.g., customers) in predetermined time windows. The clusters are depicted as circles having a uniform pattern. By way of example only and not by way of limitation, the service domain 302 includes three clusters and four depots. Each vehicle has a limited capacity. It starts from the depot and terminates at the depot. Each node should be served once; In this case, only available vehicles are used in the route optimization problem. Further, each available vehicle is used to cluster customers until the capacity of the vehicle is reached).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining optimal routes from a set of nodes, wherein the set of nodes are clustered based on a distance of the invention of Ushijima-Mwesigwa et al. to further specify wherein the set of nodes are clustered based on the number of vehicles available to traverse the optimal routes of the invention of Kumar et al. because doing so would allow the method to use a set of available vehicles to serve a cluster of nodes (see Kumar et al., Paragraph 0035). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claims 4, 10, and 17 (Original), which are dependent of claims 3, 9, and 16, the combination of Ushijima-Mwesigwa et al., Wu, Choi, and Kumar discloses all the limitations in claims 3, 9, and 16. Although Ushijima-Mwesigwa et al. discloses combining evolved node clusters based on a distance (Paragraph 0062, The distance-based objective function 304A may be formulated as a function of a distance between each pair of locations of the set of locations that may be assigned to a particular cluster of the set of clusters. The processor 204 may be configured to minimize a formulation of the distance-based objective function 304A to obtain an optimal partitioning of the set of locations into the set of location clusters), Ushijima-Mwesigwa et al. does not specifically disclose wherein the distance is based on a distance between the cluster centroids.
However, Wu further discloses determining cluster centroids for the evolved node clusters for which optimal routes have been generated, wherein combining the evolved node clusters is based on a distance between the cluster centroids (Page 2, Background, Paragraph 0003, K-means clustering algorithm is a clustering analysis algorithm of iterative solving, the step is randomly selecting K objects as initial clustering centre, then calculating the distance between each object and each clustering centre, distributing each object to the nearest clustering centre. K-means clustering algorithm convergence speed is fast, can improve the whole solving speed of the algorithm mixed with it, so the invention selects the K-means clustering algorithm to mix with the ACO).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining optimal routes from a set of nodes, wherein the set of nodes are clustered based on a distance of the invention of Ushijima-Mwesigwa et al. to further specify wherein the distance is based on a distance between the cluster centroids of the invention of Wu because doing so would allow the method to distribute each object to the nearest clustering centre (see Wu, Page 2, Background, Paragraph 0003). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Claims 6, 12, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Ushijima-Mwesigwa et al. (US 2024/0183670 A1), in view of Wu (CN 116341783 A), in further view of Choi (US 2022/0357167 A1) and Bernal et al. (US 2012/0301051 A1).
Regarding claims 6, 12, and 19 (Original), which are dependent of claims 1, 7, and 14, the combination of Ushijima-Mwesigwa et al., Wu, and Choi discloses all the limitations in claims 1, 7, and 14. Ushijima-Mwesigwa et al. further discloses wherein: the potential solutions are determined by the [solver machine] over a first timeframe (Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters);
the potential solutions are evolved by the simulated annealing process over a second timeframe (Paragraph 0014, Some embodiments described in the present disclosure relate to methods and systems for generation of routes for a Vehicle Routing Problem (VRP) and variants thereof. Herein, the vehicle routing problem may be a combinatorial optimization problem whose goal may be to determine a set of optimal routes between a central depot and a set of locations; Paragraph 0015, VRP may have variants such as a Traveling Salesman Problem (TSP), a Capacitated Vehicle Routing Problem (CVRP), a Vehicle Routing Problem with Time-Windows (VRPTW), or a Pickup and Delivery Problem with Time-Windows (PDPTW). Each VRP variant may be bounded by a set of constraints. The set of constraints may vary amongst VRP variants based on application specific requirements associated with each VRP variant. The constraints may include, for example, a vehicle's capacity, a customer demand, a time window within which the delivery needs to be completed, and so on. Based on the constraints defining a VRP, hardware and/or software-based optimization solvers (for example, heuristics, meta-heuristics, exact algorithms, approximate algorithms, and so on) may be used for determination of a set of optimal routes as a solution of VRP; Paragraph 0022, An example of an environment with delivery locations and vehicles is shown via a map 114. An exemplary vehicle routing environment may include a depot, a set of locations (for example, warehouse or customer locations), and a plurality of vehicles (for example, transport vehicles). To solve the optimization problem, the system 102 may generate a set of location clusters by partitioning the set of locations using a solution obtained from the optimization solver machine 106 and may generate a set of candidate routes based on the set of location clusters; Paragraph 0026, In some embodiments, the optimization solver machine 106 may be a quantum annealing computer that may be specifically designed and hardware/software optimized to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing. Like the generalized quantum computing device, the quantum annealing computer may also use qubits and may require a carefully controlled cryogenic environment to function properly; As stated in Paragraph 0032 of Applicant’s specification, the evolved solution comprises breaking the CRVP problem into subproblems. Therefore, based on broadest reasonable interpretation in light of the specification, Ushijima-Mwesigwa et al. discloses “evolved node cluster” since it breaks the problem into subproblems by clustering/partitioning a set of locations);
the evolved node clusters of the selected evolved solution are annealed by the quantum annealer over a third timeframe (Paragraph 0018, The optimization solver machine (for example, a quantum inspired hardware) may be used for minimization of the weighted summation based on a set of predefined constraints. The minimization may lead to the generation of a binary solution that may be used for the partitioning of the set of locations into the set of location clusters. The binary solutions may be generalized for all variants of VRP; Paragraph 0024, In one or more embodiments of the disclosure, the optimization solver machine 106 may be implemented as a generalized quantum computing device that may be hosted on a cloud optimization system. The cloud optimization system may be implemented as one of a private cloud, a public cloud, or a hybrid cloud. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a QUBO solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing to search for the solution of the QUBO formulation from a discrete solution space; Paragraph 0025, The generalized quantum computing device may be different from a digital bit-based computing device, such as digital devices that are based on transistor-based digital circuits. The generalized quantum computing device may include one or more quantum gates that use quantum bits (hereinafter referred to as “qubits”) to perform computations for different information processing applications, such as quantum annealing computations for solving the QUBO formulation. In general, a qubit can represent “0”, “1”, or a superposition of both “0” and “1”); ...
Although Ushijima-Mwesigwa et al. discloses determining potential solutions from the node clusters using a solver machine, Ushijima-Mwesigwa et al. does not specifically disclose wherein the potential solutions from the node clusters are determined using a genetic algorithm.
However, Wu discloses wherein: the potential solutions are determined by the genetic algorithm over a first timeframe (Page 2, Background, Paragraph 0002, At present, mainly using heurism algorithm to solve CVRP, comprising ant colony algorithm (Ant Colony Optimization, ACO), genetic algorithm (Genetic Algorithm, GA), Simulated Annealing Algorithm (SAA) and so on. However, the algorithm has respective disadvantages, ACO is easy to fall into local optimum GA convergence speed is slow, SAA is influenced by the parameter setting, therefore, the single heurism algorithm can not quickly and accurately solve CVRP, need to mix the algorithm; Page 2, Background, Paragraph 0003, K-means clustering algorithm is a clustering analysis algorithm of iterative solving, the step is randomly selecting K objects as initial clustering centre, then calculating the distance between each object and each clustering centre, distributing each object to the nearest clustering centre. K-means clustering algorithm convergence speed is fast, can improve the whole solving speed of the algorithm mixed with it, so the invention selects the K-means clustering algorithm to mix with the ACO. However, the K-means clustering algorithm is the clustering number K value of the selection is not easy to grasp, so for solving the heterogeneous vehicle problem CVRP, it needs to improve the one point and then mixed with the ACO to form a better performance of the hybrid algorithm); …
and a number of iterations during which the genetic algorithm and the simulated annealing process are employed is determined from … a total time threshold (Page 2, Background, Paragraph 0002, At present, mainly using heurism algorithm to solve CVRP, comprising ant colony algorithm (Ant Colony Optimization, ACO), genetic algorithm (Genetic Algorithm, GA), Simulated Annealing Algorithm (SAA) and so on. However, the algorithm has respective disadvantages, ACO is easy to fall into local optimum GA convergence speed is slow, SAA is influenced by the parameter setting, therefore, the single heurism algorithm can not quickly and accurately solve CVRP, need to mix the algorithm; Page 8, Paragraphs 0012-0013, Specifically, the distribution vehicle after distributing, then using ACO after clustering the cluster formed by global optimization, respectively optimizing the distribution path for each clustering cluster. Through the simulation experiment, according to the cluster formed after clustering, using ACO to calculate the quality and algorithm operation time of the ant solution obtained by calculating the proper iteration times and updating to the current iteration times of the optimal solution; In this case, Examiner interprets the “updated iteration time” as the “time threshold”).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining potential solutions of an optimization routing problem, wherein the potential solutions are determined using a solver machine of the invention of Ushijima-Mwesigwa et al. to further specify wherein the algorithm used to generate the potential solutions is a genetic algorithm of the invention of Wu because doing so would allow the method to mix a k-means clustering algorithm with a genetic algorithm to quickly and accurately solve a CVRP optimization problem (see Wu, Page 2, Background, Paragraph 0003). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Although the combination of Ushijima-Mwesigwa et al. and Wu discloses calculating the proper iteration times of the optimal solution, the combination of Ushijima-Mwesigwa et al. and Wu does not specifically disclose wherein the calculated iteration time is based on an average.
However, Bernal et al. discloses and a number of iterations during which the … process are employed is determined from an average of the first timeframe and the second timeframe, the third timeframe, and a total time threshold (Paragraph 0041, where for a given level i, N.sub.i* is the number of iterations needed to converge and t, is the average iteration time).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining potential solutions of an optimization routing problem, wherein a number of iterations is calculated based on the current iteration time of the invention of Ushijima-Mwesigwa et al. and Wu to further specify wherein the calculated iteration time is based on an average of the invention of Bernal et al. because doing so would allow the method to calculate the number of iterations needed to converge based on the average iteration time (see Bernal et al., Paragraph 0041). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Claims 13 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Ushijima-Mwesigwa et al. (US 2024/0183670 A1), in view of Wu (CN 116341783 A), in further view of Choi (US 2022/0357167 A1) and Sajid (Sajid, M., Jafar, A. and Sharma, S., 2020, November. Hybrid genetic and simulated annealing algorithm for capacitated vehicle routing problem. In 2020 Sixth International Conference on Parallel, Distributed and Grid Computing (PDGC) (pp. 131-136). IEEE).
Regarding claims 13 and 20 (Original), which are dependent of claims 7 and 14, the combination of Ushijima-Mwesigwa et al., Wu, and Choi discloses all the limitations in claims 7 and 14. Although Ushijima-Mwesigwa et al. discloses evolving the potential solutions by performing a simulated annealing process to output evolved solutions, Ushijima-Mwesigwa et al. does not specifically disclose wherein the node clusters from which the potential solutions are defined using the genetic algorithm comprise prior evolved node clusters determined by the simulated annealing during a prior iteration.
However, Sajid discloses wherein the node clusters from which the potential solutions are defined using the genetic algorithm comprise prior evolved node clusters determined by the simulated annealing during a prior iteration (Page 133, Overview of proposed HGSA Algorithm, The proposed HGSA algorithm is a hybrid algorithm which combines global optimization method i.e. genetic algorithm (GA) and local search simulated annealing (SA) algorithm. GA is a well-known established evolutionary algorithm and works based on natural selection process to solve search and optimization problems. SA is also a well known technique and works based on annealing in metallurgy. The performance of proposed HGSA algorithm is mainly based on factors like solutions’ structure and evaluation strategy, different operators, and number of generations. As shown in Figure 3, the process of HGSA algorithm starts with a population of randomly generated individuals and then, it generates new population. HGSA produces offspring using either genetic operators or Simulated Annealing (SA) based on swap, inversion, 2-opt* and exchange operators [23]. The value 0.7 against random number is set after various experiments. The newly formed population is used in the next iteration for further iterations of HGSA. The algorithm terminates after specified number of iterations).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for determining potential solutions of an optimization routing problem of the invention of Ushijima-Mwesigwa et al. and Wu to further specify wherein the node clusters from which the potential solutions are defined using the genetic algorithm comprise prior evolved node clusters determined by the simulated annealing during a prior iteration of the invention of Sajid because doing so would allow the method to use a newly formed population in the next iteration for further iterations of Hybrid Genetic and Simulated Annealing (HGSA) algorithm (see Sajid, Page 133, Overview of proposed HGSA Algorithm). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Kumar (US 2025/0037048 A1) – discloses one or more tools used by the AI engine (216) include any or a combination of Genetic Algorithms (GA) and Simulated Annealing (SA) to execute the one or more techniques (see at least Paragraph 0016).
Weichenberger (AU 2018201944 B2) - discloses performing the genetic algorithm using the quantum computing device includes iteratively performing the genetic algorithm until a determined quality of an observed global solution is above a predetermined threshold (see at least Paragraph 0015).
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MARJORIE PUJOLS-CRUZ whose telephone number is (571)272-4668. The examiner can normally be reached Mon-Thru 7:30 AM - 5:00 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Patricia H Munson can be reached at (571)270-5396. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/M.P./Examiner, Art Unit 3624 /HAMZEH OBAID/Primary Examiner, Art Unit 3624