# US 2022/0277652 A1 · Systems and methods for repositioning vehicles in a ride-hailing platform

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

- Number: US 2022/0277652 A1
- Document ID: US20220277652A1
- Status: Published application
- Kind: A1
- Application number: 17/518,192
- Filed: 2021-11-03
- Published: 2022-09-01
- Earliest claimed: 2021-02-26
- Assignees: Beijing Didi Infinity Technology and Development Co., Ltd.
- Applicants: Beijing DiDi Infinity Technology and Development Co., Ltd.
- Inventors: Shuaiji LI; Xiaocheng TANG; Zhiwei QIN
- Web page: https://patentgrep.com/patent/US20220277652A1

## CPC

- G08G 1/202: {Dispatching vehicles on the basis of a location, e.g. taxi dispatching}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/30038: {using a mask}
- G06F 18/214: Generating training patterns; Bootstrap methods, e.g. bagging or boosting
- G06N 3/02: Neural networks
- G06N 3/0499: Feedforward networks
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 3/092: Reinforcement learning
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G08G 1/207: {with respect to certain areas, e.g. forbidden or allowed areas with possible alerting when inside or outside boundaries}
- 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})
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

This disclosure describes systems and methods for repositioning vehicles. An exemplary method includes obtaining a plurality of current features associated with a vehicle located in one of the plurality of grid cells; inputting the plurality current features associated with the vehicle into a neural network; obtaining, from the neural network, a plurality of conditional action values for repositioning the vehicle to a plurality of target grid cells conditioned upon the plurality current features associated with the vehicle, wherein the plurality of target grid cells comprise the one grid cell that the vehicle is currently located in and other grid cells in the plurality of grid cells that are within two or more layers surrounding the one grid cell; and sending one or more of the plurality of target grid cells with highest conditional action values to the vehicle for repositioning.

## Claims

### Claim 1

A computer-implemented method, comprising:
obtaining, by one or more processors, a plurality of current features associated with a vehicle located in one of the plurality of grid cells;
inputting, by the one or more processors, the plurality current features associated with the vehicle into a neural network, wherein the neural network is trained using a state-action-reward-state-action (SARSA) framework based on a plurality of historical trajectories of one or more historical vehicles, historical supply-demand status in a plurality of neighboring grid cells of the one or more historical vehicles, and a plurality of actual conditional action values learned from historical data;
obtaining, by the one or more processors from the neural network, a plurality of conditional action values for repositioning the vehicle to a plurality of target grid cells conditioned upon the plurality current features associated with the vehicle, wherein the plurality of target grid cells comprise the one grid cell that the vehicle is currently located in and other grid cells in the plurality of grid cells that are within two or more layers surrounding the one grid cell; and
sending, by the one or more processors, one or more of the plurality of target grid cells with highest conditional action values to the vehicle for repositioning.

### Claim 2 (depends on 1)

The method of claim 1, wherein the other grid cells within two or more layers surrounding the one grid cell comprises at least:
a plurality of first grid cells that are immediately adjacent to the one grid cell, and
a plurality of second grid cells that are immediately adjacent to each of the plurality of first grid cells.

### Claim 3 (depends on 1)

The method of claim 1, wherein the inputting the plurality current features associated with the vehicle into the trained neural network comprises:
inputting the one grid cell in which the vehicle is currently located into a mask-based embedding layer of the neural network to obtain an embedded vector representation of the one grid cell.

### Claim 4 (depends on 3)

The method of claim 3, wherein the mask-based embedding layer comprises a plurality of first embedding vectors respectively trained for the plurality of grid cells, and
the inputting the one grid cell in which the vehicle is currently located into the trained mask-based embedding layer of the neural network comprises:
inputting the one grid cell to a corresponding first embedding vector to obtain the embedded vector representation of the one grid cell.

### Claim 5 (depends on 3)

The method of claim 3, wherein the mask-based embedding layer further comprises a second embedding vector trained by:
obtaining training data comprising a plurality of historical grid cells from a historical period of time, wherein each of the plurality of historical grid cells comprises location information and supply-demand features of neighboring grid cells surrounding the each historical grid cell in the historical period of time;
updating the training data by masking the location information of a subset of the plurality of historical grid cells; and
training the mask-based embedding layer based on the updated training data, wherein the training comprises:
initializing the second embedding vector representing the subset of the plurality of historical grid cells; and
for each of the subset of the plurality of historical grid cells, updating the second embedding vector based on the supply-demand features of the neighboring grid cells surrounding the each of the subset of the plurality of historical grid cells.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
obtaining information of a new grid cell in which a new vehicle is located, wherein the new grid cell has no corresponding first embeding vector in the mask-based embedding layer; and
inputting the information of the new grid cell into the second embedding vector to obtain an embedded vector representation of the new grid cell.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
preprocessing the plurality of historical trajectories of one or more historical vehicles for training the neural network, wherein the preprocessing comprises:
segmenting each of the plurality of historical trajectories of each historical vehicle into a plurality of state transition sections based on a dynamic time slot, wherein the dynamic time slot is proportional to a quantity of the two or more layers surrounding the one grid cell; and
training the neural network using SARSA based on the plurality of state transition sections.

### Claim 8 (depends on 1)

The method of claim 1, further comprising training the neural network, wherein the training comprises:
for each of the plurality of historical trajectories, sequentially feeding the sets of states of the each historical trajectory and the corresponding historical supply-demand status in the plurality of neighboring grid cells of the historical vehicle to a neural network to obtain a predicted conditional action value; and
training the neural network based on the predicted conditional action value and one of the plurality of actual conditional action values.

### Claim 9 (depends on 1)

The method of claim 1, wherein the plurality of current features associated with the vehicle comprise:
a current time, a current location of the vehicle, static features of the vehicle, and a supply-demand status at the current location of the vehicle.

### Claim 10 (depends on 9)

The method of claim 9, wherein the static features of the vehicle comprise at least one of the following:
vehicle capacity, manufacturer, year, and model.

### Claim 11 (depends on 9)

The method of claim 9, wherein the supply-demand status includes a ratio of the supply to the demand, the supply corresponds to a number of idle vehicles providing transportation services, and the demand corresponds to a number of pending orders for transportation.

### Claim 12 (depends on 1)

The method of claim 1, wherein the neural network comprises an attention module, and the method further comprises:
for each of neighboring grid cells of the grid cell in which the vehicle is located, determining, through the attention module, a score based on a first supply-demand vector representing the supply-demand status of the grid cell and a second supply-demand vector representing the supply-demand status in the neighboring grid cell;
applying the score to the second supply-demand vector to obtain a weighted supply-demand vector; and
generating a weighted supply-demand context vector for the grid cell in which the vehicle is located based on the plurality of weighted supply-demand vectors of the neighboring grid cells.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
determining the one or more of the plurality of target grid cells with highest conditional action values by:
performing unequal probability sampling from the plurality of neighboring grid cells corresponding to the plurality of target grid cells based on the plurality of conditional action values to obtain one sampled grid cell, wherein a probability of one grid cell being sampled is proportional to the one grid cell's corresponding conditional action value.

### Claim 14

A system comprising one or more processors and one or more non-transitory computer-readable memories coupled to the one or more processors, the one or more non-transitory computer-readable memories storing instructions that, when executed by the one or more processors, cause the system to perform operations comprising:
obtaining a plurality of current features associated with a vehicle located in one of the plurality of grid cells;
inputting the plurality current features associated with the vehicle into a neural network, wherein the neural network is trained using a state-action-reward-state-action (SARSA) framework based on a plurality of historical trajectories of one or more historical vehicles, historical supply-demand status in a plurality of neighboring grid cells of the one or more historical vehicles, and a plurality of actual conditional action values learned from historical data;
obtaining, from the neural network, a plurality of conditional action values for repositioning the vehicle to a plurality of target grid cells conditioned upon the plurality current features associated with the vehicle, wherein the plurality of target grid cells comprise the one grid cell that the vehicle is currently located in and other grid cells in the plurality of grid cells that are within two or more layers surrounding the one grid cell; and
sending one or more of the plurality of target grid cells with highest conditional action values to the vehicle for repositioning.

### Claim 15 (depends on 14)

The system of claim 14, wherein the other grid cells within two or more layers surrounding the one grid cell comprises at least:
a plurality of first grid cells that are immediately adjacent to the one grid cell, and
a plurality of second grid cells that are immediately adjacent to each of the plurality of first grid cells.

### Claim 16 (depends on 14)

The system of claim 14, wherein the inputting the plurality current features associated with the vehicle into the trained neural network comprises:
inputting the one grid cell in which the vehicle is currently located into a trained mask-based embedding layer of the neural network to obtain an embedded vector representation of the one grid cell.

### Claim 17 (depends on 16)

The system of claim 16, wherein the trained mask-based embedding layer comprises a plurality of first embedding vectors respectively trained for the plurality of grid cells, and
the inputting the one grid cell in which the vehicle is currently located into the trained mask-based embedding layer of the neural network comprises:
inputting the one grid cell to a corresponding first embedding vector to obtain the embedded vector representation of the one grid cell.

### Claim 18 (depends on 16)

The system of claim 16, wherein the mask-based embedding layer further comprises a second embedding vector trained by:
obtaining training data comprising a plurality of historical grid cells from a historical period of time, wherein each of the plurality of historical grid cells comprises location information and supply-demand features of neighboring grid cells surrounding the each historical grid cell in the historical period of time;
updating the training data by masking the location information of a subset of the plurality of historical grid cells; and
training the mask-based embedding layer based on the updated training data, wherein the training comprises:
initializing the second embedding vector representing the subset of the plurality of historical grid cells; and
for each of the subset of the plurality of historical grid cells, updating the second embedding vector based on the supply-demand features of the neighboring grid cells surrounding the each of the subset of the plurality of historical grid cells.

### Claim 19 (depends on 14)

The system of claim 14, further comprising training the neural network, wherein the training comprises:
for each of the plurality of historical trajectories, sequentially feeding the sets of states of the each historical trajectory and the corresponding historical supply-demand status in the plurality of neighboring grid cells of the historical vehicle to a neural network to obtain a predicted conditional action value; and
training the neural network based on the predicted conditional action value and one of the plurality of actual conditional action values.

### Claim 20

A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
obtaining a plurality of current features associated with a vehicle located in one of the plurality of grid cells representing a region;
inputting the plurality current features associated with the vehicle into a neural network, wherein the neural network is trained using a state-action-reward-state-action (SARSA) framework based on a plurality of historical trajectories of one or more historical vehicles, historical supply-demand status in a plurality of neighboring grid cells of the one or more historical vehicles, and a plurality of actual conditional action values learned from historical data;
obtaining, from the neural network, a plurality of conditional action values for repositioning the vehicle to a plurality of target grid cells conditioned upon the plurality current features associated with the vehicle, wherein the plurality of target grid cells comprise the one grid cell that the vehicle is currently located in and other grid cells in the plurality of grid cells that are within two or more layers surrounding the one grid cell; and
sending one or more of the plurality of target grid cells with highest conditional action values to the vehicle for repositioning.
