The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
DETAILED ACTION
Notice to Applicant
In response to the communication received on 01/09/2026, the following is a Final Office Action for Application No. 17821147.
Status of Claims
Claims 1, 3-8, 10-13 and 15-19 are pending.
Claims 2, 9, and 14 are cancelled.
Claims 17-19 are new.
Information Disclosure Statement
The information disclosure statement(s) (IDS) received on 01/09/2026 has been acknowledged. The submission is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Priority
As required by M.P.E.P. 201.14(c), acknowledgement is made of applicant’s claim for priority based on: 17821147 filed 08/19/2022 Claims Priority from Provisional Application 63235074 , filed 08/19/2021; 17821147 Claims Priority from Provisional Application 63250982 , filed 09/30/2021; 17821147 Claims Priority from Provisional Application 63267411 , filed 02/01/2022; 17821147 Claims Priority from Provisional Application 63367975 , filed 07/08/2022.
Response to Amendments
Applicant’s amendments and associated arguments have been fully considered.
Response to Arguments
Applicant’s arguments with respect to the claims have been considered but are not persuasive:
Applicant argues that Haghani in view of Xu fails to teach as recited in independent claim 1 (and similar claims):
[Firstly, mapping to Applicant’s arguments:]
wherein the local area route relaxation comprises an ng-route relaxation. The Examiner respectfully disagrees. The Broadest Reasonable Interpretation includes that the local area (LA) route relaxation comprises an ng-route relaxation which allows for the ng-route relaxation to be the at least one local area (LA) route relaxation since this is the only listed function in the comprised-of set of functions. Since Haghani teaches ng-route relaxation, then Haghani teaches local area (LA) route relaxation per the comprised-of set. Haghani teaches at least ¶0006 which states “This present disclosure relates to systems and methods for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns. In particular, the system determines valid smooth dual optimal inequalities (S-DOI) for a capacitated vehicle routing problem (CVRP) where optimization is performed over a set of valid columns. The system also determines valid flexible dual optimal inequalities (F-DOI) for the CVRP where optimization is performed over the set of valid columns. Then, the system adapts the S-DOI and the F-DOI to yield smooth and flexible dual optimal inequalities (SF-DOI) with respect to ng-route relaxed columns. The system utilizes the SF-DOI as relaxed DOI for the ng-route relaxed columns to accelerate column generation optimization over the ng-route relaxed columns.” Thus, Haghani teaches the above limitation.
[Secondly, mapping to Applicant’s arguments:]
shortest path algorithm. The Examiner respectfully disagrees, and in particular this claim limitation is found in at least claim 5 (and similar claims) which is dependent on claim 4 (and similar claims). Nevertheless, Haghani teaches Claim 5. The system of claim 4, wherein the pricing problem is an integer linear program (ILP) that is solved using Dijkstra's shortest-path algorithm (¶0017 By way of background, the systems and methods of the present disclosure accelerate the CG solution to expanded LP relaxations utilizing DOI. Expanded LP relaxations are utilized to solve integer linear programs (ILPs) for which compact LP relaxations are loose. Compact LP relaxations contain a small number of variables whereas expanded LP relaxations contain a large number of variables (e.g., columns). An expanded LP relaxation is typically much tighter than a corresponding compact LP relaxation and permits efficient optimization of the corresponding ILP. ¶0019 n the CVRP, a column is valid if it (1) does not include a customer more than once (e.g., no cycles in the corresponding route), and (2) does not service more demand than the vehicle has capacity. The pricing problem for CVRP is an elementary resource constrained shortest path problem, which is strongly NP-hard. A super-set of the set of valid columns, referred to as ng-routes, can facilitate solving large CVRP instances. Ng-routes provide for making pricing tractable at the cost of a decrease in the tightness of the underlying expanded LP relaxation.). Although not explicitly taught by Haghani, Xu teaches in the analogous art of network support for dynamic vehicle routing: Dijkstra's shortest-path algorithm (¶0068 Different methods may be used to plan which path segments L1-L12 to include in a route 403. For example, Dijkstra's algorithm, A* algorithm, Dynamic Programming algorithm, Bellman-Ford algorithm, and others may be used to plan the route. In one example according to Dijkstra's algorithm, planning a route may start at a start node. For example, the node 401 with cell 1 may be the start node. The other nodes 401 may be marked as unvisited and included in an unvisited set of nodes 401.). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani for the reasons stated in the Office action. Thus, Haghani in view of Xu teaches the above limitation.
[Thirdly, mapping to Applicant’s arguments:]
master problem is a linear programming problem and the subproblem is a pricing problem. The Examiner respectfully disagrees, and in particular this claim limitation is found in at least claim 4 (and similar claims). Nevertheless, Haghani teaches: Claim 4. The system of claim 1, wherein the master problem is a linear programming problem and the subproblem is a pricing problem (¶0017 By way of background, the systems and methods of the present disclosure accelerate the CG solution to expanded LP relaxations utilizing DOI. Expanded LP relaxations are utilized to solve integer linear programs (ILPs) for which compact LP relaxations are loose. Compact LP relaxations contain a small number of variables whereas expanded LP relaxations contain a large number of variables (e.g., columns). An expanded LP relaxation is typically much tighter than a corresponding compact LP relaxation and permits efficient optimization of the corresponding ILP. CG can be utilized to solve expanded LP relaxations. Since the set of all feasible columns is large and cannot be easily enumerated, a sufficient set of columns is constructed iteratively utilizing CG. Pricing refers to the process of identifying negative reduced cost columns. Pricing is performed by solving a small scale combinatorial optimization problem parameterized by the dual solution of the expanded LP relaxation defined over the nascent set of columns). Thus, Haghani teaches the above limitation.
[Fourthly, mapping to Applicant’s arguments:]
wherein the column corresponds to a particular route with a topological ordering of items serviced by a particular vehicle on the particular route. The Examiner respectfully disagrees, and in particular the summary of Haghani ¶0006 states that “This present disclosure relates to systems and methods for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns. In particular, the system determines valid smooth dual optimal inequalities (S-DOI) for a capacitated vehicle routing problem (CVRP) where optimization is performed over a set of valid columns. The system also determines valid flexible dual optimal inequalities (F-DOI) for the CVRP where optimization is performed over the set of valid columns. Then, the system adapts the S-DOI and the F-DOI to yield smooth and flexible dual optimal inequalities (SF-DOI) with respect to ng-route relaxed columns. The system utilizes the SF-DOI as relaxed DOI for the ng-route relaxed columns to accelerate column generation optimization over the ng-route relaxed columns.” Here, the system adapts the S-DOI and the F-DOI to yield smooth and flexible dual optimal inequalities (SF-DOI) with respect to ng-route relaxed columns, and the system utilizes the SF-DOI as relaxed DOI for the ng-route relaxed columns to accelerate column generation optimization over the ng-route relaxed columns. Thus, the ng-route relaxed columns to accelerate column generation optimization over the ng-route relaxed columns which corresponds to particular routing. The topological ordering of items serviced is taught in at least Haghini ¶0020 which states “A review of the minimum weight set cover formulation utilized in operations research along with the CG solution and its application to vehicle routing will now be described. A minimum weight set cover problem can be solved via a standard CG method. custom-character denotes a set of N∈Z.sub.+ items to be covered and the CG formulation includes a continuous variable θ.sub.l≥0 for every column l∈Ω where Ω is the set of all valid columns. In the standard cover formulation, a column can cover an item at most once. This can be relaxed when considering relaxed columns such as ng-routes, which can cover an item more than once. In the context of CG, the set Ω is generally exponentially large with respect to N, and therefore it can be impractical to explicitly consider the entire set Ω during optimization. Accordingly, for every column l∈Ω and for every item u∈custom-character, α.sub.ul∈{0,1} can be a binary constant equal to 1 if l covers u and otherwise α.sub.ul=0. A cost c.sub.l can be associated with the column l via a non-decreasing function over α.sub.ul ∀u∈custom-character. The minimum weight set cover is given by Equation 1.” Here, a minimum weight set cover problem can be solved via a standard CG method custom-character denotes a set of N∈Z.sub.+ items to be covered and the CG formulation includes a continuous variable θ.sub.l≥0 for every column l∈Ω where Ω is the set of all valid columns, and in the standard cover formulation, a column can cover an item at most once; further, this can be relaxed when considering relaxed columns such as ng-routes, which can cover an item more than once. Thus, Haghani teaches the above limitation.
For the reasons detailed above, Examiner is not persuaded that the claims are patentably distinguishable over the Haghani in view of Xu disclosure. Rather, Examiner maintains that the Haghani in view of Xu combination renders obvious the claimed invention. Accordingly, the previous prior art rejection is maintained.
As per the 101 rejection, Applicant argues that the claims are in favor of eligibility per Prong One of Step 2A, however Examiner respectfully disagrees. Per Prong One of Step 2A, the identified recitation of an abstract idea falls within at least one of the Abstract Idea Groupings consisting of: Mathematical Concepts, Mental Processes, or Certain Methods of Organizing Human Activity. Particularly, the identified recitation falls within the Mental Processes including concepts performed in the human mind (including an observation, evaluation judgment, opinion) and/or Certain Methods of Organizing Human Activity including managing personal behavior or relationships or interactions between people (including social activities, teaching, and following rules of instructions). Since the recitation of the claims falls into at least one of the above Groupings, there is a basis for providing further analysis with regard to Prong Two of Step 2A to determine whether the recitation of an abstract idea is deduced to being directed to an abstract idea. Thus, the rejection is maintained.
Applicant argues that the claims are in favor of eligibility per Prong Two of Step 2A, however Examiner respectfully disagrees. Per Prong Two of Step 2A, this judicial exception is not integrated into a practical application because the claim as a whole does not integrate the identified abstract idea into a practical application. The memory medium, processor, vehicle and/or robot is recited at a high level of generality, i.e., as a generic processor performing a generic computer function of processing/transmitting data. This generic processor server limitation is no more than mere instructions to apply the exception using a generic computer component. Further, memory medium, processor, vehicle and/or robot to inter alia perform the function of transmitting the corresponding optimized route is mere instruction to apply an exception using a generic computer component which cannot integrate a judicial exception into a practical application. Accordingly, this/these additional element(s) does/do not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. In other words, the present claims use a generic processing device and memory medium to inter alia perform the function of transmitting the corresponding optimized route which is a concept that can be performed in the human mind. The processor is merely used to perform the function(s), and the processor does not integrate the abstract idea into a practical application since there are no meaningful limits on practicing the abstract idea. Thus, since the claims are directed to the determined judicial exception in view of the two prongs of Step 2A, the 2019 PEG flowchart is directed to Step 2B. Thus, the rejection is maintained.
Applicant argues that the claims are in favor of eligibility per Step 2B, however Examiner respectfully disagrees. Therein, the additional elements and combinations therewith are examined in the claims to determine whether the claims as a whole amounts to significantly more than the judicial exception. It is noted here that the additional elements are to be considered both individually and as an ordered combination. In this case, the claims each at most comprise additional elements of: memory medium, processor, vehicle and/or robot . Taken individually, the additional limitations each are generically recited and thus does not add significantly more to the respective limitations. Further, memory medium, processor, vehicle and/or robot to inter alia perform the function of transmitting the corresponding optimized route is mere instruction to apply an exception using a generic computer component which cannot provide an inventive concept in Step 2B (or, looking back to Step 2A, cannot integrate a judicial exception into a practical application). For further support, the Applicant’s specification supports the claims being directed to use of a generic computer/memory type structure. Taken as an ordered combination, the claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the limitations are directed to limitations referenced in Alice Corp. that are not enough to qualify as significantly more when recited in a claim with an abstract idea include the non-limiting or non-exclusive examples of MPEP § 2106.05. Thus, the rejection is maintained.
In an effort to further expedite prosecution, see: July 2024 Subject Matter Eligibility Examples, Example 47. Anomaly Detection. Per the analysis of claim 2 Example 47, the analysis refers to MPEP 2106.05(f) which provides the following considerations for determining whether a claim simply recites a judicial exception with the words “apply it” (or an equivalent), such as mere instructions to implement an abstract idea on a computer: (1) whether the claim recites only the idea of a solution or outcome i.e., the claim fails to recite details of how a solution to a problem is accomplished; (2) whether the claim invokes computers or other machinery merely as a tool to perform an existing process; and (3) the particularity or generality of the application of the judicial exception. Although the additional elements, e.g. (per Example 47) “using a trained ANN”, limits the identified judicial exceptions, e.g. (per Example 47) “detecting one or more anomalies in a data set using the trained ANN” and, e.g. (per Example 47) “analyzing the one or more detected anomalies using the trained ANN to generate anomaly data,” this type of limitation merely confines the use of the abstract idea to a particular technological environment, e.g. (per Example 47: neural networks) and thus fails to add an inventive concept to the claims. See MPEP 2106.05(h). As an exemplary direction for claim limitations to be eligible, see claims 1 and 3 of Example 47.
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, 3-8, 10-13 and 15-19 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more. The claims fall within statutory class of process or machine; hence, the claims fall under statutory category of Step 1.
Step 2 is the two-part analysis from Alice Corp. (also called the Mayo test). The 2019 PEG makes two changes in Step 2A: It sets forth new procedure for Step 2A (called “revised Step 2A”) under which a claim is not “directed to” a judicial exception unless the claim satisfies a two-prong inquiry. The two-prong inquiry is as follows: Prong One: evaluate whether the claim recites a judicial exception (an abstract idea enumerated in the 2019 PEG, a law of nature, or a natural phenomenon). If claim recites an exception, then Prong Two: evaluate whether the claim recites additional elements that integrate the exception into a practical application of the exception. The claim(s) recite(s) the following abstract idea indicated by non-boldface font and additional limitations indicated by boldface font:
at least one memory; and at least one processor that is coupled to the at least one memory, wherein the at least one processor is configured to determine a route for a vehicle from a starting depot location to an ending depot location, wherein the route services a plurality of customers, each of the plurality of customers being associated with an item, and wherein the at least one processor is further configured to: receive information associated with the starting depot location, the ending depot location, and the items associated with the plurality of customers, wherein the information for each of the items comprises an item location and an integer demand indicating a size of the item, generate, based on the starting depot location, the ending depot location, the integer demand and the item location of each of the items, and a capacity of the vehicle, a vehicle routing problem, wherein a solution to the vehicle routing problem minimizes a distance of the route, wherein the route (a) starts at the starting depot location, (b) ends at the ending depot location, (c) visits each item location no more than once, and (d) services a capacity that does not exceed the capacity of the vehicle to carry items, split the vehicle routing problem into a master problem and a subproblem, wherein the master problem and the subproblem comprise constraints associated with the vehicle routing problem, compute, for the subproblem, a plurality of costs associated with distances between one or more item locations such that each of the distances is less than a first threshold, iteratively solve, using a column generation method with a local area route relaxation and based on the plurality of costs, the master problem and the subproblem to generate the solution comprising an optimized route that minimizes the distance of the route, and transmit, to the vehicle, the optimized route, wherein the column generation method comprises adding a column to the master problem as part of solving the subproblem, wherein the column corresponds to a particular route with a topological ordering of items serviced by a particular vehicle on the particular route, wherein the local area route relaxation comprises an ng-route relaxation, wherein the ng-route relaxation specifies that a first item location is followed by a second item location such that a distance between the first item location and the second item location is greater than a second threshold, wherein the local area route relaxation specifies that the distance between the first item location and the second item location is greater than a third threshold, and wherein the first threshold, second threshold and third threshold are positive numbers and wherein the third threshold is greater than the second threshold.
[or]
the plurality of robots being configured to service a plurality of customers, each of the plurality of customers being associated with an item, and the method comprising:receiving information associated with a depot location and the items associated with the plurality of customers, wherein the information for each of the items comprises an item location and an integer demand indicating a size of the item; generating, based on the depot location, the integer demand and the item location of each of the items, and a capacity of each of the plurality of robots, a robot routing problem, wherein a solution to the robot routing problem minimizes a distance of the route, wherein the route (a) starts at the depot location, (b) ends at the depot location, (c) visits each item location no more than once, and (d) services a capacity that does not exceed the capacity of the corresponding robot to carry items; splitting the robot routing problem into a master problem and a subproblem, wherein the master problem and the subproblem comprise constraints associated with the robot routing problem; computing, for the subproblem, a plurality of costs associated with distances between one or more item locations such that each of the distances is less than a first threshold; iteratively solving, using a column generation method with a local area route relaxation and based on the plurality of costs, the master problem and the subproblem to generate the solution comprising an optimized route that minimizes the distance of the route; and transmitting, to each of the plurality of robots, the corresponding optimized route, wherein the column generation method comprises adding a column to the master problem as part of solving the subproblem, wherein the column corresponds to a particular route with a topological ordering of items serviced by a particular vehicle on the particular route, wherein the local area route relaxation comprises an ng-route relaxation, wherein the ng-route relaxation specifies that a first item location is followed by a second item location such that a distance between the first item location and the second item location is greater than a second threshold, wherein the local area route relaxation specifies that the distance between the first item location and the second item location is greater than a third threshold, and wherein the first threshold, second threshold and third threshold are positive numbers and wherein the third threshold is greater than the second threshold.
[or]
receiving information associated with the depot location and a plurality of customers, wherein each of the plurality of customers is associated with an item, and wherein the information for each of the items comprises an item location and an integer demand indicating a size of the item; generating, based on the depot location, the integer demand and the item location of each of the items, and a capacity of each of the plurality of autonomous vehicles, a vehicle routing problem, wherein a solution to the vehicle routing problem minimizes a distance of the route, wherein the route (a) starts at the depot location, (b) ends at the depot location, and (c) visits each item location no more than once, wherein each autonomous vehicle is configured to service a capacity that does not exceed its capacity to carry items; iteratively solving, using a column generation method with a local area route relaxation, the vehicle routing problem to generate the solution comprising an optimized route that minimizes the distance of the route; and transmitting, to each of the plurality of autonomous vehicles, the corresponding optimized route, wherein the vehicle routing problem comprises a master problem and a subproblem, the master problem and the subproblem comprising constraints associated with the vehicle routing problem, wherein the column generation method comprises adding a column to the master problem as part of solving the subproblem, wherein the column corresponds to a particular route with a topological ordering of items serviced by a particular vehicle on the particular route, wherein the local area route relaxation comprises an ng-route relaxation, wherein the ng-route relaxation specifies that a first item location is followed by a second item location such that a distance between the first item location and the second item location is greater than a second threshold, wherein the local area route relaxation specifies that the distance between the first item location and the second item location is greater than a third threshold, and wherein the first threshold, second threshold and third threshold are positive numbers and wherein the third threshold is greater than the second threshold.
Per Prong One of Step 2A, the identified recitation of an abstract idea falls within at least one of the Abstract Idea Groupings consisting of: Mathematical Concepts, Mental Processes, or Certain Methods of Organizing Human Activity. Particularly, the identified recitation falls within the Mental Processes including concepts performed in the human mind (including an observation, evaluation judgment, opinion) and/or Mathematical Concepts. “[In a claim that includes a series of steps that recite mental steps as well as a mathematical calculation, an examiner should identify the claim as reciting both a mental process and a mathematical concept for Step 2A, Prong One to make the analysis clear on the record.” MPEP 2106.04, subsection II.B. Under such circumstances, however, the Supreme Court has treated such claims in the same manner as claims reciting a single judicial exception. Id. (discussing Bilski v. Kappos, 561 U.S. 593 (2010)). Limitations are considered together as a single abstract idea for further analysis.
Per Prong Two of Step 2A, this judicial exception is not integrated into a practical application because the claim as a whole does not integrate the identified abstract idea into a practical application. The memory medium, processor, vehicle and/or robot is recited at a high level of generality, i.e., as a generic processor performing a generic computer function of processing/transmitting data. This generic memory medium, processor, vehicle and/or robot limitation is no more than mere instructions to apply the exception using a generic computer component. Further, transmitting the corresponding optimized route by a memory medium, processor, vehicle and/or robot is mere instruction to apply an exception using a generic computer component which cannot integrate a judicial exception into a practical application. Accordingly, this/these additional element(s) does/do not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. Thus, since the claims are directed to the determined judicial exception in view of the two prongs of Step 2A, the 2019 PEG flowchart is directed to Step 2B.
Per Step 2B, the additional elements and combinations therewith are examined in the claims to determine whether the claims as a whole amounts to significantly more than the judicial exception. It is noted here that the additional elements are to be considered both individually and as an ordered combination. In this case, the claims each at most comprise additional elements of: memory medium, processor, vehicle and robot. Taken individually, the additional limitations each are generically recited and thus does not add significantly more to the respective limitations. Further, transmitting the corresponding optimized route by a memory medium, processor, vehicle and/or robot is mere instruction to apply an exception using a generic computer component which cannot provide an inventive concept in Step 2B (or, looking back to Step 2A, cannot integrate a judicial exception into a practical application). For further support, the Applicant’s specification supports the claims being directed to use of a generic computer/memory type structure at ¶00193 wherein “Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer.” Taken as an ordered combination, the claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the limitations are directed to limitations referenced in Alice Corp. that are not enough to qualify as significantly more when recited in a claim with an abstract idea include, as a non-limiting or non-exclusive examples: i. Adding the words "apply it" (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, e.g., a limitation indicating that a particular function such as creating and maintaining electronic records is performed by a computer, as discussed in Alice Corp., 134 S. Ct. at 2360, 110 USPQ2d at 1984 (see MPEP § 2106.05(f));
PNG
media_image1.png
18
19
media_image1.png
Greyscale
ii. Simply appending well-understood, routine, conventional activities previously known to the industry, specified at a high level of generality, to the judicial exception, e.g., a claim to an abstract idea requiring no more than a generic computer to perform generic computer functions that are well-understood, routine and conventional activities previously known to the industry, as discussed in Alice Corp., 134 S. Ct. at 2359-60, 110 USPQ2d at 1984 (see MPEP § 2106.05(d));
PNG
media_image1.png
18
19
media_image1.png
Greyscale
iii. Adding insignificant extra-solution activity to the judicial exception, e.g., mere data gathering in conjunction with a law of nature or abstract idea such as a step of obtaining information about credit card transactions so that the information can be analyzed by an abstract mental process, as discussed in CyberSource v. Retail Decisions, Inc., 654 F.3d 1366, 1375, 99 USPQ2d 1690, 1694 (Fed. Cir. 2011) (see MPEP § 2106.05(g)); or
PNG
media_image1.png
18
19
media_image1.png
Greyscale
v. Generally linking the use of the judicial exception to a particular technological environment or field of use, e.g., a claim describing how the abstract idea of hedging could be used in the commodities and energy markets, as discussed in Bilski v. Kappos, 561 U.S. 593, 595, 95 USPQ2d 1001, 1010 (2010) or a claim limiting the use of a mathematical formula to the petrochemical and oil-refining fields, as discussed in Parker v. Flook. The courts have recognized the following computer functions inter alia to be well-understood, routine, and conventional functions when they are claimed in a merely generic manner: performing repetitive calculations; receiving, processing, and storing data (e.g., the present claims); electronically scanning or extracting data; electronic recordkeeping; automating mental tasks (e.g., process/machine/manufacture for performing the present claims); and receiving or transmitting data (e.g., the present claims).
The dependent claims do not cure the above stated deficiencies, and in particular, the dependent claims further narrow the abstract idea without reciting additional elements that integrate the exception into a practical application of the exception or providing significantly more than the abstract idea. Additional elements are stated in Claim 7 as follows: “wherein the at least one processor comprises a first processor that is used to solve the master problem and a second processor that is used to solve the subproblem.” Taken individually and in combination, the additional limitations each are generically recited and thus does not add significantly more to the respective limitations. Since there are no elements or ordered combination of elements that amount to significantly more than the judicial exception, the claims are not eligible subject matter under 35 USC §101.
Thus, viewed as a whole, these additional claim element(s) do not provide meaningful limitation(s) to transform the abstract idea into a patent eligible application of the abstract idea such that the claim(s) amounts to significantly more than the abstract idea itself. Therefore, the claim(s) are rejected under 35 U.S.C. 101 as being directed to non-statutory subject matter.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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 of this title, 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.
Claims 1, 3-8, 10-13 and 15-19 are rejected under 35 U.S.C. 103 as being unpatentable over Haghani et al. (US 20210325195 A1) hereinafter referred to as Haghani in view of Xu et al. (US 20220196426 A1) hereinafter referred to as Xu.
Haghani teaches:
Claim 1. A system for vehicular routing, comprising:
at least one memory;and at least one processor that is coupled to the at least one memory, wherein the at least one processor is configured to determine a route for a vehicle from a starting depot location to an ending depot location, wherein the route services a plurality of customers, each of the plurality of customers being associated with an item, and wherein the at least one processor is further configured to (¶0019 Some classes of mixed-integer optimization problems, such as the CVRP, consider a super-set of the columns including original columns (e.g., valid columns) and additional columns (e.g., relaxed columns) to increase tractability of pricing. SF-DOI does not provide for modeling relaxed columns. In the CVRP, a column is valid if it (1) does not include a customer more than once (e.g., no cycles in the corresponding route), and (2) does not service more demand than the vehicle has capacity. The pricing problem for CVRP is an elementary resource constrained shortest path problem, which is strongly NP-hard. A super-set of the set of valid columns, referred to as ng-routes, can facilitate solving large CVRP instances. Ng-routes provide for making pricing tractable at the cost of a decrease in the tightness of the underlying expanded LP relaxation. The ng-route relaxation provides for a customer to be visited more than once in a route but precludes many short cycles localized in space. ¶0045 Turning to the drawings, FIG. 1 is a diagram illustrating an embodiment of the system 10 of the present disclosure. The system 10 could be embodied as a central processing unit 12 (processor) in communication with a database 14. The processor 12 could include, but is not limited to, a computer system, a server, a personal computer, a cloud computing device, a smart phone, or any other suitable device programmed to carry out the processes disclosed herein. The system 10 could determine SF-DOI for CVRP and implement the SF-DOI to accelerate CG optimization over ng-routes relaxed columns of a CVRP dataset obtained from the database 14 ¶0054 The system 10 determines the maximum value satisfying Equation 5 by considering all possible predecessor/successor pairs for u constructed from route l and respecting the order of route l. Then, the system 10 connects the predecessor to the successor directly instead of via u in the route created by removing u. Equation 14 below describes σ.sub.ul as optimization by denoting the customers/depots that include a route l in the order that they are visited in route l from first to last with: l={u.sub.0.sup.l, u.sub.1.sup.l, u.sub.2.sup.l . . . custom-character, u.sub.N+1.sup.l} where u.sub.0.sup.l, u.sub.N+1.sup.l respectively denote the starting depot and the ending depot Equation 14 ¶0069 FIG. 8 a diagram illustrating another embodiment of the system 200 of the present disclosure. In particular, FIG. 8 illustrates additional computer hardware and network components on which the system 200 could be implemented. The system 200 can include a plurality of computation servers 202a-202n having at least one processor and memory for executing the computer instructions and methods described above (which could be embodied as system code 16). The system 200 can also include a plurality of dataset storage servers 204a-204n for storing CVRP datasets. The computation servers 202a-202n and the dataset storage servers 204a-204n can communicate over a communication network 208):
receive information associated with the starting depot location, the ending depot location, and the items associated with the plurality of customers, wherein the information for each of the items comprises an item location and an integer demand indicating a size of the item (¶0020 A review of the minimum weight set cover formulation utilized in operations research along with the CG solution and its application to vehicle routing will now be described. A minimum weight set cover problem can be solved via a standard CG method. custom-character denotes a set of N∈Z.sub.+ items to be covered and the CG formulation includes a continuous variable θ.sub.l≥0 for every column l∈Ω where Ω is the set of all valid columns. In the standard cover formulation, a column can cover an item at most once. This can be relaxed when considering relaxed columns such as ng-routes, which can cover an item more than once. ¶0038 The formulation of CVRP as a minimum weight set cover problem based on several terms and variables will now be described with reference to Equation 9 below. The range {1, 2 . . . N} denotes a set of customers and 0, N+1 respectively denotes the starting and ending depots where N is a number of customers. Additionally, Ω denotes a set of feasible routes which are indexed by l, each of which starts at the starting depot and ends at the ending depot. A route is feasible if it contains no customer more than once and services no more demand that it has capacity. Ω can be described utilizing α.sub.ul∈{0,1} where α.sub.ul=1 if and only if route l services customer u and α.sub.ul=0 otherwise. If a route visits a given customer u, then that route services the entire demand of that customer u. The positive integer d.sub.u denotes a number of units of commodity that are demanded by customer u and the positive integer K denotes a capacity of a single vehicle. The capacity constraint for a vehicle route can be given by Equation 9 ¶0054 The system 10 determines the maximum value satisfying Equation 5 by considering all possible predecessor/successor pairs for u constructed from route l and respecting the order of route l. Then, the system 10 connects the predecessor to the successor directly instead of via u in the route created by removing u. Equation 14 below describes σ.sub.ul as optimization by denoting the customers/depots that include a route l in the order that they are visited in route l from first to last with: l={u.sub.0.sup.l, u.sub.1.sup.l, u.sub.2.sup.l . . . custom-character, u.sub.N+1.sup.l} where u.sub.0.sup.l, u.sub.N+1.sup.l respectively denote the starting depot and the ending depot Equation 14 ),
generate, based on the starting depot location, the ending depot location, the integer demand and the item location of each of the items, and a capacity of the vehicle, a vehicle routing problem, wherein a solution to the vehicle routing problem minimizes a distance of the route, wherein the route (a) starts at the starting depot location, (b) ends at the ending depot location, (c) visits each item location no more than once, and (d) services a capacity that does not exceed the capacity of the vehicle to carry items (¶0020 A review of the minimum weight set cover formulation utilized in operations research along with the CG solution and its application to vehicle routing will now be described. A minimum weight set cover problem can be solved via a standard CG method. custom-character denotes a set of N∈Z.sub.+ items to be covered and the CG formulation includes a continuous variable θ.sub.l≥0 for every column l∈Ω where Ω is the set of all valid columns. In the standard cover formulation, a column can cover an item at most once. This can be relaxed when considering relaxed columns such as ng-routes, which can cover an item more than once. ¶0038 The formulation of CVRP as a minimum weight set cover problem based on several terms and variables will now be described with reference to Equation 9 below. The range {1, 2 . . . N} denotes a set of customers and 0, N+1 respectively denotes the starting and ending depots where N is a number of customers. Additionally, Ω denotes a set of feasible routes which are indexed by l, each of which starts at the starting depot and ends at the ending depot. A route is feasible if it contains no customer more than once and services no more demand that it has capacity. Ω can be described utilizing α.sub.ul∈{0,1} where α.sub.ul=1 if and only if route l services customer u and α.sub.ul=0 otherwise. If a route visits a given customer u, then that route services the entire demand of that customer u. The positive integer d.sub.u denotes a number of units of commodity that are demanded by customer u and the positive integer K denotes a capacity of a single vehicle. The capacity constraint for a vehicle route can be given by Equation 9 ¶0021 Given the unscalability of enumerating the set Ω explicitly, CG considers a subset Ω.sub.R⊂Ω at any given time, and thus the optimization (referred to as the restricted master problem or RMP) obtains the solution of the problem (e.g., RMP(Ω.sub.R)) in Equation 1 but restricted to the columns in Ω.sub.R. Additionally, (α.sub.ucustom-character can denote the dual variables associated with the constraints Σ.sub.i∈Ωα.sub.ulθ.sub.i≥1 in problem RMP(Ω.sub.R). The reduced cost of a column l∈Ω\Ω.sub.R can be computed as c.sub.l=c.sub.l−custom-characterα.sub.uα.sub.ul. Therefore, problem RMP(Ω.sub.R) provides a proven optimal solution of Equation 1 if min{c.sub.l:l∈Ω\Ω.sub.R}≥0. It should be understood that determining negative reduced cost columns is application specific but is generally a small scale combinatorial optimization problem. Utilizing DOI to accelerate CG will now be described. DOI provide bounds on the dual variables, which provably do not remove all dual optimal solutions. DOI are utilized to decrease the search space over α, and hence accelerate optimization. Generally, DOI are applied to specific problems with specially tailored structure (e.g., the cutting stock problem). Recently, known approaches have demonstrated that DOI, such as S-DOI, F-DOI and SF-DOI, can be constructed for general classes of problems. These DOI are described in further detail below with respect to minimum weight set cover formulations),
split the vehicle routing problem into a master problem and a subproblem, wherein the master problem and the subproblem comprise constraints associated with the vehicle routing problem (¶0036 As mentioned earlier, pricing can be computationally challenging or NP-hard. To facilitate solving difficult pricing problems, a known approach performs CG optimization over a super-set of Ω, denoted as Ω.sup.+, for which pricing can be solved efficiently over. Accordingly, Ω can be replaced with Ω.sup.+ in Equations 1 and 8. The additional columns (Ω.sup.+ \Ω) can be referred to as relaxed. It should be understood that considering Ω.sup.+ instead of Ω can loosen the relaxation. However, if the members of (Ω.sup.+ \Ω) are inactive at the conclusion of CG, then the solution is equal to that corresponding to optimization over Ω. It is possible that the mechanism that generates DOI can be imperfect thereby yielding DOI that cut off all dual optimal solutions. However, the DOI can be intuitive and close to correct. Accordingly the DOI (e.g., relaxed DOI), while invalid, can accelerate optimization of a slightly weaker LP relaxation. Relaxed DOI can be removed, as needed, to ensure that the LP relaxation is not weakened. ¶0040 It should be understood that CVRP can be commonly attacked as a minimum weight set cover problem utilizing the formulation in Equation 1 and determining negative reduced cost columns can be attacked as an elementary resource constrained shortest path problem (ERCSPP) which is strongly NP-Hard. Specifically, the computational difficulty of the ERCSPP grows exponentially in custom-character. The difficulty of solving the ERCSPP is a consequence of enforcing the elementarity constraint during pricing which states that no item can be included more than once in a route. To circumvent the difficulty of enforcing elementarity, a known approach is to weaken the LP relaxation in Equation 1 to consider a superset of vehicle routes Ω, denoted as Ω.sup.+ and referred to as the set of ng-routes. The ng-route relaxation partially relaxes elementarity by enforced elementarity only between nearby customers),
compute, for the subproblem, a plurality of costs associated with distances between one or more item locations such that each of the distances is less than a first threshold, iteratively solve, using a column generation method with a local area route relaxation and based on the plurality of costs, the master problem and the subproblem to generate the solution comprising an optimized route that minimizes the distance of the route (¶0039 As described in further detail below in reference to Equation 10, c.sub.l denotes the cost of any route l ∈Ω. Additionally, T.sub.uvl=1 indicates that in a route l, a customer (or depot) u is followed immediately by customer (or depot) v and c.sub.uv denotes the associated cost which is the distance between u, v in metric space. In CVRP, c.sub.uv satisfies the triangle inequality. The cost c.sub.l is a fixed constant f∈custom-character.sub.0+ for instantiating the vehicle plus the total distance traveled on route l. The offset f corresponds to a dualized constraint providing an upper bound on a number of vehicles utilized. The range custom-character={1, 2, 3 . . . N} denotes the set of customers and custom-character.sup.+ denotes the union of the set custom-character, the starting depot 0 and ending depot N+1. Accordingly, c.sub.l is defined by Equation 10 ¶0052 In step 82, the system 10 determines a tighter variant of S-DOI. It should be understood that ρ.sub.uv for u, v in the context of vehicle routing is a maximum amount that the cost of a route can increase when replacing customer u with v. As mentioned earlier, (u, v)∈S if and only if the demand of a customer u is greater than or equal to the demand of a customer v (e.g., d.sub.u≥d.sub.v). Accordingly, ρ.sub.uv is given by Equation 13 It should be understood that by iterating over all possible pairs ∈+{0 . . . N+1}, the system 10 can efficiently evaluate ρ.sub.uv.), and
transmit, to the vehicle, the optimized route (¶0046 The code 16 could communicate with the database 14, which could be stored on the same computer system as the code 16, or on one or more other computer systems in communication with the code 16. The routing instructions generated by the automated vehicle routing system code 16 could be transmitted to one or more vehicle controllers (e.g., vehicle navigation system controller, etc.), such that the vehicle controllers can operate the vehicle in accordance with the route determined by the system code 16. The types of vehicles that can be controlled by the code 16 include, but are not limited to, cars, trucks, airplanes, unmanned aerial vehicles (UAVs), or any other type of vehicle that is capable of being controlled by a vehicle controller.),
wherein the column generation method comprises adding a column to the master problem as part of solving the subproblem, wherein the column corresponds to a particular route with a topological ordering of items serviced by a particular vehicle on the particular route, wherein the local area route relaxation comprises an ng-route relaxation, wherein the ng-route relaxation specifies that a first item location is followed by a second item location such that a distance between the first item location and the second item location is greater than a second threshold, wherein the local area route relaxation specifies that the distance between the first item location and the second item location is greater than a third threshold, and wherein the first threshold, second threshold and third threshold are positive numbers, and wherein the third threshold is greater than the second threshold (¶0006 This present disclosure relates to systems and methods for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns. In particular, the system determines valid smooth dual optimal inequalities (S-DOI) for a capacitated vehicle routing problem (CVRP) where optimization is performed over a set of valid columns. The system also determines valid flexible dual optimal inequalities (F-DOI) for the CVRP where optimization is performed over the set of valid columns. Then, the system adapts the S-DOI and the F-DOI to yield smooth and flexible dual optimal inequalities (SF-DOI) with respect to ng-route relaxed columns. The system utilizes the SF-DOI as relaxed DOI for the ng-route relaxed columns to accelerate column generation optimization over the ng-route relaxed columns ¶0019 In the CVRP, a column is valid if it (1) does not include a customer more than once (e.g., no cycles in the corresponding route), and (2) does not service more demand than the vehicle has capacity. The pricing problem for CVRP is an elementary resource constrained shortest path problem, which is strongly NP-hard. A super-set of the set of valid columns, referred to as ng-routes, can facilitate solving large CVRP instances. Ng-routes provide for making pricing tractable at the cost of a decrease in the tightness of the underlying expanded LP relaxation. The ng-route relaxation provides for a customer to be visited more than once in a route but precludes many short cycles localized in space. ¶0020 A review of the minimum weight set cover formulation utilized in operations research along with the CG solution and its application to vehicle routing will now be described. A minimum weight set cover problem can be solved via a standard CG method. custom-character denotes a set of N∈Z.sub.+ items to be covered and the CG formulation includes a continuous variable θ.sub.l≥0 for every column l∈Ω where Ω is the set of all valid columns. In the standard cover formulation, a column can cover an item at most once. This can be relaxed when considering relaxed columns such as ng-routes, which can cover an item more than once. In the context of CG, the set Ω is generally exponentially large with respect to N, and therefore it can be impractical to explicitly consider the entire set Ω during optimization. Accordingly, for every column l∈Ω and for every item u∈custom-character, α.sub.ul∈{0,1} can be a binary constant equal to 1 if l covers u and otherwise α.sub.ul=0. A cost c.sub.l can be associated with the column l via a non-decreasing function over α.sub.ul ∀u∈custom-character. The minimum weight set cover is given by Equation 1 ¶0065 Testing and processing results of the system 10 will now be described in relation to FIGS. 6 and 7. The system 10 tests the performance of the SF-DOI on four benchmark datasets including datasets A, B, P and E. Datasets A, B and P were introduced in 1995 and dataset E was introduced in 1969. The system 10 tests on instances with at most 50 customers and traversal costs are calculated as the Euclidean distance between customer locations rounded to the nearest integer. The system 10 solves the relaxed ng-routes problem where neighborhoods are set as the five nearest customers. Pricing amounts to solving an ng-route shortest path problem which is solved as a dynamic program. The system 10 evaluates DOI by the speedup in convergence they provide in comparison to non-stabilized CG. Algorithms are coded in MATLAB and CPLEX is utilized as the LP-solver.).
Although not explicitly taught by Haghani, Xu teaches in the analogous art of network support for dynamic vehicle routing:
receive information associated with the starting depot location and the ending depot location (¶0095 At act S115, the controller 800 receives a start and end point of a route. In some cases, the start point and end point may be included as part of the vehicle routing request. The start point and end point may define a desired starting and end location for the route. In some cases, only an end point may be received. The start point may be determined based on a location reported by the mobile device, e.g. received by the controller 800 in the probe data. ¶0105 In act S201, the controller 900 sends a vehicle routing request. The vehicle routing request may include a starting location and/or a destination for a route. The vehicle routing request may be sent to the server 125 of FIGS. 1 and 6.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani for the following reasons:
(1) a finding that there was some teaching, suggestion, or motivation, either in the references themselves or in the knowledge generally available to one of ordinary skill in the art, to modify the reference or to combine reference teachings, e.g. Haghani ¶0003 teaches that the CVRP is increasingly important for a variety of industries (e.g., electronic commerce) and applications thereof (e.g., supply chain management and shipping) where transportation can be a significant component of the cost of a product.;
(2) a finding that there was reasonable expectation of success since the only difference between the claimed invention and the prior art being the lack of actual combination of the elements in a single prior art reference, e.g. Haghani Abstract teaches systems and methods for automated vehicle routing using column generation optimization, and Xu Abstract teaches driving assistance features may be enabled or disabled based on the wireless performance data for the path segment where the vehicle route may be updated to continue to enable a set of the driving assistance features; and
(3) whatever additional findings based on the Graham factual inquiries may be necessary, in view of the facts of the case under consideration, to explain a conclusion of obviousness, e.g. Haghani at least the above cited paragraphs, and Xu at least the inclusively cited paragraphs.
Therefore, it would be obvious to one skilled in the art at the time of the invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani. The rationale to support a conclusion that the claim would have been obvious is that "a person of ordinary skill in the art would have been motivated to combine the prior art to achieve the claimed invention and whether there would have been a reasonable expectation of success in doing so." DyStar Textilfarben GmbH & Co. Deutschland KG v. C.H. Patrick Co., 464 F.3d 1356, 1360, 80 USPQ2d 1641, 1645 (Fed. Cir. 2006). See MPEP 2143(G).
Haghani teaches:
Claim 3. The system of claim 1, wherein the starting depot location and the ending depot location are collocated (¶0054 The system 10 determines the maximum value satisfying Equation 5 by considering all possible predecessor/successor pairs for u constructed from route l and respecting the order of route l. Then, the system 10 connects the predecessor to the successor directly instead of via u in the route created by removing u. Equation 14 below describes σ.sub.ul as optimization by denoting the customers/depots that include a route l in the order that they are visited in route l from first to last with: l={u.sub.0.sup.l, u.sub.1.sup.l, u.sub.2.sup.l . . . custom-character, u.sub.N+1.sup.l} where u.sub.0.sup.l, u.sub.N+1.sup.l respectively denote the starting depot and the ending depot Equation 14 ¶0065 Testing and processing results of the system 10 will now be described in relation to FIGS. 6 and 7. The system 10 tests the performance of the SF-DOI on four benchmark datasets including datasets A, B, P and E. Datasets A, B and P were introduced in 1995 and dataset E was introduced in 1969. The system 10 tests on instances with at most 50 customers and traversal costs are calculated as the Euclidean distance between customer locations rounded to the nearest integer. The system 10 solves the relaxed ng-routes problem where neighborhoods are set as the five nearest customers. Pricing amounts to solving an ng-route shortest path problem which is solved as a dynamic program. The system 10 evaluates DOI by the speedup in convergence they provide in comparison to non-stabilized CG. Algorithms are coded in MATLAB and CPLEX is utilized as the LP-solver).
Haghani teaches:
Claim 4. The system of claim 1, wherein the master problem is a linear programming problem and the subproblem is a pricing problem (¶0017 By way of background, the systems and methods of the present disclosure accelerate the CG solution to expanded LP relaxations utilizing DOI. Expanded LP relaxations are utilized to solve integer linear programs (ILPs) for which compact LP relaxations are loose. Compact LP relaxations contain a small number of variables whereas expanded LP relaxations contain a large number of variables (e.g., columns). An expanded LP relaxation is typically much tighter than a corresponding compact LP relaxation and permits efficient optimization of the corresponding ILP. CG can be utilized to solve expanded LP relaxations. Since the set of all feasible columns is large and cannot be easily enumerated, a sufficient set of columns is constructed iteratively utilizing CG. Pricing refers to the process of identifying negative reduced cost columns. Pricing is performed by solving a small scale combinatorial optimization problem parameterized by the dual solution of the expanded LP relaxation defined over the nascent set of columns ).
Haghani teaches:
Claim 5. The system of claim 4, wherein the pricing problem is an integer linear program (ILP) that is solved using Dijkstra's shortest-path algorithm (¶0017 By way of background, the systems and methods of the present disclosure accelerate the CG solution to expanded LP relaxations utilizing DOI. Expanded LP relaxations are utilized to solve integer linear programs (ILPs) for which compact LP relaxations are loose. Compact LP relaxations contain a small number of variables whereas expanded LP relaxations contain a large number of variables (e.g., columns). An expanded LP relaxation is typically much tighter than a corresponding compact LP relaxation and permits efficient optimization of the corresponding ILP. ¶0019 n the CVRP, a column is valid if it (1) does not include a customer more than once (e.g., no cycles in the corresponding route), and (2) does not service more demand than the vehicle has capacity. The pricing problem for CVRP is an elementary resource constrained shortest path problem, which is strongly NP-hard. A super-set of the set of valid columns, referred to as ng-routes, can facilitate solving large CVRP instances. Ng-routes provide for making pricing tractable at the cost of a decrease in the tightness of the underlying expanded LP relaxation.).
Although not explicitly taught by Haghani, Xu teaches in the analogous art of network support for dynamic vehicle routing:
Dijkstra's shortest-path algorithm (¶0068 Different methods may be used to plan which path segments L1-L12 to include in a route 403. For example, Dijkstra's algorithm, A* algorithm, Dynamic Programming algorithm, Bellman-Ford algorithm, and others may be used to plan the route. In one example according to Dijkstra's algorithm, planning a route may start at a start node. For example, the node 401 with cell 1 may be the start node. The other nodes 401 may be marked as unvisited and included in an unvisited set of nodes 401.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani for the following reasons:
(1) a finding that there was some teaching, suggestion, or motivation, either in the references themselves or in the knowledge generally available to one of ordinary skill in the art, to modify the reference or to combine reference teachings, e.g. Haghani ¶0003 teaches that the CVRP is increasingly important for a variety of industries (e.g., electronic commerce) and applications thereof (e.g., supply chain management and shipping) where transportation can be a significant component of the cost of a product.;
(2) a finding that there was reasonable expectation of success since the only difference between the claimed invention and the prior art being the lack of actual combination of the elements in a single prior art reference, e.g. Haghani Abstract teaches systems and methods for automated vehicle routing using column generation optimization, and Xu Abstract teaches driving assistance features may be enabled or disabled based on the wireless performance data for the path segment where the vehicle route may be updated to continue to enable a set of the driving assistance features; and
(3) whatever additional findings based on the Graham factual inquiries may be necessary, in view of the facts of the case under consideration, to explain a conclusion of obviousness, e.g. Haghani at least the above cited paragraphs, and Xu at least the inclusively cited paragraphs.
Therefore, it would be obvious to one skilled in the art at the time of the invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani. The rationale to support a conclusion that the claim would have been obvious is that "a person of ordinary skill in the art would have been motivated to combine the prior art to achieve the claimed invention and whether there would have been a reasonable expectation of success in doing so." DyStar Textilfarben GmbH & Co. Deutschland KG v. C.H. Patrick Co., 464 F.3d 1356, 1360, 80 USPQ2d 1641, 1645 (Fed. Cir. 2006). See MPEP 2143(G).
Haghani teaches:
Claim 6. The system of claim 1, wherein the at least one processor is part of a cloud computing infrastructure (¶0045 Turning to the drawings, FIG. 1 is a diagram illustrating an embodiment of the system 10 of the present disclosure. The system 10 could be embodied as a central processing unit 12 (processor) in communication with a database 14. The processor 12 could include, but is not limited to, a computer system, a server, a personal computer, a cloud computing device, a smart phone, or any other suitable device programmed to carry out the processes disclosed herein. ¶0046 the code 16 could be distributed across multiple computer systems in communication with each other over a communications network, and/or stored and executed on a cloud computing platform and remotely accessed by a computer system in communication with the cloud platform. The code 16 could communicate with the database 14, which could be stored on the same computer system as the code 16, or on one or more other computer systems in communication with the code 16.).
Haghani teaches:
Claim 7. The system of claim 6, wherein the at least one processor comprises a first processor that is used to solve the master problem and a second processor that is used to solve the subproblem (¶0045 Turning to the drawings, FIG. 1 is a diagram illustrating an embodiment of the system 10 of the present disclosure. The system 10 could be embodied as a central processing unit 12 (processor) in communication with a database 14. The processor 12 could include, but is not limited to, a computer system, a server, a personal computer, a cloud computing device, a smart phone, or any other suitable device programmed to carry out the processes disclosed herein. The system 10 could determine SF-DOI for CVRP and implement the SF-DOI to accelerate CG optimization over ng-routes relaxed columns of a CVRP dataset obtained from the database 14 ¶0069 FIG. 8 a diagram illustrating another embodiment of the system 200 of the present disclosure. In particular, FIG. 8 illustrates additional computer hardware and network components on which the system 200 could be implemented. The system 200 can include a plurality of computation servers 202a-202n having at least one processor and memory for executing the computer instructions and methods described above (which could be embodied as system code 16). The system 200 can also include a plurality of dataset storage servers 204a-204n for storing CVRP datasets. The computation servers 202a-202n and the dataset storage servers 204a-204n can communicate over a communication network 208.).
As per claims 8,10-11 and 12,15-16, the method and method tracks the system of claims 1,4,5 and 1,4,5, respectively, resulting in substantially similar limitations. The same cited prior art and rationale of claims 1,4,5 and 1,4,5 are applied to claims 8,10-11 and 12,15-16, respectively. Additional limitations from claims 8 and 12 are as follows, however:
Haghani teaches:
[from Claim 8] a warehouse, the plurality of robots (¶0018 A known approach adapts a flexible DOI (F-DOI) framework to describe rebates for over-including customers. This approach observes that similar customers (e.g., with regards to spatial position and demand) should be associated with similar dual values resulting in smooth DOI (S-DOI). In this approach, the combination of S-DOI and F-DOI is referred to as SF-DOI and is tested on a single source capacitated facility location. SF-DOI can provide up to 130 times speed up for the problems considered by the aforementioned approach while provably not changing the final solution. ¶0038 he range {1, 2 . . . N} denotes a set of customers and 0, N+1 respectively denotes the starting and ending depots where N is a number of customers. Additionally, Ω denotes a set of feasible routes which are indexed by l, each of which starts at the starting depot and ends at the ending depot. A route is feasible if it contains no customer more than once and services no more demand that it has capacity. Ω can be described utilizing α.sub.ul∈{0,1} where α.sub.ul=1 if and only if route l services customer u and α.sub.ul=0 otherwis ¶0046 The code 16 could communicate with the database 14, which could be stored on the same computer system as the code 16, or on one or more other computer systems in communication with the code 16. The routing instructions generated by the automated vehicle routing system code 16 could be transmitted to one or more vehicle controllers (e.g., vehicle navigation system controller, etc.), such that the vehicle controllers can operate the vehicle in accordance with the route determined by the system code 16. The types of vehicles that can be controlled by the code 16 include, but are not limited to, cars, trucks, airplanes, unmanned aerial vehicles (UAVs), or any other type of vehicle that is capable of being controlled by a vehicle controller.).
Haghani teaches:
[from Claim 12] transmitting, to each of the plurality of autonomous vehicles, the corresponding optimized route, wherein the vehicle routing problem comprises a master problem and a subproblem, the master problem and the subproblem comprising constraints associated with the vehicle routing problem (¶0006 This present disclosure relates to systems and methods for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns. In particular, the system determines valid smooth dual optimal inequalities (S-DOI) for a capacitated vehicle routing problem (CVRP) where optimization is performed over a set of valid columns. The system also determines valid flexible dual optimal inequalities (F-DOI) for the CVRP where optimization is performed over the set of valid columns. Then, the system adapts the S-DOI and the F-DOI to yield smooth and flexible dual optimal inequalities (SF-DOI) with respect to ng-route relaxed columns. The system utilizes the SF-DOI as relaxed DOI for the ng-route relaxed columns to accelerate column generation optimization over the ng-route relaxed columns. ¶0021 Given the unscalability of enumerating the set Ω explicitly, CG considers a subset Ω.sub.R⊂Ω at any given time, and thus the optimization (referred to as the restricted master problem or RMP) obtains the solution of the problem (e.g., RMP(Ω.sub.R)) in Equation 1 but restricted to the columns in Ω.sub.R. Additionally, (α.sub.ucustom-character can denote the dual variables associated with the constraints Σ.sub.i∈Ωα.sub.ulθ.sub.i≥1 in problem RMP(Ω.sub.R). The reduced cost of a column l∈Ω\Ω.sub.R can be computed as c.sub.l=c.sub.l−custom-characterα.sub.uα.sub.ul. Therefore, problem RMP(Ω.sub.R) provides a proven optimal solution of Equation 1 if min{c.sub.l:l∈Ω\Ω.sub.R}≥0. It should be understood that determining negative reduced cost columns is application specific but is generally a small scale combinatorial optimization problem).
Although not explicitly taught by Haghani, Xu teaches in the analogous art of network support for dynamic vehicle routing:
Claim 13. The method of claim 12, wherein at least one of the plurality of autonomous vehicle is operating in a Society of Automotive Engineers (SAE) Level 4 (L4) automation mode (¶0027 The society of automotive engineers (SAE) sorts driver assistance features into different levels, ranging from 0 to 5. ¶0032 Level 4: Similar automated control as in level 3, but no driver attention is required for safety. For example, the driver may safely go to sleep or leave the driver's seat. Level 4 may be referred to as “mind off” or “driverless.” Self-driving in level 4 may be supported only in limited spatial areas (e.g. within geofenced areas) or under special circumstances, like traffic jams. Outside of these areas or circumstances, the vehicle may safely abort the trip (e.g. park the car) if the driver does not retake control.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani for the following reasons:
(1) a finding that there was some teaching, suggestion, or motivation, either in the references themselves or in the knowledge generally available to one of ordinary skill in the art, to modify the reference or to combine reference teachings, e.g. Haghani ¶0003 teaches that the CVRP is increasingly important for a variety of industries (e.g., electronic commerce) and applications thereof (e.g., supply chain management and shipping) where transportation can be a significant component of the cost of a product.;
(2) a finding that there was reasonable expectation of success since the only difference between the claimed invention and the prior art being the lack of actual combination of the elements in a single prior art reference, e.g. Haghani Abstract teaches systems and methods for automated vehicle routing using column generation optimization, and Xu Abstract teaches driving assistance features may be enabled or disabled based on the wireless performance data for the path segment where the vehicle route may be updated to continue to enable a set of the driving assistance features; and
(3) whatever additional findings based on the Graham factual inquiries may be necessary, in view of the facts of the case under consideration, to explain a conclusion of obviousness, e.g. Haghani at least the above cited paragraphs, and Xu at least the inclusively cited paragraphs.
Therefore, it would be obvious to one skilled in the art at the time of the invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani. The rationale to support a conclusion that the claim would have been obvious is that "a person of ordinary skill in the art would have been motivated to combine the prior art to achieve the claimed invention and whether there would have been a reasonable expectation of success in doing so." DyStar Textilfarben GmbH & Co. Deutschland KG v. C.H. Patrick Co., 464 F.3d 1356, 1360, 80 USPQ2d 1641, 1645 (Fed. Cir. 2006). See MPEP 2143(G).
Haghani teaches:
Claim 17. The method of claim 16, wherein a lowest-cost component path determined by the Dijkstra's shortest-path algorithm is computed only once prior to iteratively solving the vehicle routing problem using the column generation method with the local area route relaxation (¶0017 By way of background, the systems and methods of the present disclosure accelerate the CG solution to expanded LP relaxations utilizing DOI. Expanded LP relaxations are utilized to solve integer linear programs (ILPs) for which compact LP relaxations are loose. Compact LP relaxations contain a small number of variables whereas expanded LP relaxations contain a large number of variables (e.g., columns). An expanded LP relaxation is typically much tighter than a corresponding compact LP relaxation and permits efficient optimization of the corresponding ILP. ¶0019 n the CVRP, a column is valid if it (1) does not include a customer more than once (e.g., no cycles in the corresponding route), and (2) does not service more demand than the vehicle has capacity. The pricing problem for CVRP is an elementary resource constrained shortest path problem, which is strongly NP-hard. A super-set of the set of valid columns, referred to as ng-routes, can facilitate solving large CVRP instances. Ng-routes provide for making pricing tractable at the cost of a decrease in the tightness of the underlying expanded LP relaxation.).
Although not explicitly taught by Haghani, Xu teaches in the analogous art of network support for dynamic vehicle routing:
Dijkstra's shortest-path algorithm (¶0068 Different methods may be used to plan which path segments L1-L12 to include in a route 403. For example, Dijkstra's algorithm, A* algorithm, Dynamic Programming algorithm, Bellman-Ford algorithm, and others may be used to plan the route. In one example according to Dijkstra's algorithm, planning a route may start at a start node. For example, the node 401 with cell 1 may be the start node. The other nodes 401 may be marked as unvisited and included in an unvisited set of nodes 401.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani for the following reasons:
(1) a finding that there was some teaching, suggestion, or motivation, either in the references themselves or in the knowledge generally available to one of ordinary skill in the art, to modify the reference or to combine reference teachings, e.g. Haghani ¶0003 teaches that the CVRP is increasingly important for a variety of industries (e.g., electronic commerce) and applications thereof (e.g., supply chain management and shipping) where transportation can be a significant component of the cost of a product.;
(2) a finding that there was reasonable expectation of success since the only difference between the claimed invention and the prior art being the lack of actual combination of the elements in a single prior art reference, e.g. Haghani Abstract teaches systems and methods for automated vehicle routing using column generation optimization, and Xu Abstract teaches driving assistance features may be enabled or disabled based on the wireless performance data for the path segment where the vehicle route may be updated to continue to enable a set of the driving assistance features; and
(3) whatever additional findings based on the Graham factual inquiries may be necessary, in view of the facts of the case under consideration, to explain a conclusion of obviousness, e.g. Haghani at least the above cited paragraphs, and Xu at least the inclusively cited paragraphs.
Therefore, it would be obvious to one skilled in the art at the time of the invention to combine the network support for dynamic vehicle routing of Xu with the system for systems for automated vehicle routing using relaxed dual optimal inequalities for relaxed columns of Haghani. The rationale to support a conclusion that the claim would have been obvious is that "a person of ordinary skill in the art would have been motivated to combine the prior art to achieve the claimed invention and whether there would have been a reasonable expectation of success in doing so." DyStar Textilfarben GmbH & Co. Deutschland KG v. C.H. Patrick Co., 464 F.3d 1356, 1360, 80 USPQ2d 1641, 1645 (Fed. Cir. 2006). See MPEP 2143(G).
As per claims 18 and 19, the system and method tracks the method of claims 17 and 17 respectively, resulting in substantially similar limitations. The same cited prior art and rationale of claims 17 and 17 are applied to claims 18 and 19, respectively.
Conclusion
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).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KURTIS GILLS whose telephone number is (571) 270-3315. The examiner can normally be reached on M-F, 8am-5pm EST.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jerry O’Connor can be reached on 571-272-6787. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/KURTIS GILLS/Primary Examiner, Art Unit 3624