Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendments
This action is in response to amendments and remarks filed on 10/06/2025.
Claims 1-3, 5-7, 9-11 and 13 are pending. Claims 4, 8 and 12 are cancelled. Claims 1, 5 and 9 are amended. Claim 13 is new. Applicant's amendment necessitated new grounds of rejection therefore, claims 1-3, 5-7, 9-11 and 13 are rejected.
Response to Arguments
Applicant presents the following arguments regarding the previous office action:
James does not disclose the nodes being sorted based upon a minimum angle from the depot and starting with an angle as 0, and the plurality of initial routes are created with minimum angle nodes until a capacity constraint is satisfied, and calculating polar angles of nodes in the network of customers.
None of the prior art James, Zhong, Stefan, Kindervater, Wang and Rousseau discloses the amended claim limitations of claim 4 which are incorporated into claim 1.
James, Zhong, Stefan, Kindervater, Wang and Rousseau do not teach or suggest the amended claim limitations of new claim 13.
Regarding Applicant’s arguments A-C, the arguments have been fully considered and is moot in light of new grounds for rejection below with the incorporation of Huang et al, Kupriyanova, and Tarawneh et al.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 5-7 and 9-11 are all rejected under 35 U.S.C. 103 as being unpatentable over James et al. (US20130096815A1) in view of Zhong (US7660651B2), further in view of Stefan et al. (An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows), further in view of Kindervater et al. (Vehicle Routing 2 Handling Side Constraints), further in view of Wang et al. (CN110006430B), further in view of Tarawneh et al. (Solving Capacitated Vehicle Routing Problem Using Two Phase Heuristic Method), further in view of Huang et al. (Rapid Route Comparison Based on GPS Coordinates and Bounding Boxes).
Regarding claim 1, James discloses, a processor implemented method for vehicle route optimization, (James, Terminology, Paragraph 4, Lines 1-3, the various illustrative logical blocks and modules described in connection with the embodiments disclosed herein can be implemented or performed by a machine, such as a general purpose processor) comprising: obtaining, via one or more hardware processors, information on (i) a network of customers (0052, (e.g., the fleet vehicle type to be routed, service level selected by the requestor, customer identification code, etc.) for a particular fleet of vehicles), wherein the network of customers comprises nodes corresponding to a plurality of customer locations and a depot, and edges representing connections between the customer locations, (ii) distance between each pair of customer locations among the plurality of customer locations (James, Distance Estimation, Paragraph 2, Lines 4-7, nodes in the tree represent vehicle stops and edges represent cost between the stops (such as driving time, fuel costs, distance, wait time, combinations of the same, or the like). A user can request multiple distance estimates to be run with different routes), (iii) one or more orders received from one or more of the customers from the network of customers (James, Vehicle Management System Overview, Paragraph 2, Lines 6-15, users can access and monitor vehicle information obtained from one or more of the in-vehicle devices 105 by the vehicle management system 150. Such vehicle status information can include data on vehicle routes used, stops, speed, vehicle feature usage (such as power takeoff device usage), driver behavior and performance, vehicle emissions, vehicle maintenance, energy usage, and the like), (iv) service start time,(v) service end time, (James, Exclusion Zones Embodiments, Paragraph 1, Lines 1-8, the routing module can delay the start of a vehicle's route if it would be more efficient to do so. As an illustration, an exclusion zone might specify that certain vehicles cannot enter the zone from 9 am to 10 am. If a driver of such a vehicle is ordinarily scheduled to start his route at 8 am but has to go through the exclusion zone), and(vi) servicing time (James, Routing Module Embodiments, Paragraph 6, Lines 2-6, the feasible routes can be determined using one or more initial searching algorithms based on one or more initial criteria, factors or variables (e.g., distance and/or estimated transit time) to trim down the search space to exclude unreasonable routes); creating a plurality of initial routes based on the network of customers (James, Gravity Points, Paragraph 3, Lines 1-3, the vehicle management system 150 can instead provide functionality for users to define a predetermined point within a drivers territory), by considering the depot as a center coordinate and by calculating polar angles of the nodes in the network of customers, to assign the nodes to the plurality of initial routes (James, Gravity Points, Paragraph 3, Lines 3-6, which can also be considered a gravity point for drivers. In some embodiments, each driver can be assigned a gravity point. The gravity point can represent a point of maximum gravity, and the driver's territory can extend around the gravity point); dividing the plurality of initial routes into a plurality of segments to combine a plurality of nearby routes (James, Gravity Points, Paragraph 11, Lines 1-7, the routing module 200 can group all the stops received in operation block 405 according to the proximity of the points identified in operation block 415. For example, each point can be assigned a value, such as the cost value, based on its distance from the reference point. These calculations can be repeated until all the stops have been grouped so as to provide one group of stops for each vehicle and such that the costs associated with the groupings are also about the same), wherein each of the plurality of segments comprises a set of adjacent routes from among the plurality of initial routes (James, Summary, Paragraph 5, Lines 5-7, additionally, territories could be overlapped such that the radius of two adjacent territories overlap geographically such that two vehicles could be routed to the same place); identifying a second route such that geocoordinates of the node in the first route lies within the quadrilateral corresponding to the second route; (James, Routing Module Embodiments, Paragraph 5, Lines 5-7, additionally, territories could be overlapped such that the radius of two adjacent territories overlap geographically such that two vehicles could be routed to the same place) and generating a second set of routes, wherein the second set of routes is generated by swapping orders between different pairs of routes in the first set of routes; inserting an order from one route to another route in each pair of routes in the second set of routes (James, Summary, Paragraph 8, Lines 2-6, the associated routing algorithm can compare routing solutions for vehicles adjacent territories and recalculate routes to balance loads or costs amongst the vehicles in a more balanced approach, without the need for user to manually reset territorial boundaries). However, James does not explicitly disclose, some limitation of claim 1.
Nevertheless, Zhong who is in the same field of endeavor of planning for optimizing routes discloses, obtaining an optimal set of routes corresponding to the plurality of initial routes, by performing for each of the plurality of segments the steps of: creating an order matrix for the one or more orders (Zhong, Route Consistency, Paragraph 12, Lines 11-15, in one embodiment, an array or matrix may be used to categorize and easily reference the data regarding each grid segment 152, for each day during a reference period, and for each assigned driver, in the following steps:) wherein the order matrix indicates each of the one or more orders as being serviceable or non-serviceable (Zhong, Summary, Paragraph 9, Lines 1-4, any cell located outside any of the new core areas may be classified as a daily cell and assigned to the nearest assigned driver. Similarly, any stop located outside any of the new core areas or outside any of the daily cells may be classified as a daily stop and assigned to the nearest assigned stop driver); obtaining a first set of routes from the plurality of initial routes, based on data in the order matrix, wherein routes among the first set of routes are grouped based on proximity to form a plurality of pairs of routes (Zhong, A Mathematical Model for Route Consistency, Paragraph 1, Lines 1-5, in one embodiment, the present invention provides a method for measuring route consistency within a service territory using a mathematical model. There exists an opposing tension between route consistency and optimal route planning because route optimization requires flexibility (as opposed to consistency)) … (Zhong, Empirical Data and the Grid Method, Paragraph 8, Lines 11-15, compare a current day to the reference day. The route planning algorithm run for the current day produces a plurality of unassigned routes. a) For each of the assigned routes on the reference day:(i) find the one of the plurality of unassigned routes for the current day which has the maximum geographic overlap with the assigned route, wherein the geographic overlap is determined by calculating the area of the intersection between the convex hull of the assigned route and the convex hull of the unassigned route), wherein obtaining the first set of routes comprises: determining a quadrilateral corresponding to each route among a set of routes within the segment (0179, a first step may include dividing the service territory 20 or a portion thereof into a plurality of grid segments 152 using a grid 150. The grid 150 may be take any shape and may include grid segments 152 of any size or shape, including random shapes and including various sizes and shapes within the same grid 150), Wherein determining if the resultant set of routes is feasible comprises: calculating from an initial solution, an initial total distance of all routes (0350, the Intra-route Exchange procedure attempts to re-order the stop sequence within a given route in order to achieve better route cost. In one embodiment, the best route cost has the shortest total route duration), wherein the initial total distance is a distance travelled by all the nodes; confirming that the total distance of the resultant set of routes have lesser distance than the initial total distance of all the routes calculated from the initial solution when the nodes are moved between routes (0368, the objective for the SSP is to find a node tour that starts and ends at subset S0, that only has one node (the depot or hub 30), visits all nodes exactly once, and has a minimum total distance traveled); and replacing the initial solution with newly obtained resultant set of routes and updating the initial total distance (0350, the Inter-route Exchange procedure swaps a stop on one route with a stop on another route, to determine if the exchange reduces the total route cost, within the maximum workday duration constraint); and performing a local optimization on the updated first, second and third routes to obtain the first set of routes (0350, the Intra-route Exchange procedure attempts to re-order the stop sequence within a given route in order to achieve better route cost. In one embodiment, the best route cost has the shortest total route duration, within the maximum workday duration constraint), wherein the local optimization comprises swapping of one or more orders between the first, second and third routes such that a pre-defined delivery window constraint and hard or soft constraints related to deliveries, priorities are satisfied (0350, the Inter-route Exchange procedure swaps a stop on one route with a stop on another route, to determine if the exchange reduces the total route cost, within the maximum workday duration constraint), and total distance travelled in the routes is minimum (0350, in one embodiment, the best route cost has the shortest total route duration);
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine James and Zhong’s disclosures to enhance the
functionality of James system by integrating advanced feasibility checks and improving
boundaries. The matrix from Zhong would assign routes to ensure deliveries meet the appropriate time window. While the convex hull polygons would reduce the optimization search
space leading to faster route adjustments.
Justification for combining James and Zhong’s disclosures not only comes from the state
of the art but from Zhong (Zhong, Conclusion, Paragraph 2, Lines 4-7, one of ordinary skill in
the art may recognize that further combinations and permutations are possible. Accordingly,
this application is intended to embrace alterations, modifications). Though, Zhong still does not disclose some limitations of claim 1.
Nevertheless, Stefan who is in the same field of endeavor of large neighborhood search for the pickup and delivery discloses, updating the segment by including a pre-defined percentage of routes existing in the segment and by taking a pre-defined percentage of routes from remaining segments (Stefan, Parameters, Paragraph 2, Lines 1-5, in order to control the acceptance criteria we use two parameters, w and c. The weight adjustment algorithm is controlled by four parameters, σ1, σ2, σ3 and r. Finally we have to determine a noise rate η and a parameter ξ that controls how many requests we remove in each iteration. In each iteration, we chose a random number ρ that satisfies 4 ≤ ρ ≤ min(100,ξn), and remove ρ requests. We stop the search after 25000 LNS iterations as this resulted in a fair trade-off between time and quality).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine James and Stefan’s disclosures to enhance the
functionality of James system by improving its balance between local route retention and cross-
segment optimization. The percentage parameters ensure route stability within each segment and
encourage leniency for global improvements.
Justification for combining James, Zhong and Stefan’s disclosures not only comes from the state of the art but from James (James, Summary, Paragraph 12, Lines 2-5, the routing system can then apply an appropriate routing technique for finding an operable route for vehicles to follow in order to make the final list of predetermined stops. Such techniques can include routing techniques known as the traveling salesman algorithm, or other algorithms).
However, Stefan still does not disclose some limitations of claim 1.
Nevertheless, Kindervater who is in the same field of endeavor of route streamlining discloses, elements of the order matrix have a value as 1 when a vehicle reaches from order i to order j and service order j within delivery time windows (3.1 Preprocessing, the screening procedure is based on the following observation: if firstdesi denotes the first destination of a precedence relation for which both origin and destination lie beyond i, then the exchange of {i, i + 1} and { j, j + 1} with {i, j} and {i + 1, j + 1} is feasible if and only if j < firstdesi. The screening procedure first computes the values firstdesi and then constructs the feasibility matrix feas, i.e., feasij = 1), else have the value as 0 (3.1 Preprocessing, if j < firstdesi and feasij = 0 otherwise), exchanging the node in the first route with a node in the second route (2.2 Edge-exchange neighborhoods for multiple routes, two vertices from different routes are simultaneously placed into the other routes); identifying a third route and inserting the node in the second route into a minimum distance position of the third route (2.2 Edge-exchange neighborhoods for multiple routes, due to the computational intensity of searching cyclic transfer neighborhoods only b-cyclic k-transfers with only small numbers b and k are considered, i.e., b ≤ 3 and k ≤ 2.) … (3 TECHNIQUES TO HANDLE SIDE CONSTRAINTS, However, it should be clear in the end that the techniques presented can easily be used to produce an edge exchange algorithm that can handle any combination of side constraints for edge exchange neighborhoods involving either a single route or multiple routes), wherein inserting the node into the minimum distance position refers to the node placed into the third route in a position which yields a minimum distance (2.2 Edge-exchange neighborhoods for multiple routes, Gendreau, Hertz & Laporte [1994] propose an extension of the relocate neighborhood in which a vertex can also be inserted between the two vertices on the destination route that are nearest to it), wherein with insertion of the nodes, a first node, a second node and a third node are updated (2.2 Edge-exchange neighborhoods for multiple routes, Note that the vertex being relocated is inserted between two consecutive vertices on the destination route), and determining if a resultant set of routes with updated first, second, and third routes is feasible based on a calculated total distance for the resultant set of routes (3 TECHNIQUES TO HANDLE SIDE CONSTRAINTS, as opposed to the TSP where one only has to test whether the exchange is profitable and one does not have to bother about feasibility. A 2 exchange, for instance, will reverse the path (i + 1, . . . , j), which means that one has to check the feasibility of at least all the vertices on the new path with respect to those constraints).
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified James, Zhong and Stefan’s disclosure to incorporate the teachings of Kindervater for the benefit of not having to re-evaluate travel time. Instead the system can go directly from order to order because the matrix is pre computed as being feasible or not feasible automatically. However, Kindervater still does not explicitly disclose some limitations of claim 1.
Nevertheless, Wang who is in the same field of endeavor of track planning algorithms discloses, routes are identified as the set of adjacent routes by using a pruning technique (Simulation Experiment, Paragraph 5, the target boundary box in the optimization method has the main function of node pruning), in which a number of neighbors for a node or a consecutive set of nodes or customer locations in a route for an applicable move is determined by extreme latitude and longitude coordinates of the route that form a rectangle around the route (2, technical scheme, Paragraph 12, carrying out destination-free Dijkstra search on the nodes to obtain nodes in Dijkstra search mapping in each search direction of the nodes; constructing a bounding box of each search direction according to the minimum circumscribed rectangle of the nodes in the Dijkstra search map in each search direction; and selecting a search direction boundary box containing a ship target point as a target boundary box of the current node), wherein the neighbor for the node or the consecutive set of nodes or the customer locations in the route is selected only if the co-ordinate of the node lies within the extreme latitude and longitude co-ordinates of the neighbor (2, technical scheme, Paragraph 1, when the neighborhood of each node in the traversal set C is searched for the next feasible node, selecting the node which is in the non-obstacle area and the current node target boundary box in the current node neighborhood as the next feasible node; and updating the set O to judge the waypoints according to the next feasible node).
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified James, Zhong, Stefan, and Kindervater’s disclosure to incorporate the teachings of Wang for the benefit of having rectangular bounding boxes for pruning multiple adjacent routes. This algorithm would serve as the basis to simplify and reduce travel time and distances by combining routes that overlap. However, Wang still down not disclose some limitations of claim 1.
Nevertheless, Huang who is in the same field of endeavor of route comparisons based on GPS coordinates and bounding boxes discloses, the quadrilateral has (i) minimum latitude, (ii) minimum longitude, (iii) maximum latitude, and (iv) maximum longitude (IV. RAPID ROUTE COMPARISON, a bounding box can be constructed from the leftbottom vertex and the right-top vertex as shown in Fig. 7. The left-bottom vertex (V_LB) is a coordinate with the minimum latitude and longitude in a route, and the righttop vertex (V_RT) is a coordinate with the maximum latitude and longitude in a route), as four corner points, identified based on geocoordinates of nodes in the route a bounding box can be defined as, 𝐵(𝑟) = {𝑉𝐿𝐵, 𝑉𝑅𝑇}, See Figure 7.
PNG
media_image1.png
403
549
media_image1.png
Greyscale
Fetching geocoordinates of the node in a first route in the set of routes (III. INTERSECTION ROUTES, a route is composed of multiple segments from the beginning to the end, denoted as {𝑠1, ⋯ , 𝑠𝑖}, where 𝑠𝑖 consists of many pairs of latitude and longitude coordinates); identifying a second route such that geocoordinates of the node in the first route lies within the quadrilateral corresponding to the second route (IV. RAPID ROUTE COMPARISON, 𝐵(𝑟1) is the bounding box of 𝑟1 and 𝐵(𝑟2) is the bounding box of 𝑟2. If 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝 is not an empty set, first remove the pairs of coordinates of each route which are in the range of 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝. Next, coordinates of two routes in the 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝 are compared one by one to find the overlapped route).
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified James, Zhong, Stefan, Kindervater and Wang’s disclosure to incorporate the teachings of Huang for the benefit of having explicit min and max coordinates for the corner points of identified nodes in a route. This allows for improved efficiency when comparing two routes to eliminate most of the coordinates in a route.
Further justification for combining these disclosures not only comes from the state of the art but from Huang (VI. CONCLUSION, the proposed t-BB and n-BB can be also used in other geographic information systems (e.g., Apple Map and Bing Map) and achieve rapid and accurate result of comparison of two routes). However, even with Huang there is a missing limitation explicitly stated in claim 1.
Nevertheless, Tarawneh who is in the same field of endeavor of solving the capacitated vehicle routing problem discloses, the nodes being sorted based upon a minimum angle from the depot and starting with an angle as 0 the plurality of initial routes are created with minimum angle nodes until a capacity constraint is satisfied (1. Introduction, A “sweep” is then started from angle 0 in the clockwise direction, including as many locations as possible until the capacity of a certain vehicle is exhausted), wherein once the route is completed the step of creating the plurality of initial routes is repeated until all the nodes are added to the routes (1. Introduction, the process is then repeated, this time starting from the angular position where the previous iteration ended, to determine the delivery sector for the next vehicle and so on);
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified James, Zhong, Stefan, Kindervater, Wang and Huang’s disclosure to incorporate the teachings of Tarawneh for the benefit of having reduced search space and faster convergence for optimization for constructing feasible routes by sorting customer nodes by their polar angle relative to the depot.
Further justification for combining these disclosures not only comes from the state of the art but from Tarawneh (5. Conclusion and Future Work, Future work includes applying this approach for larger instances where different demands of locations are taken, and different capacities of vehicles are considered).
Regarding claim 2, James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh disclose, the method of claim 1, as discussed supra. Additionally, James discloses, the swapping of the orders is performed only if a resulting route satisfies a pre-defined delivery window constraint and reduces total distance travelled in the routes at least by a pre-defined percentage (James, Overall Routing System Process, Paragraph 8, Lines 2-6, the feasible routes can be generated based on shortest distance or estimated transit time. Feasible routes can also include routes having a characteristic within a predefined percentage of the “best” route, such as a route having a time or distance within about 1%, within about 5%, or within about 10% of the calculated best route).
Regarding claim 3, James, Zhong, Stefan, Kindervater and Wang disclose, the method of claim 1, as discussed supra. Additionally, James discloses, the insertion of routes is performed only if a resultant route satisfies a delivery window constraint and reduces total distance travelled in the routes at least by a pre-defined percentage (James, Gravity Points, Paragraph 5, Lines 1-5, in some embodiments, the gravity point therefore defines a center of a cost field akin to a gravitational field surrounding a mass of matter. The routing algorithm used by the routing module can take this gravity field into account as part of an optimization problem to determine whether to assign a driver to a stop (or vice versa)) … (James, Overall Routing System Process, Paragraph 8, Lines 2-6, the feasible routes can be generated based on shortest distance or estimated transit time. Feasible routes can also include routes having a characteristic within a predefined percentage of the “best” route, such as a route having a time or distance within about 1%, within about 5%, or within about 10% of the calculated best route).
Regarding claim 5, James discloses, A system for vehicle route optimization, comprising: one or more hardware processors; a communication interface; and a memory storing a plurality of instructions, wherein the plurality of instructions when executed, cause the one or more hardware processors to: obtaining, via one or more hardware processors, information on (i) a network of customers (0052, (e.g., the fleet vehicle type to be routed, service level selected by the requestor, customer identification code, etc.) for a particular fleet of vehicles), wherein the network of customers comprises nodes corresponding to a plurality of customer locations and a depot, and edges representing connections between the customer locations, (ii) distance between each pair of customer locations among the plurality of customer locations (James, Distance Estimation, Paragraph 2, Lines 4-7, nodes in the tree represent vehicle stops and edges represent cost between the stops (such as driving time, fuel costs, distance, wait time, combinations of the same, or the like). A user can request multiple distance estimates to be run with different routes), (iii) one or more orders received from one or more of the customers from the network of customers (James, Vehicle Management System Overview, Paragraph 2, Lines 6-15, users can access and monitor vehicle information obtained from one or more of the in-vehicle devices 105 by the vehicle management system 150. Such vehicle status information can include data on vehicle routes used, stops, speed, vehicle feature usage (such as power takeoff device usage), driver behavior and performance, vehicle emissions, vehicle maintenance, energy usage, and the like), (iv) service start time,(v) service end time, (James, Exclusion Zones Embodiments, Paragraph 1, Lines 1-8, the routing module can delay the start of a vehicle's route if it would be more efficient to do so. As an illustration, an exclusion zone might specify that certain vehicles cannot enter the zone from 9 am to 10 am. If a driver of such a vehicle is ordinarily scheduled to start his route at 8 am but has to go through the exclusion zone), and(vi) servicing time (James, Routing Module Embodiments, Paragraph 6, Lines 2-6, the feasible routes can be determined using one or more initial searching algorithms based on one or more initial criteria, factors or variables (e.g., distance and/or estimated transit time) to trim down the search space to exclude unreasonable routes); creating a plurality of initial routes based on the network of customers (James, Gravity Points, Paragraph 3, Lines 1-3, the vehicle management system 150 can instead provide functionality for users to define a predetermined point within a drivers territory), by considering the depot as a center coordinate and by calculating polar angles of the nodes in the network of customers, to assign the nodes to the plurality of initial routes (James, Gravity Points, Paragraph 3, Lines 3-6, which can also be considered a gravity point for drivers. In some embodiments, each driver can be assigned a gravity point. The gravity point can represent a point of maximum gravity, and the driver's territory can extend around the gravity point); dividing the plurality of initial routes into a plurality of segments to combine a plurality of nearby routes (James, Gravity Points, Paragraph 11, Lines 1-7, the routing module 200 can group all the stops received in operation block 405 according to the proximity of the points identified in operation block 415. For example, each point can be assigned a value, such as the cost value, based on its distance from the reference point. These calculations can be repeated until all the stops have been grouped so as to provide one group of stops for each vehicle and such that the costs associated with the groupings are also about the same), wherein each of the plurality of segments comprises a set of adjacent routes from among the plurality of initial routes (James, Summary, Paragraph 5, Lines 5-7, additionally, territories could be overlapped such that the radius of two adjacent territories overlap geographically such that two vehicles could be routed to the same place); identifying a second route such that geocoordinates of the node in the first route lies within the quadrilateral corresponding to the second route; (James, Routing Module Embodiments, Paragraph 5, Lines 5-7, additionally, territories could be overlapped such that the radius of two adjacent territories overlap geographically such that two vehicles could be routed to the same place) and generating a second set of routes, wherein the second set of routes is generated by swapping orders between different pairs of routes in the first set of routes; inserting an order from one route to another route in each pair of routes in the second set of routes (James, Summary, Paragraph 8, Lines 2-6, the associated routing algorithm can compare routing solutions for vehicles adjacent territories and recalculate routes to balance loads or costs amongst the vehicles in a more balanced approach, without the need for user to manually reset territorial boundaries). However, James does not explicitly disclose, some limitation of claim 1.
Nevertheless, Zhong who is in the same field of endeavor of planning for optimizing routes discloses, obtaining an optimal set of routes corresponding to the plurality of initial routes, by performing for each of the plurality of segments the steps of: creating an order matrix for the one or more orders (Zhong, Route Consistency, Paragraph 12, Lines 11-15, in one embodiment, an array or matrix may be used to categorize and easily reference the data regarding each grid segment 152, for each day during a reference period, and for each assigned driver, in the following steps:) wherein the order matrix indicates each of the one or more orders as being serviceable or non-serviceable (Zhong, Summary, Paragraph 9, Lines 1-4, any cell located outside any of the new core areas may be classified as a daily cell and assigned to the nearest assigned driver. Similarly, any stop located outside any of the new core areas or outside any of the daily cells may be classified as a daily stop and assigned to the nearest assigned stop driver); obtaining a first set of routes from the plurality of initial routes, based on data in the order matrix, wherein routes among the first set of routes are grouped based on proximity to form a plurality of pairs of routes (Zhong, A Mathematical Model for Route Consistency, Paragraph 1, Lines 1-5, in one embodiment, the present invention provides a method for measuring route consistency within a service territory using a mathematical model. There exists an opposing tension between route consistency and optimal route planning because route optimization requires flexibility (as opposed to consistency)) … (Zhong, Empirical Data and the Grid Method, Paragraph 8, Lines 11-15, compare a current day to the reference day. The route planning algorithm run for the current day produces a plurality of unassigned routes. a) For each of the assigned routes on the reference day:(i) find the one of the plurality of unassigned routes for the current day which has the maximum geographic overlap with the assigned route, wherein the geographic overlap is determined by calculating the area of the intersection between the convex hull of the assigned route and the convex hull of the unassigned route), wherein obtaining the first set of routes comprises: determining a quadrilateral corresponding to each route among a set of routes within the segment (0179, a first step may include dividing the service territory 20 or a portion thereof into a plurality of grid segments 152 using a grid 150. The grid 150 may be take any shape and may include grid segments 152 of any size or shape, including random shapes and including various sizes and shapes within the same grid 150), Wherein determining if the resultant set of routes is feasible comprises: calculating from an initial solution, an initial total distance of all routes (0350, the Intra-route Exchange procedure attempts to re-order the stop sequence within a given route in order to achieve better route cost. In one embodiment, the best route cost has the shortest total route duration), wherein the initial total distance is a distance travelled by all the nodes; confirming that the total distance of the resultant set of routes have lesser distance than the initial total distance of all the routes calculated from the initial solution when the nodes are moved between routes (0368, the objective for the SSP is to find a node tour that starts and ends at subset S0, that only has one node (the depot or hub 30), visits all nodes exactly once, and has a minimum total distance traveled); and replacing the initial solution with newly obtained resultant set of routes and updating the initial total distance (0350, the Inter-route Exchange procedure swaps a stop on one route with a stop on another route, to determine if the exchange reduces the total route cost, within the maximum workday duration constraint); and performing a local optimization on the updated first, second and third routes to obtain the first set of routes (0350, the Intra-route Exchange procedure attempts to re-order the stop sequence within a given route in order to achieve better route cost. In one embodiment, the best route cost has the shortest total route duration, within the maximum workday duration constraint), wherein the local optimization comprises swapping of one or more orders between the first, second and third routes such that a pre-defined delivery window constraint and hard or soft constraints related to deliveries, priorities are satisfied (0350, the Inter-route Exchange procedure swaps a stop on one route with a stop on another route, to determine if the exchange reduces the total route cost, within the maximum workday duration constraint), and total distance travelled in the routes is minimum (0350, in one embodiment, the best route cost has the shortest total route duration).
Additionally, Stefan who is in the same field of endeavor of large neighborhood search for the pickup and delivery discloses, updating the segment by including a pre-defined percentage of routes existing in the segment and by taking a pre-defined percentage of routes from remaining segments (Stefan, Parameters, Paragraph 2, Lines 1-5, in order to control the acceptance criteria we use two parameters, w and c. The weight adjustment algorithm is controlled by four parameters, σ1, σ2, σ3 and r. Finally we have to determine a noise rate η and a parameter ξ that controls how many requests we remove in each iteration. In each iteration, we chose a random number ρ that satisfies 4 ≤ ρ ≤ min(100,ξn), and remove ρ requests. We stop the search after 25000 LNS iterations as this resulted in a fair trade-off between time and quality).
Additionally, Kindervater who is in the same field of endeavor of route streamlining discloses, elements of the order matrix have a value as 1 when a vehicle reaches from order i to order j and service order j within delivery time windows (3.1 Preprocessing, the screening procedure is based on the following observation: if firstdesi denotes the first destination of a precedence relation for which both origin and destination lie beyond i, then the exchange of {i, i + 1} and { j, j + 1} with {i, j} and {i + 1, j + 1} is feasible if and only if j < firstdesi. The screening procedure first computes the values firstdesi and then constructs the feasibility matrix feas, i.e., feasij = 1), else have the value as 0 (3.1 Preprocessing, if j < firstdesi and feasij = 0 otherwise), exchanging the node in the first route with a node in the second route (2.2 Edge-exchange neighborhoods for multiple routes, two vertices from different routes are simultaneously placed into the other routes); identifying a third route and inserting the node in the second route into a minimum distance position of the third route (2.2 Edge-exchange neighborhoods for multiple routes, due to the computational intensity of searching cyclic transfer neighborhoods only b-cyclic k-transfers with only small numbers b and k are considered, i.e., b ≤ 3 and k ≤ 2.) … (3 TECHNIQUES TO HANDLE SIDE CONSTRAINTS, However, it should be clear in the end that the techniques presented can easily be used to produce an edge exchange algorithm that can handle any combination of side constraints for edge exchange neighborhoods involving either a single route or multiple routes), wherein inserting the node into the minimum distance position refers to the node placed into the third route in a position which yields a minimum distance (2.2 Edge-exchange neighborhoods for multiple routes, Gendreau, Hertz & Laporte [1994] propose an extension of the relocate neighborhood in which a vertex can also be inserted between the two vertices on the destination route that are nearest to it), wherein with insertion of the nodes, a first node, a second node and a third node are updated (2.2 Edge-exchange neighborhoods for multiple routes, Note that the vertex being relocated is inserted between two consecutive vertices on the destination route), and determining if a resultant set of routes with updated first, second, and third routes is feasible based on a calculated total distance for the resultant set of routes (3 TECHNIQUES TO HANDLE SIDE CONSTRAINTS, as opposed to the TSP where one only has to test whether the exchange is profitable and one does not have to bother about feasibility. A 2 exchange, for instance, will reverse the path (i + 1, . . . , j), which means that one has to check the feasibility of at least all the vertices on the new path with respect to those constraints).
Additionally, Huang who is in the same field of endeavor of route comparisons based on GPS coordinates and bounding boxes discloses, the quadrilateral has (i) minimum latitude, (ii) minimum longitude, (iii) maximum latitude, and (iv) maximum longitude (IV. RAPID ROUTE COMPARISON, a bounding box can be constructed from the leftbottom vertex and the right-top vertex as shown in Fig. 7. The left-bottom vertex (V_LB) is a coordinate with the minimum latitude and longitude in a route, and the righttop vertex (V_RT) is a coordinate with the maximum latitude and longitude in a route), as four corner points, identified based on geocoordinates of nodes in the route a bounding box can be defined as, 𝐵(𝑟) = {𝑉𝐿𝐵, 𝑉𝑅𝑇}, See Figure 7. Fetching geocoordinates of the node in a first route in the set of routes (III. INTERSECTION ROUTES, a route is composed of multiple segments from the beginning to the end, denoted as {𝑠1, ⋯ , 𝑠𝑖}, where 𝑠𝑖 consists of many pairs of latitude and longitude coordinates); identifying a second route such that geocoordinates of the node in the first route lies within the quadrilateral corresponding to the second route (IV. RAPID ROUTE COMPARISON, 𝐵(𝑟1) is the bounding box of 𝑟1 and 𝐵(𝑟2) is the bounding box of 𝑟2. If 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝 is not an empty set, first remove the pairs of coordinates of each route which are in the range of 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝. Next, coordinates of two routes in the 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝 are compared one by one to find the overlapped route).
Additionally, Tarawneh who is in the same field of endeavor of solving the capacitated vehicle routing problem discloses, the nodes being sorted based upon a minimum angle from the depot and starting with an angle as 0 the plurality of initial routes are created with minimum angle nodes until a capacity constraint is satisfied (1. Introduction, A “sweep” is then started from angle 0 in the clockwise direction, including as many locations as possible until the capacity of a certain vehicle is exhausted), wherein once the route is completed the step of creating the plurality of initial routes is repeated until all the nodes are added to the routes (1. Introduction, the process is then repeated, this time starting from the angular position where the previous iteration ended, to determine the delivery sector for the next vehicle and so on).
Regarding claim 6 James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh disclose, the system as claimed in claim 5 as discussed supra. Additionally, James discloses, hardware processors are configured to perform swapping of the orders is performed only if a resulting route satisfies a pre-defined delivery window constraint and reduces total distance travelled in the routes at least by a pre-defined percentage (James, Overall Routing System Process, Paragraph 8, Lines 2-6, the feasible routes can be generated based on shortest distance or estimated transit time. Feasible routes can also include routes having a characteristic within a predefined percentage of the “best” route, such as a route having a time or distance within about 1%, within about 5%, or within about 10% of the calculated best route).
Regarding claim 7 James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh disclose, the system as claimed in claim 5 as discussed supra. Additionally, James discloses, the one or more hardware processors are configured to perform the insertion of routes is performed only if a resultant route satisfies a delivery window constraint and reduces total distance travelled in the routes at least by a pre-defined percentage (James, Gravity Points, Paragraph 5, Lines 1-5, in some embodiments, the gravity point therefore defines a center of a cost field akin to a gravitational field surrounding a mass of matter. The routing algorithm used by the routing module can take this gravity field into account as part of an optimization problem to determine whether to assign a driver to a stop (or vice versa)) … (James, Overall Routing System Process, Paragraph 8, Lines 2-6, the feasible routes can be generated based on shortest distance or estimated transit time. Feasible routes can also include routes having a characteristic within a predefined percentage of the “best” route, such as a route having a time or distance within about 1%, within about 5%, or within about 10% of the calculated best route).
Regarding claim 9, James discloses One or more non-transitory machine-readable information storage mediums comprising one or more instructions (0064, the parameter database 240. The classifications can be stored using a look-up table or other storage approach to facilitate access of the classification data for use in calculating routes), which when executed by one or more hardware processors cause: obtaining information on (i) a network of customers, (0052, (e.g., the fleet vehicle type to be routed, service level selected by the requestor, customer identification code, etc.) for a particular fleet of vehicles), wherein the network of customers comprises node corresponding to a plurality of customer locations and a depot, and edges representing connections between the customer locations, (ii) distance between each pair of customer locations among the plurality of customer locations (James, Distance Estimation, Paragraph 2, Lines 4-7, nodes in the tree represent vehicle stops and edges represent cost between the stops (such as driving time, fuel costs, distance, wait time, combinations of the same, or the like). A user can request multiple distance estimates to be run with different routes), (iii) one or more orders received from one or more of the customers from the network of customers (James, Vehicle Management System Overview, Paragraph 2, Lines 6-15, users can access and monitor vehicle information obtained from one or more of the in-vehicle devices 105 by the vehicle management system 150. Such vehicle status information can include data on vehicle routes used, stops, speed, vehicle feature usage (such as power takeoff device usage), driver behavior and performance, vehicle emissions, vehicle maintenance, energy usage, and the like), (iv) service start time,(v) service end time, (James, Exclusion Zones Embodiments, Paragraph 1, Lines 1-8, the routing module can delay the start of a vehicle's route if it would be more efficient to do so. As an illustration, an exclusion zone might specify that certain vehicles cannot enter the zone from 9 am to 10 am. If a driver of such a vehicle is ordinarily scheduled to start his route at 8 am but has to go through the exclusion zone), and(vi) servicing time (James, Routing Module Embodiments, Paragraph 6, Lines 2-6, the feasible routes can be determined using one or more initial searching algorithms based on one or more initial criteria, factors or variables (e.g., distance and/or estimated transit time) to trim down the search space to exclude unreasonable routes); creating a plurality of initial routes based on the network of customers (James, Gravity Points, Paragraph 3, Lines 1-3, the vehicle management system 150 can instead provide functionality for users to define a predetermined point within a drivers territory), by considering the depot as a center coordinate and by calculating polar angles of the nodes in the network of customers, to assign the nodes to the plurality of initial routes (James, Gravity Points, Paragraph 3, Lines 3-6, which can also be considered a gravity point for drivers. In some embodiments, each driver can be assigned a gravity point. The gravity point can represent a point of maximum gravity, and the driver's territory can extend around the gravity point); dividing the plurality of initial routes into a plurality of segments to combine a plurality of nearby routes (James, Gravity Points, Paragraph 11, Lines 1-7, the routing module 200 can group all the stops received in operation block 405 according to the proximity of the points identified in operation block 415. For example, each point can be assigned a value, such as the cost value, based on its distance from the reference point. These calculations can be repeated until all the stops have been grouped so as to provide one group of stops for each vehicle and such that the costs associated with the groupings are also about the same), wherein each of the plurality of segments comprises a set of adjacent routes from among the plurality of initial routes (James, Summary, Paragraph 5, Lines 5-7, additionally, territories could be overlapped such that the radius of two adjacent territories overlap geographically such that two vehicles could be routed to the same place); identifying a second route such that geocoordinates of the node in the first route lies within the quadrilateral corresponding to the second route; (James, Routing Module Embodiments, Paragraph 5, Lines 5-7, additionally, territories could be overlapped such that the radius of two adjacent territories overlap geographically such that two vehicles could be routed to the same place) and generating a second set of routes, wherein the second set of routes is generated by swapping orders between different pairs of routes in the first set of routes; inserting an order from one route to another route in each pair of routes in the second set of routes (James, Summary, Paragraph 8, Lines 2-6, the associated routing algorithm can compare routing solutions for vehicles adjacent territories and recalculate routes to balance loads or costs amongst the vehicles in a more balanced approach, without the need for user to manually reset territorial boundaries). However, James does not explicitly disclose, some limitation of claim 1.
Nevertheless, Zhong who is in the same field of endeavor of planning for optimizing routes discloses, obtaining an optimal set of routes corresponding to the plurality of initial routes, by performing for each of the plurality of segments the steps of: creating an order matrix for the one or more orders (Zhong, Route Consistency, Paragraph 12, Lines 11-15, in one embodiment, an array or matrix may be used to categorize and easily reference the data regarding each grid segment 152, for each day during a reference period, and for each assigned driver, in the following steps:) wherein the order matrix indicates each of the one or more orders as being serviceable or non-serviceable (Zhong, Summary, Paragraph 9, Lines 1-4, any cell located outside any of the new core areas may be classified as a daily cell and assigned to the nearest assigned driver. Similarly, any stop located outside any of the new core areas or outside any of the daily cells may be classified as a daily stop and assigned to the nearest assigned stop driver); obtaining a first set of routes from the plurality of initial routes, based on data in the order matrix, wherein routes among the first set of routes are grouped based on proximity to form a plurality of pairs of routes (Zhong, A Mathematical Model for Route Consistency, Paragraph 1, Lines 1-5, in one embodiment, the present invention provides a method for measuring route consistency within a service territory using a mathematical model. There exists an opposing tension between route consistency and optimal route planning because route optimization requires flexibility (as opposed to consistency)) … (Zhong, Empirical Data and the Grid Method, Paragraph 8, Lines 11-15, compare a current day to the reference day. The route planning algorithm run for the current day produces a plurality of unassigned routes. a) For each of the assigned routes on the reference day:(i) find the one of the plurality of unassigned routes for the current day which has the maximum geographic overlap with the assigned route, wherein the geographic overlap is determined by calculating the area of the intersection between the convex hull of the assigned route and the convex hull of the unassigned route), wherein obtaining the first set of routes comprises: determining a quadrilateral corresponding to each route among a set of routes within the segment (0179, a first step may include dividing the service territory 20 or a portion thereof into a plurality of grid segments 152 using a grid 150. The grid 150 may be take any shape and may include grid segments 152 of any size or shape, including random shapes and including various sizes and shapes within the same grid 150), Wherein determining if the resultant set of routes is feasible comprises: calculating from an initial solution, an initial total distance of all routes (0350, the Intra-route Exchange procedure attempts to re-order the stop sequence within a given route in order to achieve better route cost. In one embodiment, the best route cost has the shortest total route duration), wherein the initial total distance is a distance travelled by all the nodes; confirming that the total distance of the resultant set of routes have lesser distance than the initial total distance of all the routes calculated from the initial solution when the nodes are moved between routes (0368, the objective for the SSP is to find a node tour that starts and ends at subset S0, that only has one node (the depot or hub 30), visits all nodes exactly once, and has a minimum total distance traveled); and replacing the initial solution with newly obtained resultant set of routes and updating the initial total distance (0350, the Inter-route Exchange procedure swaps a stop on one route with a stop on another route, to determine if the exchange reduces the total route cost, within the maximum workday duration constraint); and performing a local optimization on the updated first, second and third routes to obtain the first set of routes (0350, the Intra-route Exchange procedure attempts to re-order the stop sequence within a given route in order to achieve better route cost. In one embodiment, the best route cost has the shortest total route duration, within the maximum workday duration constraint), wherein the local optimization comprises swapping of one or more orders between the first, second and third routes such that a pre-defined delivery window constraint and hard or soft constraints related to deliveries, priorities are satisfied (0350, the Inter-route Exchange procedure swaps a stop on one route with a stop on another route, to determine if the exchange reduces the total route cost, within the maximum workday duration constraint), and total distance travelled in the routes is minimum (0350, in one embodiment, the best route cost has the shortest total route duration).
Additionally, Stefan who is in the same field of endeavor of large neighborhood search for the pickup and delivery discloses, updating the segment by including a pre-defined percentage of routes existing in the segment and by taking a pre-defined percentage of routes from remaining segments (Stefan, Parameters, Paragraph 2, Lines 1-5, in order to control the acceptance criteria we use two parameters, w and c. The weight adjustment algorithm is controlled by four parameters, σ1, σ2, σ3 and r. Finally we have to determine a noise rate η and a parameter ξ that controls how many requests we remove in each iteration. In each iteration, we chose a random number ρ that satisfies 4 ≤ ρ ≤ min(100,ξn), and remove ρ requests. We stop the search after 25000 LNS iterations as this resulted in a fair trade-off between time and quality).
Additionally, Kindervater who is in the same field of endeavor of route streamlining discloses, elements of the order matrix have a value as 1 when a vehicle reaches from order i to order j and service order j within delivery time windows (3.1 Preprocessing, the screening procedure is based on the following observation: if firstdesi denotes the first destination of a precedence relation for which both origin and destination lie beyond i, then the exchange of {i, i + 1} and { j, j + 1} with {i, j} and {i + 1, j + 1} is feasible if and only if j < firstdesi. The screening procedure first computes the values firstdesi and then constructs the feasibility matrix feas, i.e., feasij = 1), else have the value as 0 (3.1 Preprocessing, if j < firstdesi and feasij = 0 otherwise), exchanging the node in the first route with a node in the second route (2.2 Edge-exchange neighborhoods for multiple routes, two vertices from different routes are simultaneously placed into the other routes); identifying a third route and inserting the node in the second route into a minimum distance position of the third route (2.2 Edge-exchange neighborhoods for multiple routes, due to the computational intensity of searching cyclic transfer neighborhoods only b-cyclic k-transfers with only small numbers b and k are considered, i.e., b ≤ 3 and k ≤ 2.) … (3 TECHNIQUES TO HANDLE SIDE CONSTRAINTS, However, it should be clear in the end that the techniques presented can easily be used to produce an edge exchange algorithm that can handle any combination of side constraints for edge exchange neighborhoods involving either a single route or multiple routes), wherein inserting the node into the minimum distance position refers to the node placed into the third route in a position which yields a minimum distance (2.2 Edge-exchange neighborhoods for multiple routes, Gendreau, Hertz & Laporte [1994] propose an extension of the relocate neighborhood in which a vertex can also be inserted between the two vertices on the destination route that are nearest to it), wherein with insertion of the nodes, a first node, a second node and a third node are updated (2.2 Edge-exchange neighborhoods for multiple routes, Note that the vertex being relocated is inserted between two consecutive vertices on the destination route), and determining if a resultant set of routes with updated first, second, and third routes is feasible based on a calculated total distance for the resultant set of routes (3 TECHNIQUES TO HANDLE SIDE CONSTRAINTS, as opposed to the TSP where one only has to test whether the exchange is profitable and one does not have to bother about feasibility. A 2 exchange, for instance, will reverse the path (i + 1, . . . , j), which means that one has to check the feasibility of at least all the vertices on the new path with respect to those constraints).
Additionally, Huang who is in the same field of endeavor of route comparisons based on GPS coordinates and bounding boxes discloses, the quadrilateral has (i) minimum latitude, (ii) minimum longitude, (iii) maximum latitude, and (iv) maximum longitude (IV. RAPID ROUTE COMPARISON, a bounding box can be constructed from the leftbottom vertex and the right-top vertex as shown in Fig. 7. The left-bottom vertex (V_LB) is a coordinate with the minimum latitude and longitude in a route, and the righttop vertex (V_RT) is a coordinate with the maximum latitude and longitude in a route), as four corner points, identified based on geocoordinates of nodes in the route a bounding box can be defined as, 𝐵(𝑟) = {𝑉𝐿𝐵, 𝑉𝑅𝑇}, See Figure 7. Fetching geocoordinates of the node in a first route in the set of routes (III. INTERSECTION ROUTES, a route is composed of multiple segments from the beginning to the end, denoted as {𝑠1, ⋯ , 𝑠𝑖}, where 𝑠𝑖 consists of many pairs of latitude and longitude coordinates); identifying a second route such that geocoordinates of the node in the first route lies within the quadrilateral corresponding to the second route (IV. RAPID ROUTE COMPARISON, 𝐵(𝑟1) is the bounding box of 𝑟1 and 𝐵(𝑟2) is the bounding box of 𝑟2. If 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝 is not an empty set, first remove the pairs of coordinates of each route which are in the range of 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝. Next, coordinates of two routes in the 𝑆𝑜𝑣𝑒𝑟𝑙𝑎𝑝 are compared one by one to find the overlapped route).
Additionally, Tarawneh who is in the same field of endeavor of solving the capacitated vehicle routing problem discloses, the nodes being sorted based upon a minimum angle from the depot and starting with an angle as 0 the plurality of initial routes are created with minimum angle nodes until a capacity constraint is satisfied (1. Introduction, A “sweep” is then started from angle 0 in the clockwise direction, including as many locations as possible until the capacity of a certain vehicle is exhausted), wherein once the route is completed the step of creating the plurality of initial routes is repeated until all the nodes are added to the routes (1. Introduction, the process is then repeated, this time starting from the angular position where the previous iteration ended, to determine the delivery sector for the next vehicle and so on).
Regarding claim 10, James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh disclose, the one or more non-transitory machine-readable information storage mediums of claim 9, as discussed supra. Additionally, James discloses, swapping of the orders is performed only if a resulting route satisfies a pre-defined delivery window constraint and reduces total distance travelled in the routes at least by a pre-defined percentage (James, Overall Routing System Process, Paragraph 8, Lines 2-6, the feasible routes can be generated based on shortest distance or estimated transit time. Feasible routes can also include routes having a characteristic within a predefined percentage of the “best” route, such as a route having a time or distance within about 1%, within about 5%, or within about 10% of the calculated best route).
Regarding claim 11, James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh disclose, the one or more non-transitory machine-readable information storage mediums of claim 9, as discussed supra. Additionally, James discloses, the insertion of routes is performed only if a resultant route satisfies a delivery window constraint and reduces total distance travelled in the routes at least by a pre-defined percentage (James, Gravity Points, Paragraph 5, Lines 1-5, in some embodiments, the gravity point therefore defines a center of a cost field akin to a gravitational field surrounding a mass of matter. The routing algorithm used by the routing module can take this gravity field into account as part of an optimization problem to determine whether to assign a driver to a stop (or vice versa)) … (James, Overall Routing System Process, Paragraph 8, Lines 2-6, the feasible routes can be generated based on shortest distance or estimated transit time. Feasible routes can also include routes having a characteristic within a predefined percentage of the “best” route, such as a route having a time or distance within about 1%, within about 5%, or within about 10% of the calculated best route).
Claim 13 is rejected under 35 U.S.C. 103 as being unpatentable over James et al. (US20130096815A1) in view of Zhong (US7660651B2), further in view of Stefan et al. (An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows), further in view of Kindervater et al. (Vehicle Routing 2 Handling Side Constraints), further in view of Wang et al. (CN110006430B), further in view of Tarawneh et al. (Solving Capacitated Vehicle Routing Problem Using Two Phase Heuristic Method), further in view of Huang et al. (Rapid Route Comparison Based on GPS Coordinates and Bounding Boxes), further in view of Tarawneh et al. (Solving Capacitated Vehicle Routing Problem Using Two Phase Heuristic Method), further in view of Kupriyanova (A Vehicle Routing Problem with Time Windows and Shift Time Limits).
Regarding claim 13, James, Zhong, Stefan, Kindervater, Wang, Tarawneh, and Huang disclose the method of claim 1 as discussed supra. Additionally, Kupriyanova who is in the same field of endeavor of solving the vehicle routing problem with time windows discloses a vehicle starts from the depot (Chapter 2. Theory, Constraints (2.3)-(2.4) state that each route starts and terminates at the depot), and each customer is visited only once by any one of one or more vehicles (Chapter 2. Theory, split deliveries and multiple visits are not allowed, i.e. each customer must be serviced by exactly one vehicle), and sum of a demand taken by the vehicle does not exceed capacity (Chapter 2. Theory, Constraints (2.3)-(2.4) state that each route starts and terminates at the depot. Constraints (2.5) specify that each customer is visited by exactly one vehicle. Constraints (2.6) are the capacity constraints for the vehicles), wherein servicing time si, at each customer point is between the service start time, ssi and the service end time, se,[ssi< si< sei or as applicable with and without delivery windows (Chapter 2. Theory, The service time for customer i is denoted si and servicing customer i must begin within a time window [Ei, Li], where Ei is the earliest allowable time and Li is the latest allowable Time), wherein the vehicle arriving early waits till ssi to start service and the vehicle departs immediately from customer location after servicing customer i (Chapter 2. Theory, if the vehicle arrives at the customer site before the earliest allowable time, it must wait until the time window opens) … (the arrival time compatibility between a pair of customers and work as follows: Let C be a large constant. If xijk = 0, the constraint is not binding. However, if customer j is serviced directly after customer i, i.e. xijk = 1, the constraint becomes binding and ensures that the condition ti + si + tij ≤ tj holds), and an order is considered as violated if it is serviced beyond its service end time, sei (Chapter 2. Theory, Arrival after the latest allowable time is not permitted and results in an infeasible solution), and wherein the one or more vehicles return from the depot after completion of the service Chapter 2. Theory, Constraints (2.3)-(2.4) state that each route starts and terminates at the depot).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh’s disclosure to incorporate the teachings of Kupriyanova to obtain routes that satisfy the depot start/return single visit capacity requirement for standard and established feasibility routing protocols.
Justification for combining James, Zhong, Stefan, Kindervater, Wang, Huang, and Tarawneh’s disclosures with Kupriyanova not only comes from the state of the art but from Kupriyanova (CHAPTER 5. ROUTE GENERATION PHASE, more efficient implementations of checking the feasibility have been suggested in the literature. In this thesis the approach described by Campbell and Savelsbergh [9] is applied when handling vehicle capacity and customer time window constraints. Some of their ideas are then used when implementing feasibility checks with respect to availability windows and shift time limits for vehicles).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SHANE E DOUGLAS whose telephone number is (703)756-1417. The examiner can normally be reached Monday - Friday 7:30AM - 5:00PM.
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 on (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.
/S.E.D./Examiner, Art Unit 3665
/CHRISTIAN CHACE/Supervisory Patent Examiner, Art Unit 3665