# US 2020/0394922 A1 · Systems and methods for improved vehicle routing to account for real-time passenger pickup and dropoff

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0394922 A1
- Document ID: US20200394922A1
- Status: Published application
- Kind: A1
- Application number: 16/553,837
- Filed: 2019-08-28
- Published: 2020-12-17
- Earliest claimed: 2019-06-11
- Assignees: Toyota Connected North America, Inc.
- Applicants: Toyota Connected North America, Inc.
- Inventors: Mathew D. Gardner; Taylor G. Smith
- Web page: https://patentgrep.com/patent/US20200394922A1

## CPC

- G08G 1/20: {Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles}
- G01C 21/3415: {Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents}
- G01C 21/3438: {Rendezvous; Ride sharing}
- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G06Q 10/0631: Resource planning, allocation, distributing or scheduling for enterprises or organisations
- G08G 1/096811: {where the route is computed offboard}
- G08G 1/096838: {where the user preferences are taken into account or the user selects one route out of a plurality}
- G08G 1/202: {Dispatching vehicles on the basis of a location, e.g. taxi dispatching}
- 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})
- 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)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

System, methods, and other embodiments described herein relate to improving vehicle routing for a mobility service. In one embodiment, a method includes, in response to receiving a routing request for the mobility service, determining candidate vehicles and candidate routes for the candidate vehicles to fulfill the routing request. The method includes evaluating the candidate routes using a meta-heuristic that modifies and assesses the candidate routes according to at least a fitness function defines attributes for constraining the candidate routes. The method includes providing a solution route from the candidate routes upon the solution route satisfying at least one solution condition.

## Claims

### Claim 1

A routing system for improving routing of vehicles for a mobility service, comprising:
one or more processors;
a memory communicably coupled to the one or more processors and storing:
an acquisition module including instructions that when executed by the one or more processors cause the one or more processors to, in response to receiving a routing request for the mobility service, determine candidate vehicles and candidate routes for the candidate vehicles to fulfill the routing request; and
a routing module including instructions that when executed by the one or more processors cause the one or more processors to:
evaluate the candidate routes using a meta-heuristic that modifies and assesses the candidate routes according to at least a fitness function defines attributes for constraining the candidate routes, and
provide a solution route from the candidate routes upon the solution route satisfying at least one solution condition.

### Claim 2 (depends on 1)

The routing system of claim 1, wherein the acquisition module further includes instructions to define, prior to receiving the routing request, routing parameters of the fitness function to control how the fitness function assesses the candidate routes to serve as the solution route,
wherein the acquisition module includes the instructions to define the routing parameters including instructions to define at least weights for constraints of the fitness function including: a first cost as an overall distance of the solution route, a second cost as a capacity of the solution route for cargo including one or more of parcels and riders, a third cost associated with the solution route exceeding a time overage, a fourth cost as a promptness in relation to a pickup time and a drop off time, and a fifth cost as a trip length penalty, and
wherein the at least one solution condition is based, at least in part, on the routing parameters.

### Claim 3 (depends on 1)

The routing system of claim 1, wherein the routing module includes instructions to evaluate the candidate routes using the meta-heuristic including instructions to perform a large neighborhood search (LNS) over the candidate routes by:
i) removing the routing request from at least one of the candidate routes without removing existing requests for onboard riders, and
ii) reconstructing the at least one of the candidate routes using a pre-computed nearest neighbor k-d tree to identify a nearest neighbor pair and insert the routing request into the at least one of the candidate routes including the nearest neighbor pair, wherein a nearest neighbor pair is a separate request for the mobility service that includes a pickup location and a destination location.

### Claim 4 (depends on 1)

The routing system of claim 1, wherein the routing module includes instructions to evaluate the candidate routes including instructions to sort the candidate routes according to fitness scores produced using the fitness function that is part of the meta-heuristic,
wherein the fitness function assesses the candidate routes according to a set of constraints that separately value aspects of the candidate routes, and
wherein the at least one solution condition indicates at least a number of iterations to evaluate the candidate routes using the meta-heuristic.

### Claim 5 (depends on 1)

The routing system of claim 1, wherein the routing module includes instructions to determine the candidate vehicles including instructions to identify which of the vehicles for the mobility service are within a defined distance of a pickup location of the routing request,
wherein the routing module includes instructions to determine the candidate routes for the candidate vehicles including instructions to populate the candidate routes with an originating point and a destination point for at least the routing request, and
wherein one or more of the candidate vehicles include a trip that is underway for which populating an associated candidate route includes generating a deviation to the trip.

### Claim 6 (depends on 1)

The routing system of claim 1, wherein the routing module includes instructions to provide the solution route including instructions to assign the routing request to a respective one of the candidate vehicles associated with the solution route and to electronically communicate the routing request to the respective one of the candidate vehicles to cause the respective one of the candidate vehicles to service the routing request on-demand including deviating from a current trip to fulfill the routing request.

### Claim 7 (depends on 1)

The routing system of claim 1, wherein the routing module includes instructions to evaluate the candidate routes iteratively until satisfying a number of iterations for evaluating as specified by the solution condition,
wherein the mobility service is a rideshare service, and
wherein the acquisition module includes instructions to receive the routing request including instructions to receive multiple routing requests for a future time to process as a batch.

### Claim 8 (depends on 1)

The routing system of claim 1, wherein one or more of the candidate vehicles are autonomous vehicles.

### Claim 9

A non-transitory computer-readable medium storing for improving routing of vehicles for a mobility service and including instructions that when executed by one or more processors cause the one or more processors to:
in response to receiving a routing request for the mobility service, determine candidate vehicles and candidate routes for the candidate vehicles to fulfill the routing request;
evaluate the candidate routes using a meta-heuristic that modifies and assesses the candidate routes according to at least a fitness function defines attributes for constraining the candidate routes; and
provide a solution route from the candidate routes upon the solution route satisfying at least one solution condition.

### Claim 10 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the instructions further include instructions to define, prior to receiving the routing request, routing parameters of the fitness function to control how the fitness function assesses the candidate routes to serve as the solution route,
wherein the instructions to define the routing parameters include instructions to define at least weights for constraints of the fitness function including: a first cost as an overall distance of the solution route, a second cost as a capacity of the solution route for cargo including one or more of parcels and riders, a third cost associated with the solution route exceeding a time overage, a fourth cost as a promptness in relation to a pickup time and a drop off time, and a fifth cost as a trip length penalty, and
wherein the at least one solution condition is based, at least in part, on the routing parameters.

### Claim 11 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the instructions to evaluate the candidate routes using the meta-heuristic include instructions to execute a large neighborhood search (LNS) over the candidate routes by:
i) removing the routing request from at least one of the candidate routes without removing existing requests for onboard riders, and
ii) reconstructing the at least one of the candidate routes using a pre-computed nearest neighbor k-d tree to identify a nearest neighbor pair and insert the routing request into the at least one of the candidate routes including the nearest neighbor pair, wherein a nearest neighbor pair is a separate request for the mobility service that includes a pickup location and a destination location.

### Claim 12 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the instructions to evaluate the candidate routes include instructions to sort the candidate routes according to fitness scores produced using the fitness function that is part of the meta-heuristic,
wherein the fitness function assesses the candidate routes according to a set of constraints that separately value aspects of the candidate routes, and
wherein the at least one solution condition indicates at least a number of iterations to evaluate the candidate routes using the meta-heuristic.

### Claim 13 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the instructions to determine the candidate vehicles include instructions to identify which of the vehicles for the mobility service are within a defined distance of a pickup location of the routing request,
wherein the instructions to determine the candidate routes for the candidate vehicles include instructions to populate the candidate routes with an originating point and a destination point for at least the routing request, and
wherein one or more of the candidate vehicles include a trip that is underway for which populating an associated candidate route includes generating a deviation to the trip.

### Claim 14

A method for improving routing of vehicles for a mobility service, comprising:
in response to receiving a routing request for the mobility service, determining candidate vehicles and candidate routes for the candidate vehicles to fulfill the routing request;
evaluating the candidate routes using a meta-heuristic that modifies and assesses the candidate routes according to at least a fitness function defines attributes for constraining the candidate routes; and
providing a solution route from the candidate routes upon the solution route satisfying at least one solution condition.

### Claim 15 (depends on 14)

The method of claim 14, further including:
defining, prior to receiving the routing request, routing parameters of the fitness function to control how the fitness function assesses the candidate routes to serve as the solution route,
wherein defining the routing parameters includes defining at least weights for constraints of the fitness function including: a first cost as an overall distance of the solution route, a second cost as a capacity of the solution route for cargo including one or more of parcels and riders, a third cost associated with the solution route exceeding a time overage, a fourth cost as a promptness in relation to a pickup time and a drop off time, and a fifth cost as a trip length penalty, and
wherein the at least one solution condition is based, at least in part, on the routing parameters.

### Claim 16 (depends on 14)

The method of claim 14, wherein evaluating the candidate routes using the meta-heuristic includes performing a large neighborhood search (LNS) over the candidate routes by:
i) removing the routing request from at least one of the candidate routes without removing existing requests for onboard riders, and
ii) reconstructing the at least one of the candidate routes using a pre-computed nearest neighbor k-d tree to identify a nearest neighbor pair and insert the routing request into the at least one of the candidate routes including the nearest neighbor pair, wherein a nearest neighbor pair is a separate request for the mobility service that includes a pickup location and a destination location.

### Claim 17 (depends on 14)

The method of claim 14, wherein evaluating the candidate routes includes sorting the candidate routes according to fitness scores produced using the fitness function that is part of the meta-heuristic,
wherein the fitness function assesses the candidate routes according to a set of constraints that separately value aspects of the candidate routes, and
wherein the at least one solution condition indicates at least a number of iterations to evaluate the candidate routes using the meta-heuristic.

### Claim 18 (depends on 14)

The method of claim 14, wherein determining the candidate vehicles includes identifying which of the vehicles for the mobility service are within a defined distance of a pickup location of the routing request,
wherein determining the candidate routes for the candidate vehicles includes populating the candidate routes with an originating point and a destination point for at least the routing request, and
wherein one or more of the candidate vehicles include a trip that is underway for which populating an associated candidate route includes generating a deviation to the trip.

### Claim 19 (depends on 14)

The method of claim 14, wherein providing the solution route includes assigning the routing request to a respective one of the candidate vehicles associated with the solution route and electronically communicating the routing request to the respective one of the candidate vehicles to cause the respective one of the candidate vehicles to service the routing request on-demand including deviating from a current trip to fulfill the routing request.

### Claim 20 (depends on 14)

The method of claim 14, wherein evaluating the candidate routes executes iteratively until satisfying a number of iterations for evaluating the candidate routes as specified by the solution condition,
wherein the mobility service is a rideshare service, and
wherein receiving the routing request includes receiving multiple routing requests for a future time to process as a batch.
