DETAILED ACTION
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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55. Priority is being given to 07/15/2022.
Status of Claims
This action is in reply to the amendments filed on 07/28/2025.
Claims 1, 3-8, 10-15, and 17-21 are currently pending and have been examined.
Claims 1, 3, 4, 8, 10, 15, and 17 are amended.
Claims 2, 9, and 16 are cancelled.
Claims 1, 3-8, 10-15, and 17-21 are currently rejected.
This action is made FINAL.
Response to Arguments
Applicant’s arguments filed 07/28/2025 have been fully considered but they are not persuasive.
Applicant’s arguments with regards to the art rejections have been considered and are not persuasive. Applicant argues for 5 distinguishing features of the amended claims which the examiner will respond to individually.
Regarding distinguishing feature 1, applicant argues that Kokiopoulou reduces the dimensionality of the data and is not equivalent to projection onto an orthogonal line. Projecting 2D data onto an orthogonal line results in a 1D line which is a reduction of dimensionality of the data. Li teaches projecting the destination data to an orthogonal line representing the road and Kokiopoulou teaches the ability to mathematically represent this projection/reduction to the explicitly stated benefit of improving optimization by allowing the system to focus on the preserved property as a result of the projection/reduction. Therefore it would have been obvious to apply the teachings of Li and Kokiopoulou to the teachings of Kannan to teach the argued limitation.
Regarding distinguishing feature 2, applicant argues that the claimed invention does not reduce the dimensionality of the data. This is not persuasive because projecting 2D data onto a 1D line involved a reduction of dimensionality where the focus is on the ordering of the reduced destinations in the ability to reallocate them. Therefore examiner does not find the arguments that the art teaches away from the claims persuasive.
Regarding distinguishing feature 3, applicant argues that the art of record fails to teach the amended limitations which are addressed in the updated rejections below.
Regarding distinguishing feature 4, applicant argues that the art of record fails to teach the amended limitations which are addressed in the updated rejections below.
Regarding distinguishing feature 5, applicant argues that the art of record fails to teach the amended limitations which are addressed in the updated rejections below.
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 (i.e., changing from AIA to pre-AIA ) 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, 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 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.
Claim(s) 1, 3-5, 8, 10-12, 15, and 17-19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Kannan (US 2021/0004763), herein Kannan in view of Li et. al. (CN 105701204), herein Li, Kokiopoulou et. al. (Orthogonal Neighborhood Preserving Projections: A Projection-Based Dimensionality Reduction Technique - NPL), and Singh et. al. (US 2022/0156693), herein Singh.
Regarding claim 1:
Kannan teaches:
A method (an object of the present disclosure is to provide a novel method and system for vehicular fleet routing [0007]) for optimizing vehicle route overlap in vehicle routing plans (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]), the method comprising:
storing in a non-transitory memory medium (As used herein, “memory unit”, “storage unit” and/or “memory” refers to a machine or computer-readable medium including any mechanism for storing information in a form readable by a computer or similar machine. For example, a computer-readable medium includes read-only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices or other types of machine-accessible storage media. Any of the methods herein can be implemented in one or more computer-readable media comprising computer-executable instructions that, when executed, cause a computing system to perform the method. [0030]) a vehicle routing plan including a plurality of vehicle routes (The invention aims to achieve efficient planning of routes for servicing a set of locations at specified time windows from a given hub by a certain number of vehicles. [0022]), the vehicle routing plan being optimized according to at least one optimization criterion other than an overlap criterion (the present disclosure in order to provide a solution relating to optimal routing of shipments, takes into consideration a number of cost parameters associated with outliers on routes, uneven distribution of shipments across the vehicles and non-compactness of routes aside from constraints associated with capacity of the vehicles and arrivals at customer locations within their respective time-windows. [0022]), each of the plurality of vehicle routes including a plurality of destination nodes for a respective vehicle () and satisfying capacity (constraints associated with capacity of the vehicles [0022]) and timing parameters (and arrivals at customer locations within their respective time-windows [0022]) for the respective vehicle to serve the plurality of destination nodes (an initial set of routes between the hub and the set of locations [0037]);
computing a plurality of overlap metrics (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]) of the plurality of vehicle routes (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed[0044]; Furthermore, in one more instance, the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids. Further, said one or more route pairs are identified for switching/swapping the one or more locations between them. Thereafter, the processing unit [104] is configured to assign the one or more route pairs, a probability inversely proportional to square root of the rank (i.e. of the distance), to further determine the route pair based on that probability. Once the route pair is determined, the processing unit [104] is thereafter configured to identify one or more customer segments at random, both in terms of their starting index and their length with a constraint that the number of customers does not exceed a threshold. [0046]);
selecting a first vehicle route and a second vehicle route of the plurality of vehicle routes (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed. Also, in an instance the selection of route-pair and the one or more customers to be removed is further based on a reduction or elimination of a total capacity breach. [0078]) using the plurality of overlap metrics (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed[0044]; Furthermore, in one more instance, the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids. Further, said one or more route pairs are identified for switching/swapping the one or more locations between them. Thereafter, the processing unit [104] is configured to assign the one or more route pairs, a probability inversely proportional to square root of the rank (i.e. of the distance), to further determine the route pair based on that probability. Once the route pair is determined, the processing unit [104] is thereafter configured to identify one or more customer segments at random, both in terms of their starting index and their length with a constraint that the number of customers does not exceed a threshold. [0046]);
reallocating the destination nodes of the first vehicle route and the second vehicle route to a first new route and a second new route (see figs. 4a-4c showing altering of routes 1 and 2; the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed. Also, in an instance the selection of route-pair and the one or more customers to be removed is further based on a reduction or elimination of a total capacity breach. [0076]) using [an ordered projection] of the destination nodes onto a line passing through the first vehicle route and the second vehicle route (the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids [0046]), the first new route satisfying first capacity and timing parameters of the first vehicle route, the second new route satisfying second capacity and timing parameters of the first vehicle route (the present disclosure in order to provide a solution relating to optimal routing of shipments, takes into consideration a number of cost parameters associated with outliers on routes, uneven distribution of shipments across the vehicles and non-compactness of routes aside from constraints associated with capacity of the vehicles and arrivals at customer locations within their respective time-windows. [0022])
wherein the reallocating (the method in order to exchange/reorder one or more locations/customers between a pair of routes, encompasses optimizing each route independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered. [0091]) comprises:
allocating the destination nodes of the first vehicle route and the second vehicle route (Furthermore, the processing unit [104] in order to modify, iteratively, the determined initial set of routes is further configured to reconfigure an ordering of locations on the route. For instance, the processing unit [104] is configured to exchange/reorder one or more locations/customers between a pair of routes, wherein each of these routes is further optimized independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered. [0053]), in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route (In one implementation, the two customer segments, one in each route, are determined by also considering capacity constraints requiring that the number of customers in each route is less than a threshold. Thereafter, the processing unit [104] is further configured to analyze an impact of a customer segment swap on an overall cost including cost associated with time-window violations. Further, the customer segment swaps iterates over all combinations of traversals of the customer segment pair. [0045]); and
allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route (In one implementation, the two customer segments, one in each route, are determined by also considering capacity constraints requiring that the number of customers in each route is less than a threshold. Thereafter, the processing unit [104] is further configured to analyze an impact of a customer segment swap on an overall cost including cost associated with time-window violations. Further, the customer segment swaps iterates over all combinations of traversals of the customer segment pair. [0045]);
[constructing] the line to intersect a first centroid of the first vehicle route and a second centroid of the second vehicle route (the method encompasses identifying via the processing unit [104], one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids [0080]);
determining an overlap-optimized (to reduce regions having overlapping routes [0007]) vehicle routing plan including the first new route and the second new route (the FIG. 4 (c) indicates a reinsertion of the three identified customers/locations i.e. A, B and C into the routes based on an associated minimum insertion cost. [0088]); and
providing the overlap-optimized vehicle routing plan to control dispatch of a plurality of vehicles (the present disclosure provides systems and methods for vehicular fleet routing that provides better route optimization during one or more shipment deliveries and shipment scheduling in heterogeneous hubs [0100]; examiner notes that the method would inherently send the final routes out to the vehicles.).
Kannan does not explicitly teach, however Li teaches:
using an ordered projection of the destination nodes (The specific solution is as follows: for the current road line (road topological line) according to a certain width to generate the road line of the buffer area, judging which points into the buffer to find the (road line) boundary, calculate the boundary point on the road line of the projection point (the boundary point of the road line as vertical to the road line, the intersection point is the projection point), and establishing a boundary point (original point) one-to-one corresponding relation with the projection point (as shown in FIG. 8). the buffer area is an influence range or geographic space target service range, specifically refers to a polygon with a certain width around the point, line and plane entity established. calculated (located) on the road line each projection point along the passage route to starting point of road line length according to the length of said projection point sequencing, thereby forming ordered projection point set. [page 4]) onto a line passing through the first vehicle route and the second vehicle route (examiner notes that it would be obvious to use the line between the route centroids as determined in Kannan as the projection line for the ordered projection as taught by Li),
wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line (see at least fig. 8 showing the points being projected to the line in an orthogonal direction.)
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan to include the teachings as taught by Li with a reasonable expectation of success. Kannan teaches the ability to optimize the routing of multiple vehicles by reallotting the points between two routes. However, Kannan does not explicitly teach that using an ordered projection is the method used to reallocate the points. However, ordered projections is a known mathematical concept that would be known to one having ordinary skill in the art and Kannan does teach the ability to calculate the line between the centroids of the two routes. Therefore it would have been obvious to apply the use of an ordered projection as taught by Li to arrive at the claimed invention. Li is in the same field of endeavor of navigation routing and would be applying one of a finite amount of methods for optimizing the ordering of navigation routing which would be well within the skill of one having ordinary skill in the art at the time of filing.
Kannan in view of Li does not explicitly teach, however Kokiopoulou teaches:
an ordered projection of the destination nodes (The proposed method, named orthogonal Neighborhood Preserving Projections (ONPP) [3], projects the high-dimensional data samples on a lower dimensional space by means of a linear transformation V [page 2143]) onto a line passing through the first vehicle route and the second vehicle route (Given a data set X ¼ ½x1; x2; ... ; xn 2 Rmn, the goal of dimensionality reduction is to produce a set Y , which is an accurate representation of X, but which is of dimension d, with d - m. This can be achieved in different ways by selecting the type of the reduced dimension Y and the desirable properties to be preserved. By type, we mean whether we require that Y be simply a low-rank representation of X or a data set in a vector space with fewer dimensions. [page 2144]; examiner notes that it would have been obvious for one having ordinary skill in the art to have chosen the line connecting the route centroids as taught in Kannan as the line to perform the projection onto as taught by Kokiopoulou. When looking to find an optimal order for the routes, one would be motivated to use a projection line that best corresponds to provide the best spread of the data, which would occur via the line connecting the centroids. This also amounts to routine optimization because given the finite amount of orientations to use for the projection line it would have been obvious to find this orientation through routine experimentation.)
constructing the line to intersect a first centroid of the first vehicle route and a second centroid of the second vehicle route (Given a data set X ¼ ½x1; x2; ... ; xn 2 Rmn, the goal of dimensionality reduction is to produce a set Y , which is an accurate representation of X, but which is of dimension d, with d - m. This can be achieved in different ways by selecting the type of the reduced dimension Y and the desirable properties to be preserved. By type, we mean whether we require that Y be simply a low-rank representation of X or a data set in a vector space with fewer dimensions. [page 2144]);
determining projections of the destination nodes of the first vehicle route and the second vehicle route onto the line (Projection-based techniques consist of replacing the original data X by a matrix of the form Y ¼ V >X; where V 2 Rmd: ð1Þ Thus, each vector xi is replaced by yi ¼ V >xi, a member of the d-dimensional space Rd. If V is a unitary matrix, then Y represents the orthogonal projection of X into the V -space [page 2144]), wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line (the goal of dimensionality reduction is to produce a set Y, which is an accurate representation of X but which is of a dimension d, with d<<m. [page 2144]; examiner notes that reducing dimensionality of the data does not reduce the amount of data points, just the dimension that represents each data point (i.e. projection).);
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li to include the teachings as taught by Kokiopoulou with a reasonable expectation of success. Kokiopoulou teaches “The goal of dimensionality reduction is to map the high-dimensional samples to a lower dimensional space such that certain properties are preserved. Usually, the property that is preserved is quantified by an objective function and the dimensionality reduction problem is formulated as an optimization problem [Kokiopoulou, page 2143]” and “a linear dimensionality reduction technique is advocated, which preserves the intrinsic geometry of the local neighborhoods. The proposed method, named Orthogonal Neighborhood Preserving Projections (ONPP) [3], projects the high-dimensional data samples on a lower dimensional space by means of a linear transformation V [Kokiopoulou, page 2143]”.
Singh also teaches:
allocating the destination nodes of the first vehicle route and the second vehicle route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]); and
allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]);
Kannan in view of Li and Kokiopoulou does not explicitly teach, however Singh teaches:
determining a sequential order of the destination nodes of the first vehicle route and the second vehicle route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), according to an order of the projections of the destination nodes onto the line (a dynamic program is implemented to permute the customers in order to find the sequence of customers on the route that will optimize the route cost [0101]; examiner notes that applying the teachings of Li and Kokiopoulou as shown above it would have been obvious to have applied the projection technique with the teachings of Singh to arrive at the claimed invention.);
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li and Kokiopoulou to include the teachings as taught by Singh with a reasonable expectation of success. Singh teaches the benefits of “the exemplary optimized cargo transportation solution development systems and methods described in this application are operable to optimally assign trucks to specific routes, determine optimal truck routes, and minimize transportation costs [Singh, 0007]”.
Regarding claim 3:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 2, upon which this claim is dependent.
Kannan further teaches:
wherein the reallocating (the method in order to exchange/reorder one or more locations/customers between a pair of routes, encompasses optimizing each route independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered [0091]) comprises:
repeating the allocating with the line rotated by an angle (examiner notes that Kannan teaches repeating the allocation process even when it fails to create a satisfactory route and in light of the projection of the points onto the line as taught in claim 1, it would be obvious to rotate the line in order to change a variable in order to rerun the allocation. The projection reduces the 2D map into a 1D line and in order to be able to retry the allocation the 1D line needs to be changed, which is only possible of the projection is redone around a different angle.) if the allocating does not successfully allocate all of the destinations nodes (the system [100] is also configured to provide route optimization in various modes where a route capacity constraint may be violated at an intermediate stage in order to explore the solution space more thoroughly, but these capacity constraints are restored via the system [100] while implementing the features of the present disclosure.); and
adopting the first candidate route as the first new route and the second candidate route as the second new route if the allocating accounts for all of the destinations nodes (Next, at step [212], the method comprises selecting, via the processing unit [104], a route modification criteria based on one or more iterations. Further, at step [214], the method comprises arriving, via the processing unit [104], at a final set of routes based on a stopping criteria. [0096-0097]; the processing unit [104] is also configured to select, a route modification criteria based on one or more iterations. Also, thereafter, the processing unit [104] is further configured to arrive, at a final set of routes based on a stopping criteria [0059]).
Singh further teaches:
if the allocating does not successfully allocate all of the destinations nodes (With respect to optimizing cargo transportation solution development using ACO, each ant may be equated with a fleet of trucks. When the ant (trucks) initially leaves the nest (origin) it represents a single one of the trucks. When the ant returns and then leaves the origin again, the ant represents a new truck. The scope of the ant ends whenever either all packages are delivered or all truck capacity is filled. In the searching process associated with the FrO program, if a previous truck in the ant colony (truck fleet) has already delivered a package, or the desired location cannot be reached, the node is stored in an infeasible or tabu list. As indicated below, the exemplary FrO program uses the notation Tabu.sup.k to store nodes that have already been visited by ant (truck) k and nodes that violate constraints so that they are removed from further consideration. [0065]); and
Regarding claim 4:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 1, upon which this claim is dependent.
Kannan further teaches:
repeating the selecting and the reallocating for additional pairs of vehicle routes, wherein the determining the overlap-optimized vehicle routing plan further includes additional pairs of new routes determined by the repeating the reallocating for the additional pairs of vehicle routes (The method further comprises modifying, iteratively, the determined initial set of routes based on a combination of multiple operations that reconfigure the routes to arrive at a final configuration of routes. [abstract]).
Regarding claim 5:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 4, upon which this claim is dependent.
Kannan further teaches:
wherein the repeating is performed (The method further comprises modifying, iteratively, the determined initial set of routes based on a combination of multiple operations that reconfigure the routes to arrive at a final configuration of routes. [abstract]) to account for all vehicle routes having an overlap metric satisfying an overlap optimization criterion (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]).
Regarding claim 8:
Kannan teaches:
A system (an object of the present disclosure is to provide a novel method and system for vehicular fleet routing [0007]) for optimizing vehicle route overlap in vehicle routing plans (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]), the system comprising:
a non-transitory memory medium configured to store instructions (As used herein, “memory unit”, “storage unit” and/or “memory” refers to a machine or computer-readable medium including any mechanism for storing information in a form readable by a computer or similar machine. For example, a computer-readable medium includes read-only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices or other types of machine-accessible storage media. Any of the methods herein can be implemented in one or more computer-readable media comprising computer-executable instructions that, when executed, cause a computing system to perform the method. [0030]) for processing a vehicle routing plan including a plurality of vehicle routes (The invention aims to achieve efficient planning of routes for servicing a set of locations at specified time windows from a given hub by a certain number of vehicles. [0022]), the vehicle routing plan being optimized according to at least one optimization criterion other than an overlap criterion (the present disclosure in order to provide a solution relating to optimal routing of shipments, takes into consideration a number of cost parameters associated with outliers on routes, uneven distribution of shipments across the vehicles and non-compactness of routes aside from constraints associated with capacity of the vehicles and arrivals at customer locations within their respective time-windows. [0022]), each of the plurality of vehicle routes including a plurality of destination nodes for a respective vehicle () and satisfying capacity (constraints associated with capacity of the vehicles [0022]) and timing parameters (and arrivals at customer locations within their respective time-windows [0022]) for the respective vehicle to serve the plurality of destination nodes (an initial set of routes between the hub and the set of locations [0037]);
one or more processors configured to execute the instructions stored in the non-transitory memory medium (The system [100] comprises, at least one transceiver unit [102], at least one processing unit [104] and at least one storage unit [106] [0033]) to:
compute a plurality of overlap metrics (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]) of the plurality of vehicle routes (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed[0044]; Furthermore, in one more instance, the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids. Further, said one or more route pairs are identified for switching/swapping the one or more locations between them. Thereafter, the processing unit [104] is configured to assign the one or more route pairs, a probability inversely proportional to square root of the rank (i.e. of the distance), to further determine the route pair based on that probability. Once the route pair is determined, the processing unit [104] is thereafter configured to identify one or more customer segments at random, both in terms of their starting index and their length with a constraint that the number of customers does not exceed a threshold. [0046]);
select a first vehicle route and a second vehicle route of the plurality of vehicle routes (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed. Also, in an instance the selection of route-pair and the one or more customers to be removed is further based on a reduction or elimination of a total capacity breach. [0078]) using the plurality of overlap metrics (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed[0044]; Furthermore, in one more instance, the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids. Further, said one or more route pairs are identified for switching/swapping the one or more locations between them. Thereafter, the processing unit [104] is configured to assign the one or more route pairs, a probability inversely proportional to square root of the rank (i.e. of the distance), to further determine the route pair based on that probability. Once the route pair is determined, the processing unit [104] is thereafter configured to identify one or more customer segments at random, both in terms of their starting index and their length with a constraint that the number of customers does not exceed a threshold. [0046]);
reallocating the destination nodes of the first vehicle route and the second vehicle route to a first new route and a second new route (see figs. 4a-4c showing altering of routes 1 and 2; the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed. Also, in an instance the selection of route-pair and the one or more customers to be removed is further based on a reduction or elimination of a total capacity breach. [0076]) using [an ordered projection] of the destination nodes onto a line passing through the first vehicle route and the second vehicle route (the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids [0046]), the first new route satisfying first capacity and timing parameters of the first vehicle route, the second new route satisfying second capacity and timing parameters of the first vehicle route (the present disclosure in order to provide a solution relating to optimal routing of shipments, takes into consideration a number of cost parameters associated with outliers on routes, uneven distribution of shipments across the vehicles and non-compactness of routes aside from constraints associated with capacity of the vehicles and arrivals at customer locations within their respective time-windows. [0022])
wherein the reallocating (the method in order to exchange/reorder one or more locations/customers between a pair of routes, encompasses optimizing each route independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered. [0091]) comprises:
allocating the destination nodes of the first vehicle route and the second vehicle route (Furthermore, the processing unit [104] in order to modify, iteratively, the determined initial set of routes is further configured to reconfigure an ordering of locations on the route. For instance, the processing unit [104] is configured to exchange/reorder one or more locations/customers between a pair of routes, wherein each of these routes is further optimized independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered. [0053]), in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route (In one implementation, the two customer segments, one in each route, are determined by also considering capacity constraints requiring that the number of customers in each route is less than a threshold. Thereafter, the processing unit [104] is further configured to analyze an impact of a customer segment swap on an overall cost including cost associated with time-window violations. Further, the customer segment swaps iterates over all combinations of traversals of the customer segment pair. [0045]); and
allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route (In one implementation, the two customer segments, one in each route, are determined by also considering capacity constraints requiring that the number of customers in each route is less than a threshold. Thereafter, the processing unit [104] is further configured to analyze an impact of a customer segment swap on an overall cost including cost associated with time-window violations. Further, the customer segment swaps iterates over all combinations of traversals of the customer segment pair. [0045]);
[constructing] the line to intersect a first centroid of the first vehicle route and a second centroid of the second vehicle route (the method encompasses identifying via the processing unit [104], one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids [0080]);
determine an overlap-optimized (to reduce regions having overlapping routes [0007]) vehicle routing plan including the first new route and the second new route (the FIG. 4 (c) indicates a reinsertion of the three identified customers/locations i.e. A, B and C into the routes based on an associated minimum insertion cost. [0088]); and
provide the overlap-optimized vehicle routing plan to control dispatch of a plurality of vehicles (the present disclosure provides systems and methods for vehicular fleet routing that provides better route optimization during one or more shipment deliveries and shipment scheduling in heterogeneous hubs [0100]; examiner notes that the method would inherently send the final routes out to the vehicles.).
Kannan does not explicitly teach, however Li teaches:
using an ordered projection of the destination nodes (The specific solution is as follows: for the current road line (road topological line) according to a certain width to generate the road line of the buffer area, judging which points into the buffer to find the (road line) boundary, calculate the boundary point on the road line of the projection point (the boundary point of the road line as vertical to the road line, the intersection point is the projection point), and establishing a boundary point (original point) one-to-one corresponding relation with the projection point (as shown in FIG. 8). the buffer area is an influence range or geographic space target service range, specifically refers to a polygon with a certain width around the point, line and plane entity established. calculated (located) on the road line each projection point along the passage route to starting point of road line length according to the length of said projection point sequencing, thereby forming ordered projection point set. [page 4]) onto a line passing through the first vehicle route and the second vehicle route (examiner notes that it would be obvious to use the line between the route centroids as determined in Kannan as the projection line for the ordered projection as taught by Li),
wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line (see at least fig. 8 showing the points being projected to the line in an orthogonal direction.)
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan to include the teachings as taught by Li with a reasonable expectation of success. Kannan teaches the ability to optimize the routing of multiple vehicles by reallotting the points between two routes. However, Kannan does not explicitly teach that using an ordered projection is the method used to reallocate the points. However, ordered projections is a known mathematical concept that would be known to one having ordinary skill in the art and Kannan does teach the ability to calculate the line between the centroids of the two routes. Therefore it would have been obvious to apply the use of an ordered projection as taught by Li to arrive at the claimed invention. Li is in the same field of endeavor of navigation routing and would be applying one of a finite amount of methods for optimizing the ordering of navigation routing which would be well within the skill of one having ordinary skill in the art at the time of filing.
Kannan in view of Li does not explicitly teach, however Kokiopoulou teaches:
an ordered projection of the destination nodes (The proposed method, named orthogonal Neighborhood Preserving Projections (ONPP) [3], projects the high-dimensional data samples on a lower dimensional space by means of a linear transformation V [page 2143]) onto a line passing through the first vehicle route and the second vehicle route (Given a data set X ¼ ½x1; x2; ... ; xn 2 Rmn, the goal of dimensionality reduction is to produce a set Y , which is an accurate representation of X, but which is of dimension d, with d - m. This can be achieved in different ways by selecting the type of the reduced dimension Y and the desirable properties to be preserved. By type, we mean whether we require that Y be simply a low-rank representation of X or a data set in a vector space with fewer dimensions. [page 2144]; examiner notes that it would have been obvious for one having ordinary skill in the art to have chosen the line connecting the route centroids as taught in Kannan as the line to perform the projection onto as taught by Kokiopoulou. When looking to find an optimal order for the routes, one would be motivated to use a projection line that best corresponds to provide the best spread of the data, which would occur via the line connecting the centroids. This also amounts to routine optimization because given the finite amount of orientations to use for the projection line it would have been obvious to find this orientation through routine experimentation.)
constructing the line to intersect a first centroid of the first vehicle route and a second centroid of the second vehicle route (Given a data set X ¼ ½x1; x2; ... ; xn 2 Rmn, the goal of dimensionality reduction is to produce a set Y , which is an accurate representation of X, but which is of dimension d, with d - m. This can be achieved in different ways by selecting the type of the reduced dimension Y and the desirable properties to be preserved. By type, we mean whether we require that Y be simply a low-rank representation of X or a data set in a vector space with fewer dimensions. [page 2144]);
determining projections of the destination nodes of the first vehicle route and the second vehicle route onto the line (Projection-based techniques consist of replacing the original data X by a matrix of the form Y ¼ V >X; where V 2 Rmd: ð1Þ Thus, each vector xi is replaced by yi ¼ V >xi, a member of the d-dimensional space Rd. If V is a unitary matrix, then Y represents the orthogonal projection of X into the V -space [page 2144]), wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line (the goal of dimensionality reduction is to produce a set Y, which is an accurate representation of X but which is of a dimension d, with d<<m. [page 2144]; examiner notes that reducing dimensionality of the data does not reduce the amount of data points, just the dimension that represents each data point (i.e. projection).);
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li to include the teachings as taught by Kokiopoulou with a reasonable expectation of success. Kokiopoulou teaches “The goal of dimensionality reduction is to map the high-dimensional samples to a lower dimensional space such that certain properties are preserved. Usually, the property that is preserved is quantified by an objective function and the dimensionality reduction problem is formulated as an optimization problem [Kokiopoulou, page 2143]” and “a linear dimensionality reduction technique is advocated, which preserves the intrinsic geometry of the local neighborhoods. The proposed method, named Orthogonal Neighborhood Preserving Projections (ONPP) [3], projects the high-dimensional data samples on a lower dimensional space by means of a linear transformation V [Kokiopoulou, page 2143]”.
Singh also teaches:
allocating the destination nodes of the first vehicle route and the second vehicle route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]); and
allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]);
Kannan in view of Li and Kokiopoulou does not explicitly teach, however Singh teaches:
determining a sequential order of the destination nodes of the first vehicle route and the second vehicle route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), according to an order of the projections of the destination nodes onto the line (a dynamic program is implemented to permute the customers in order to find the sequence of customers on the route that will optimize the route cost [0101]; examiner notes that applying the teachings of Li and Kokiopoulou as shown above it would have been obvious to have applied the projection technique with the teachings of Singh to arrive at the claimed invention.);
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li and Kokiopoulou to include the teachings as taught by Singh with a reasonable expectation of success. Singh teaches the benefits of “the exemplary optimized cargo transportation solution development systems and methods described in this application are operable to optimally assign trucks to specific routes, determine optimal truck routes, and minimize transportation costs [Singh, 0007]”.
Regarding claim 10:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 9, upon which this claim is dependent.
Kannan further teaches:
if all of the destinations nodes are successfully allocated, adopt the first candidate route as the first new route and the second candidate route as the second new route if the allocating accounts for all of the destinations nodes (the processing unit [104] is also configured to select, a route modification criteria based on one or more iterations. Also, thereafter, the processing unit [104] is further configured to arrive, at a final set of routes based on a stopping criteria. Also, one implementation of the stopping criteria may be a total number of iterations reaching a specified limit, based on which the processing unit [104] arrives at the final set of routes. [0059]); and
Singh further teaches:
if all of the destinations nodes are not successfully allocated (the system [100] is also configured to provide route optimization in various modes where a route capacity constraint may be violated at an intermediate stage in order to explore the solution space more thoroughly, but these capacity constraints are restored via the system [100] while implementing the features of the present disclosure.), rotate the line by an angle (examiner notes that Kannan teaches repeating the allocation process even when it fails to create a satisfactory route and in light of the projection of the points onto the line as taught in claim 1, it would be obvious to rotate the line in order to change a variable in order to rerun the allocation. The projection reduces the 2D map into a 1D line and in order to be able to retry the allocation the 1D line needs to be changed, which is only possible of the projection is redone around a different angle.) and allocate the destination nodes in order along the rotates line to a first additional candidate route and a second additional candidate route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), the first additional candidate route satisfying the first capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]), the second additional candidate route satisfying the second capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]).
Regarding claim 11:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 8, upon which this claim is dependent.
Kannan further teaches:
repeat execution of the instructions to select and reallocate for additional pairs of vehicle routes, wherein the overlap-optimized vehicle routing plan further includes additional pairs of new routes determined by the repeated execution (The method further comprises modifying, iteratively, the determined initial set of routes based on a combination of multiple operations that reconfigure the routes to arrive at a final configuration of routes. [abstract]).
Regarding claim 12:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 11, upon which this claim is dependent.
Kannan further teaches:
wherein the repeated execution is performed (The method further comprises modifying, iteratively, the determined initial set of routes based on a combination of multiple operations that reconfigure the routes to arrive at a final configuration of routes. [abstract]) to account for all vehicle routes having an overlap metric satisfying an overlap optimization criterion (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]).
Regarding claim 15:
Kannan teaches:
A non-transitory memory medium configured to store instructions executable by one or more processors (The system [100] comprises, at least one transceiver unit [102], at least one processing unit [104] and at least one storage unit [106] [0033]) to perform the acts of:
storing in a non-transitory memory medium (As used herein, “memory unit”, “storage unit” and/or “memory” refers to a machine or computer-readable medium including any mechanism for storing information in a form readable by a computer or similar machine. For example, a computer-readable medium includes read-only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices or other types of machine-accessible storage media. Any of the methods herein can be implemented in one or more computer-readable media comprising computer-executable instructions that, when executed, cause a computing system to perform the method. [0030]) a vehicle routing plan including a plurality of vehicle routes (The invention aims to achieve efficient planning of routes for servicing a set of locations at specified time windows from a given hub by a certain number of vehicles. [0022]), the vehicle routing plan being optimized according to at least one optimization criterion other than an overlap criterion (the present disclosure in order to provide a solution relating to optimal routing of shipments, takes into consideration a number of cost parameters associated with outliers on routes, uneven distribution of shipments across the vehicles and non-compactness of routes aside from constraints associated with capacity of the vehicles and arrivals at customer locations within their respective time-windows. [0022]), each of the plurality of vehicle routes including a plurality of destination nodes for a respective vehicle () and satisfying capacity (constraints associated with capacity of the vehicles [0022]) and timing parameters (and arrivals at customer locations within their respective time-windows [0022]) for the respective vehicle to serve the plurality of destination nodes (an initial set of routes between the hub and the set of locations [0037]);
computing a plurality of overlap metrics (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]) of the plurality of vehicle routes (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed[0044]; Furthermore, in one more instance, the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids. Further, said one or more route pairs are identified for switching/swapping the one or more locations between them. Thereafter, the processing unit [104] is configured to assign the one or more route pairs, a probability inversely proportional to square root of the rank (i.e. of the distance), to further determine the route pair based on that probability. Once the route pair is determined, the processing unit [104] is thereafter configured to identify one or more customer segments at random, both in terms of their starting index and their length with a constraint that the number of customers does not exceed a threshold. [0046]);
selecting a first vehicle route and a second vehicle route of the plurality of vehicle routes (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed. Also, in an instance the selection of route-pair and the one or more customers to be removed is further based on a reduction or elimination of a total capacity breach. [0078]) using the plurality of overlap metrics (the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed[0044]; Furthermore, in one more instance, the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids. Further, said one or more route pairs are identified for switching/swapping the one or more locations between them. Thereafter, the processing unit [104] is configured to assign the one or more route pairs, a probability inversely proportional to square root of the rank (i.e. of the distance), to further determine the route pair based on that probability. Once the route pair is determined, the processing unit [104] is thereafter configured to identify one or more customer segments at random, both in terms of their starting index and their length with a constraint that the number of customers does not exceed a threshold. [0046]);
reallocating the destination nodes of the first vehicle route and the second vehicle route to a first new route and a second new route (see figs. 4a-4c showing altering of routes 1 and 2; the determination of the route-pair in such instances may be based on a selection of an initial route at random, followed by identifying the one or more customers required to be removed from it, and then finding a neighboring route that is nearest to the one or more customers being removed. Also, in an instance the selection of route-pair and the one or more customers to be removed is further based on a reduction or elimination of a total capacity breach. [0076]) using [an ordered projection] of the destination nodes onto a line passing through the first vehicle route and the second vehicle route (the processing unit [104] is configured to identify one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids [0046]), the first new route satisfying first capacity and timing parameters of the first vehicle route, the second new route satisfying second capacity and timing parameters of the first vehicle route (the present disclosure in order to provide a solution relating to optimal routing of shipments, takes into consideration a number of cost parameters associated with outliers on routes, uneven distribution of shipments across the vehicles and non-compactness of routes aside from constraints associated with capacity of the vehicles and arrivals at customer locations within their respective time-windows. [0022])
wherein the reallocating (the method in order to exchange/reorder one or more locations/customers between a pair of routes, encompasses optimizing each route independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered. [0091]) comprises:
allocating the destination nodes of the first vehicle route and the second vehicle route (Furthermore, the processing unit [104] in order to modify, iteratively, the determined initial set of routes is further configured to reconfigure an ordering of locations on the route. For instance, the processing unit [104] is configured to exchange/reorder one or more locations/customers between a pair of routes, wherein each of these routes is further optimized independently by considering one or more standard edge-exchange operations within and between routes, such as all possible 2-edge exchanges and/or the like edge-exchange operations may be considered. [0053]), in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route (In one implementation, the two customer segments, one in each route, are determined by also considering capacity constraints requiring that the number of customers in each route is less than a threshold. Thereafter, the processing unit [104] is further configured to analyze an impact of a customer segment swap on an overall cost including cost associated with time-window violations. Further, the customer segment swaps iterates over all combinations of traversals of the customer segment pair. [0045]); and
allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route (In one implementation, the two customer segments, one in each route, are determined by also considering capacity constraints requiring that the number of customers in each route is less than a threshold. Thereafter, the processing unit [104] is further configured to analyze an impact of a customer segment swap on an overall cost including cost associated with time-window violations. Further, the customer segment swaps iterates over all combinations of traversals of the customer segment pair. [0045]);
[constructing] the line to intersect a first centroid of the first vehicle route and a second centroid of the second vehicle route (the method encompasses identifying via the processing unit [104], one or more route pairs, based on ranking the one or more route pairs on the basis of distance between their centroids [0080]);
determining an overlap-optimized (to reduce regions having overlapping routes [0007]) vehicle routing plan including the first new route and the second new route (the FIG. 4 (c) indicates a reinsertion of the three identified customers/locations i.e. A, B and C into the routes based on an associated minimum insertion cost. [0088]); and
providing the overlap-optimized vehicle routing plan to control dispatch of a plurality of vehicles (the present disclosure provides systems and methods for vehicular fleet routing that provides better route optimization during one or more shipment deliveries and shipment scheduling in heterogeneous hubs [0100]; examiner notes that the method would inherently send the final routes out to the vehicles.).
Kannan does not explicitly teach, however Li teaches:
using an ordered projection of the destination nodes (The specific solution is as follows: for the current road line (road topological line) according to a certain width to generate the road line of the buffer area, judging which points into the buffer to find the (road line) boundary, calculate the boundary point on the road line of the projection point (the boundary point of the road line as vertical to the road line, the intersection point is the projection point), and establishing a boundary point (original point) one-to-one corresponding relation with the projection point (as shown in FIG. 8). the buffer area is an influence range or geographic space target service range, specifically refers to a polygon with a certain width around the point, line and plane entity established. calculated (located) on the road line each projection point along the passage route to starting point of road line length according to the length of said projection point sequencing, thereby forming ordered projection point set. [page 4]) onto a line passing through the first vehicle route and the second vehicle route (examiner notes that it would be obvious to use the line between the route centroids as determined in Kannan as the projection line for the ordered projection as taught by Li),
wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line (see at least fig. 8 showing the points being projected to the line in an orthogonal direction.)
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan to include the teachings as taught by Li with a reasonable expectation of success. Kannan teaches the ability to optimize the routing of multiple vehicles by reallotting the points between two routes. However, Kannan does not explicitly teach that using an ordered projection is the method used to reallocate the points. However, ordered projections is a known mathematical concept that would be known to one having ordinary skill in the art and Kannan does teach the ability to calculate the line between the centroids of the two routes. Therefore it would have been obvious to apply the use of an ordered projection as taught by Li to arrive at the claimed invention. Li is in the same field of endeavor of navigation routing and would be applying one of a finite amount of methods for optimizing the ordering of navigation routing which would be well within the skill of one having ordinary skill in the art at the time of filing.
Kannan in view of Li does not explicitly teach, however Kokiopoulou teaches:
an ordered projection of the destination nodes (The proposed method, named orthogonal Neighborhood Preserving Projections (ONPP) [3], projects the high-dimensional data samples on a lower dimensional space by means of a linear transformation V [page 2143]) onto a line passing through the first vehicle route and the second vehicle route (Given a data set X ¼ ½x1; x2; ... ; xn 2 Rmn, the goal of dimensionality reduction is to produce a set Y , which is an accurate representation of X, but which is of dimension d, with d - m. This can be achieved in different ways by selecting the type of the reduced dimension Y and the desirable properties to be preserved. By type, we mean whether we require that Y be simply a low-rank representation of X or a data set in a vector space with fewer dimensions. [page 2144]; examiner notes that it would have been obvious for one having ordinary skill in the art to have chosen the line connecting the route centroids as taught in Kannan as the line to perform the projection onto as taught by Kokiopoulou. When looking to find an optimal order for the routes, one would be motivated to use a projection line that best corresponds to provide the best spread of the data, which would occur via the line connecting the centroids. This also amounts to routine optimization because given the finite amount of orientations to use for the projection line it would have been obvious to find this orientation through routine experimentation.)
constructing the line to intersect a first centroid of the first vehicle route and a second centroid of the second vehicle route (Given a data set X ¼ ½x1; x2; ... ; xn 2 Rmn, the goal of dimensionality reduction is to produce a set Y , which is an accurate representation of X, but which is of dimension d, with d - m. This can be achieved in different ways by selecting the type of the reduced dimension Y and the desirable properties to be preserved. By type, we mean whether we require that Y be simply a low-rank representation of X or a data set in a vector space with fewer dimensions. [page 2144]);
determining projections of the destination nodes of the first vehicle route and the second vehicle route onto the line (Projection-based techniques consist of replacing the original data X by a matrix of the form Y ¼ V >X; where V 2 Rmd: ð1Þ Thus, each vector xi is replaced by yi ¼ V >xi, a member of the d-dimensional space Rd. If V is a unitary matrix, then Y represents the orthogonal projection of X into the V -space [page 2144]), wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line (the goal of dimensionality reduction is to produce a set Y, which is an accurate representation of X but which is of a dimension d, with d<<m. [page 2144]; examiner notes that reducing dimensionality of the data does not reduce the amount of data points, just the dimension that represents each data point (i.e. projection).);
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li to include the teachings as taught by Kokiopoulou with a reasonable expectation of success. Kokiopoulou teaches “The goal of dimensionality reduction is to map the high-dimensional samples to a lower dimensional space such that certain properties are preserved. Usually, the property that is preserved is quantified by an objective function and the dimensionality reduction problem is formulated as an optimization problem [Kokiopoulou, page 2143]” and “a linear dimensionality reduction technique is advocated, which preserves the intrinsic geometry of the local neighborhoods. The proposed method, named Orthogonal Neighborhood Preserving Projections (ONPP) [3], projects the high-dimensional data samples on a lower dimensional space by means of a linear transformation V [Kokiopoulou, page 2143]”.
Singh also teaches:
allocating the destination nodes of the first vehicle route and the second vehicle route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]); and
allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route (The FrO program may operate based on two primary inputs: standard input shipment files and freight optimization parameters. The freight optimization parameters may include, without limitation, time constraints, capacity constraints, basic cost parameters, the tariff used to rate the zip-to-zip travel cost, and/or any of the other parameters identified above. [0057]);
Kannan in view of Li and Kokiopoulou does not explicitly teach, however Singh teaches:
determining a sequential order of the destination nodes of the first vehicle route and the second vehicle route (the FlO program preferably adopts a rolling-window to perform permutation, as represented in FIG. 8. The idea of this heuristic is to fix the length of the partial sequence (w) and roll w over the k.sup.th route. For each w, the FlO program calls the DP (permutation) procedure described above and combines all the w's to form a new sequence. If the new sequence is feasible, it means the new sequence is better than the original sequence, and the FlO program assigns this solution to the k.sup.th ant. [0112]), according to an order of the projections of the destination nodes onto the line (a dynamic program is implemented to permute the customers in order to find the sequence of customers on the route that will optimize the route cost [0101]; examiner notes that applying the teachings of Li and Kokiopoulou as shown above it would have been obvious to have applied the projection technique with the teachings of Singh to arrive at the claimed invention.);
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li and Kokiopoulou to include the teachings as taught by Singh with a reasonable expectation of success. Singh teaches the benefits of “the exemplary optimized cargo transportation solution development systems and methods described in this application are operable to optimally assign trucks to specific routes, determine optimal truck routes, and minimize transportation costs [Singh, 0007]”.
Regarding claim 17:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 16, upon which this claim is dependent.
Kannan further teaches:
repeating the allocating with the line rotated by an angle (examiner notes that Kannan teaches repeating the allocation process even when it fails to create a satisfactory route and in light of the projection of the points onto the line as taught in claim 1, it would be obvious to rotate the line in order to change a variable in order to rerun the allocation. The projection reduces the 2D map into a 1D line and in order to be able to retry the allocation the 1D line needs to be changed, which is only possible of the projection is redone around a different angle.) if the allocating does not successfully allocate all of the destinations nodes (the system [100] is also configured to provide route optimization in various modes where a route capacity constraint may be violated at an intermediate stage in order to explore the solution space more thoroughly, but these capacity constraints are restored via the system [100] while implementing the features of the present disclosure.); and
adopting the first candidate route as the first new route and the second candidate route as the second new route if the allocating accounts for all of the destinations nodes (Next, at step [212], the method comprises selecting, via the processing unit [104], a route modification criteria based on one or more iterations. Further, at step [214], the method comprises arriving, via the processing unit [104], at a final set of routes based on a stopping criteria. [0096-0097]; the processing unit [104] is also configured to select, a route modification criteria based on one or more iterations. Also, thereafter, the processing unit [104] is further configured to arrive, at a final set of routes based on a stopping criteria [0059]).
Singh further teaches:
if the allocating does not successfully allocate all of the destinations nodes (With respect to optimizing cargo transportation solution development using ACO, each ant may be equated with a fleet of trucks. When the ant (trucks) initially leaves the nest (origin) it represents a single one of the trucks. When the ant returns and then leaves the origin again, the ant represents a new truck. The scope of the ant ends whenever either all packages are delivered or all truck capacity is filled. In the searching process associated with the FrO program, if a previous truck in the ant colony (truck fleet) has already delivered a package, or the desired location cannot be reached, the node is stored in an infeasible or tabu list. As indicated below, the exemplary FrO program uses the notation Tabu.sup.k to store nodes that have already been visited by ant (truck) k and nodes that violate constraints so that they are removed from further consideration. [0065]); and
Regarding claim 18:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 15, upon which this claim is dependent.
Kannan further teaches:
repeating the selecting and the reallocating for additional pairs of vehicle routes, wherein the determining the overlap-optimized vehicle routing plan further includes additional pairs of new routes determined by the repeating the reallocating for the additional pairs of vehicle routes (The method further comprises modifying, iteratively, the determined initial set of routes based on a combination of multiple operations that reconfigure the routes to arrive at a final configuration of routes. [abstract]).
Regarding claim 19:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 18, upon which this claim is dependent.
Kannan further teaches:
wherein the repeating is performed (The method further comprises modifying, iteratively, the determined initial set of routes based on a combination of multiple operations that reconfigure the routes to arrive at a final configuration of routes. [abstract]) to account for all vehicle routes having an overlap metric satisfying an overlap optimization criterion (Another object of the present disclosure is not only to decrease the total travel time during a shipment delivery but also to reduce regions having overlapping routes [0007]).
Claim(s) 6-7, 13-14, and 20-21 is/are rejected under 35 U.S.C. 103 as being unpatentable over Kannan (US 2021/0004763), herein Kannan in view of Li et. al. (CN 105701204), herein Li, Kokiopoulou et. al. (Orthogonal Neighborhood Preserving Projections: A Projection-Based Dimensionality Reduction Technique - NPL), and Singh et. al. (US 2022/0156693), herein Singh in further view of Zhong et. al. (US 7,363,126), herein Zhong (From IDS).
Regarding claim 6:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 1, upon which this claim is dependent.
Kannan in view of Li, Kokiopoulou, and Singh does not explicitly teach, however Zhong teaches:
wherein the computing the plurality of overlap metrics includes computing an overlap of polygonal hulls (defining a convex hull polygon about the route; (26) (d) defining a plurality of unassigned convex hull polygons about each of the plurality of unassigned routes; (27) (e) comparing the convex hull polygon to each of the plurality of unassigned convex hull polygons and calculating a corresponding plurality of hull overlap areas; (28) (f) identifying a maximum hull overlap area from among the plurality of hull overlap areas, the maximum hull overlap area corresponding to a maximum route from among the plurality of unassigned routes; [col 3, lines 17-26]) defining perimeters of respective vehicle routes (To apply the Convex Hull heuristic algorithm, the following steps may be followed: (1) Create the convex hull of all the stops 42 within a cell 40. The convex hull of a set of points is defined as the smallest convex polygon that encloses all the points. In this procedure, the convex hull may form an outer loop of hull stops k which, when connected, produce a sub-route 45 within the cell 40. The sub-route 45 of hull stops k serves as a starting point for the computation. (2) For each stop 42 that is not a hull stop k, find the best insertion position (between stop i and stop j), such that (d.sub.ik+d.sub.kj-d.sub.ij) is minimal, where d.sub.ik is the distance between stop i and k, etc. (3) For each solution (a sequence of stops: i, k, j) found in step 2, select the best insertion stop k* and its best insertion position (between stop i* and stop j*), such that (C.sub.i*k*+C.sub.k*j*)/C.sub.i*j* is minimal. (4) Insert stop k* into the sub-route 45 between stop i* and stop j*. (5) Repeat steps 2, 3, and 4, until all the stops 42 in the sub-route 45 are ordered such that each stop 42 is visited exactly once. [col 8. Line 59- col 9, line 13]).
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li, Kokiopoulou, and Singh to include the teachings as taught by Zhong with a reasonable expectation of success. Zhong teaches the benefits of “Route planning methods for use by a package delivery service provider are disclosed that satisfy a stochastic daily demand while taking advantage of drivers' route familiarity over time. A model for estimating the value of driver familiarity is disclosed along with both an empirical and a mathematical model for estimating the value of route consistency, along with a Core Area Route Design which involves the concepts of combinational optimization, meta-heuristic algorithms, tabu search heuristics, network formulation modeling, and multi-stage graph modeling. In one embodiment, a service territory is divided into unassigned cells associated with a grid segment involving prior driver delivery stops, and a driver from a pool of unassigned drivers is assigned to a route based on examining each driver's grid segment visiting frequency limit with respect to a minimum limit so as to optimize driver selection based on of each driver's familiarity with the route. [Zhong, abstract]”.
Regarding claim 7:
Kannan in view of Li, Kokiopoulou, Singh and Zhong teaches all the limitations of claim 6, upon which this claim is dependent.
Kannan further teaches:
wherein each of the plurality of overlap metrics accounts for a number of destination nodes of one vehicle route encroaching on the perimeter of another vehicle route (the removal of the first subset of location from the one or more routes is further based on at least one of a proximity to a specific location [0081]; see fig. 4b showing the cluster ABC of points removed and reallocated.).
Regarding claim 13:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 8, upon which this claim is dependent.
Kannan in view of Li, Kokiopoulou, and Singh does not explicitly teach, however Zhong teaches:
wherein the instructions to compute the plurality of overlap metrics includes instructions to compute an overlap of polygonal hulls (defining a convex hull polygon about the route; (26) (d) defining a plurality of unassigned convex hull polygons about each of the plurality of unassigned routes; (27) (e) comparing the convex hull polygon to each of the plurality of unassigned convex hull polygons and calculating a corresponding plurality of hull overlap areas; (28) (f) identifying a maximum hull overlap area from among the plurality of hull overlap areas, the maximum hull overlap area corresponding to a maximum route from among the plurality of unassigned routes; [col 3, lines 17-26]) defining perimeters of respective vehicle routes (To apply the Convex Hull heuristic algorithm, the following steps may be followed: (1) Create the convex hull of all the stops 42 within a cell 40. The convex hull of a set of points is defined as the smallest convex polygon that encloses all the points. In this procedure, the convex hull may form an outer loop of hull stops k which, when connected, produce a sub-route 45 within the cell 40. The sub-route 45 of hull stops k serves as a starting point for the computation. (2) For each stop 42 that is not a hull stop k, find the best insertion position (between stop i and stop j), such that (d.sub.ik+d.sub.kj-d.sub.ij) is minimal, where d.sub.ik is the distance between stop i and k, etc. (3) For each solution (a sequence of stops: i, k, j) found in step 2, select the best insertion stop k* and its best insertion position (between stop i* and stop j*), such that (C.sub.i*k*+C.sub.k*j*)/C.sub.i*j* is minimal. (4) Insert stop k* into the sub-route 45 between stop i* and stop j*. (5) Repeat steps 2, 3, and 4, until all the stops 42 in the sub-route 45 are ordered such that each stop 42 is visited exactly once. [col 8. Line 59- col 9, line 13]).
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li, Kokiopoulou, and Singh to include the teachings as taught by Zhong with a reasonable expectation of success. Zhong teaches the benefits of “Route planning methods for use by a package delivery service provider are disclosed that satisfy a stochastic daily demand while taking advantage of drivers' route familiarity over time. A model for estimating the value of driver familiarity is disclosed along with both an empirical and a mathematical model for estimating the value of route consistency, along with a Core Area Route Design which involves the concepts of combinational optimization, meta-heuristic algorithms, tabu search heuristics, network formulation modeling, and multi-stage graph modeling. In one embodiment, a service territory is divided into unassigned cells associated with a grid segment involving prior driver delivery stops, and a driver from a pool of unassigned drivers is assigned to a route based on examining each driver's grid segment visiting frequency limit with respect to a minimum limit so as to optimize driver selection based on of each driver's familiarity with the route. [Zhong, abstract]”.
Regarding claim 14:
Kannan in view of Li, Kokiopoulou, and Singh and Zhong teaches all the limitations of claim 13, upon which this claim is dependent.
Kannan further teaches:
wherein each of the plurality of overlap metrics accounts for a number of destination nodes of one vehicle route encroaching on the perimeter of another vehicle route (the removal of the first subset of location from the one or more routes is further based on at least one of a proximity to a specific location [0081]; see fig. 4b showing the cluster ABC of points removed and reallocated.).
Regarding claim 20:
Kannan in view of Li, Kokiopoulou, and Singh teaches all the limitations of claim 15, upon which this claim is dependent.
Kannan in view of Li, Kokiopoulou, and Singh does not explicitly teach, however Zhong teaches:
wherein the act of computing the plurality of overlap metrics includes computing an overlap of polygonal hulls (defining a convex hull polygon about the route; (26) (d) defining a plurality of unassigned convex hull polygons about each of the plurality of unassigned routes; (27) (e) comparing the convex hull polygon to each of the plurality of unassigned convex hull polygons and calculating a corresponding plurality of hull overlap areas; (28) (f) identifying a maximum hull overlap area from among the plurality of hull overlap areas, the maximum hull overlap area corresponding to a maximum route from among the plurality of unassigned routes; [col 3, lines 17-26]) defining perimeters of respective vehicle routes (To apply the Convex Hull heuristic algorithm, the following steps may be followed: (1) Create the convex hull of all the stops 42 within a cell 40. The convex hull of a set of points is defined as the smallest convex polygon that encloses all the points. In this procedure, the convex hull may form an outer loop of hull stops k which, when connected, produce a sub-route 45 within the cell 40. The sub-route 45 of hull stops k serves as a starting point for the computation. (2) For each stop 42 that is not a hull stop k, find the best insertion position (between stop i and stop j), such that (d.sub.ik+d.sub.kj-d.sub.ij) is minimal, where d.sub.ik is the distance between stop i and k, etc. (3) For each solution (a sequence of stops: i, k, j) found in step 2, select the best insertion stop k* and its best insertion position (between stop i* and stop j*), such that (C.sub.i*k*+C.sub.k*j*)/C.sub.i*j* is minimal. (4) Insert stop k* into the sub-route 45 between stop i* and stop j*. (5) Repeat steps 2, 3, and 4, until all the stops 42 in the sub-route 45 are ordered such that each stop 42 is visited exactly once. [col 8. Line 59- col 9, line 13]).
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Kannan in view of Li, Kokiopoulou, and Singh to include the teachings as taught by Zhong with a reasonable expectation of success. Zhong teaches the benefits of “Route planning methods for use by a package delivery service provider are disclosed that satisfy a stochastic daily demand while taking advantage of drivers' route familiarity over time. A model for estimating the value of driver familiarity is disclosed along with both an empirical and a mathematical model for estimating the value of route consistency, along with a Core Area Route Design which involves the concepts of combinational optimization, meta-heuristic algorithms, tabu search heuristics, network formulation modeling, and multi-stage graph modeling. In one embodiment, a service territory is divided into unassigned cells associated with a grid segment involving prior driver delivery stops, and a driver from a pool of unassigned drivers is assigned to a route based on examining each driver's grid segment visiting frequency limit with respect to a minimum limit so as to optimize driver selection based on of each driver's familiarity with the route. [Zhong, abstract]”.
Regarding claim 21:
Kannan in view of Li, Kokiopoulou, Singh, and Zhong teaches all the limitations of claim 20, upon which this claim is dependent.
Kannan further teaches:
wherein each of the plurality of overlap metrics accounts for a number of destination nodes of one vehicle route encroaching on the perimeter of another vehicle route (the removal of the first subset of location from the one or more routes is further based on at least one of a proximity to a specific location [0081]; see fig. 4b showing the cluster ABC of points removed and reallocated.).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Kwatra (US 2023/0316215) discloses A delivery location of a first user is linked to a tokenized identifier of a package including an ordered item and delivery is initiated. A second order for the same item is received from a second user also requesting expedited delivery while the item ordered by the first user is en-route for delivery. An incentive is offered to a computing device of the first user in exchange for agreeing to a delayed delivery of the item ordered by the first user. An expedited delivery timeframe in exchange for additional compensation is offered to a computing device of the second user, and in response to receiving an acceptance of the incentive for delayed delivery and the expedited delivery in exchange for additional compensation the link to the tokenized identifier is changed to a delivery location of the second user while the package including the item is en-route.
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 Scott R Jagolinzer whose telephone number is (571)272-4180. The examiner can normally be reached M-Th 8AM - 4PM Eastern.
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, Christian Chace can be reached at (571)272-4190. 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.
Scott R. Jagolinzer
Examiner
Art Unit 3665
/S.R.J./Examiner, Art Unit 3665 /CHRISTIAN CHACE/Supervisory Patent Examiner, Art Unit 3665
Prosecution Insights