# US 2021/0241625 A1 · Method and apparatus for providing large scale vehicle routing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0241625 A1 - Document ID: US20210241625A1 - Status: Published application - Kind: A1 - Application number: 16/779,141 - Filed: 2020-01-31 - Published: 2021-08-05 - Earliest claimed: 2020-01-31 - Assignees: HERE Global B.V. - Applicants: Here Global B.V. - Inventors: Oren ELISHA - Web page: https://patentgrep.com/patent/US20210241625A1 ## CPC - G01C 21/3438: {Rendezvous; Ride sharing} - G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)} - G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes} - G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram - G06V 10/7625: {Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms} - G08G 1/0145: {for active traffic flow control} - G08G 1/202: {Dispatching vehicles on the basis of a location, e.g. taxi dispatching} - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) ## Abstract An approach is provided for large scale vehicle routing. The approach involves, for example, receiving a plurality of plans, wherein a plan of the plurality of plans assigns a vehicle, a driver of the vehicle, or a combination thereof a set of rides to traverse. The approach also involves clustering the plurality of plans into one or more clusters based on a proximity measure. The proximity measure indicates a proximity of a first plan of the plurality of plans to a second plan of a plurality of plans. The approach further involves, for each cluster of the one or more clusters, separately computing a solution to a multiple vehicle routing problem for the set of rides in said each cluster. ## Claims ### Claim 1 A method for large scale vehicle routing comprising: receiving a plurality of plans, wherein a plan of the plurality of plans assigns a vehicle, a driver of the vehicle, or a combination thereof a set of rides to traverse; clustering the plurality of plans into one or more clusters based on a proximity measure, wherein the proximity measure indicates a proximity of a first plan of the plurality of plans to a second plan of a plurality of plans; and for each cluster of the one or more clusters, separately computing a solution to a multiple vehicle routing problem for the set of rides in said each cluster. ### Claim 2 (depends on 1) The method of claim 1, wherein the proximity of the first plan to the second plan is based on a probability that a first driver following the first plan can take on a ride from the second plan. ### Claim 3 (depends on 1) The method of claim 1, further comprising: constructing a ride graph to represent one or more feasible connections between the set of rides in the first plan, the second plan, or a combination thereof, wherein the one or more feasible connections are connections in which the vehicle following the first plan, the second plan, or a combination can arrive from a drop-off location of a first ride to a pick-up location of a second ride without being late to a pick-up time of the second ride, and wherein the proximity of the first plan to the second plan is based the ride graph. ### Claim 4 (depends on 3) The method of claim 3, wherein each node of the ride graph corresponds to a ride of the set of rides, the method further comprising: constructing a first matrix representing the nodes of the ride graph of the first plan; and constructing a second matrix representing the nodes of the ride graph of the second plan, wherein the proximity measure is based on a distance metric calculated between the first matrix and the second matrix. ### Claim 5 (depends on 4) The method of claim 4, wherein the distance metric is based on one or more common nodes between the first matrix and the second matrix. ### Claim 6 (depends on 5) The method of claim 5, wherein the distance metric is based on one or more edge values between the nodes, and wherein the one or more edge values are based on whether the one or more feasible connections are present between the nodes. ### Claim 7 (depends on 6) The method of claim 6, further comprising: calculating one or more variables based on the one or more common nodes, wherein the one or more variables include at least one of: a first variable based on the one or more edge values corresponding to first edges entering the one or more common nodes; a second variable based on the one or more edge values corresponding to second edges exiting the one or more common nodes; a third variable based on the one or more edge values corresponding to third edges entering the one or more common nodes from the first plan and exiting the one or more common nodes to the second plan; and a fourth variable based on the one or more edge values corresponding to fourth edges entering the one or more common nodes from the second plan and exiting the one or more common nodes to the first plan, and wherein the distance metric is based on the one or more variables. ### Claim 8 (depends on 1) The method of claim 1, further comprising: iteratively split the one or more clusters until a corresponding cluster size is below a maximum cluster size threshold. ### Claim 9 (depends on 1) The method of claim 1, further comprising: iteratively merging the one or more clusters until a corresponding cluster size is above a minimum cluster size threshold. ### Claim 10 (depends on 9) The method of claim 9, wherein the one or more clusters are merged based a closest cluster determined using the proximity measure. ### Claim 11 An apparatus for providing large scale vehicle routing, comprising: a processor; and a memory including computer program code for a program, the memory and the computer program code configured to, with the processor, cause the apparatus to perform at least the following, receive a plurality of plans, wherein a plan of the plurality of plans assigns a vehicle, a driver of the vehicle, or a combination thereof a set of rides to traverse; cluster the plurality of plans into one or more clusters based on a proximity measure, wherein the proximity measure indicates a proximity of a first plan of the plurality of plans to a second plan of a plurality of plans; and for each cluster of the one or more clusters, separately compute a solution to a multiple vehicle routing problem for the set of rides in said each cluster. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the proximity of the first plan to the second plan is based on a probability that a first driver following the first plan can take on a ride from the second plan. ### Claim 13 (depends on 11) The apparatus of claim 11, wherein the apparatus is further caused to: construct a ride graph to represent one or more feasible connections between the set of rides in the first plan, the second plan, or a combination thereof, wherein the one or more feasible connections are connections in which the vehicle following the first plan, the second plan, or a combination can arrive from a drop-off location of a first ride to a pick-up location of a second ride without being late to a pick-up time of the second ride, and wherein the proximity of the first plan to the second plan is based the ride graph. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein each node of the ride graph corresponds to a ride of the set of rides, and the apparatus is further caused to: construct a first matrix representing the nodes of the ride graph of the first plan; and construct a second matrix representing the nodes of the ride graph of the second plan, wherein the proximity measure is based on a distance metric calculated between the first matrix and the second matrix. ### Claim 15 (depends on 14) The apparatus of claim 14, wherein the distance metric is based on one or more common nodes between the first matrix and the second matrix. ### Claim 16 A non-transitory computer-readable storage medium for providing large scale vehicle routing, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps: receiving a plurality of plans, wherein a plan of the plurality of plans assigns a vehicle, a driver of the vehicle, or a combination thereof a set of rides to traverse; clustering the plurality of plans into one or more clusters based on a proximity measure, wherein the proximity measure indicates a proximity of a first plan of the plurality of plans to a second plan of a plurality of plans; and for each cluster of the one or more clusters, separately computing a solution to a multiple vehicle routing problem for the set of rides in said each cluster. ### Claim 17 (depends on 16) The non-transitory computer-readable storage medium of claim 16, wherein the proximity of the first plan to the second plan is based on a probability that a first driver following the first plan can take on a ride from the second plan. ### Claim 18 (depends on 16) The non-transitory computer-readable storage medium of claim 16, wherein the apparatus is caused to further perform: constructing a ride graph to represent one or more feasible connections between the set of rides in the first plan, the second plan, or a combination thereof, wherein the one or more feasible connections are connections in which the vehicle following the first plan, the second plan, or a combination can arrive from a drop-off location of a first ride to a pick-up location of a second ride without being late to a pick-up time of the second ride, and wherein the proximity of the first plan to the second plan is based the ride graph. ### Claim 19 (depends on 18) The non-transitory computer-readable storage medium of claim 18, wherein each node of the ride graph corresponds to a ride of the set of rides, and the apparatus is caused to further perform: constructing a first matrix representing the nodes of the ride graph of the first plan; and constructing a second matrix representing the nodes of the ride graph of the second plan, wherein the proximity measure is based on a distance metric calculated between the first matrix and the second matrix. ### Claim 20 (depends on 19) The non-transitory computer-readable storage medium of claim 19, wherein the distance metric is based on one or more common nodes between the first matrix and the second matrix.