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 expl