# US 2022/0026222 A1 · Method, Machine Readable Medium, Device, and Vehicle For Determining a Route Connecting a Plurality of Destinations in a Road Network, Method, Machine Readable Medium, and Device For Training a Machine Learning Module

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

- Number: US 2022/0026222 A1
- Document ID: US20220026222A1
- Status: Published application
- Kind: A1
- Application number: 16/937,610
- Filed: 2020-07-24
- Published: 2022-01-27
- Earliest claimed: 2020-07-24
- Assignees: Bayerische Motoren Werke Aktiengesellschaft
- Applicants: Bayerische Motoren Werke Aktiengesellschaft
- Inventors: Jilei TIAN; Yang CAO
- Web page: https://patentgrep.com/patent/US20220026222A1

## CPC

- G01C 21/3407: {specially adapted for specific applications}
- G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)}
- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G01C 21/3626: {Details of the output of route guidance instructions (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968)}
- G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
- G06N 3/045: Combinations of networks
- G06N 3/0455: Auto-encoder networks; Encoder-decoder networks
- G06N 3/0499: Feedforward networks
- G06N 3/088: Non-supervised learning, e.g. competitive learning
- G06N 3/0895: Weakly supervised learning, e.g. semi-supervised or self-supervised learning
- G06N 3/092: Reinforcement learning
- G06N 20/00: Machine learning
- 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)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Embodiments provide a method, a machine readable medium, a device and a vehicle for determining a route connecting a plurality of destinations in a road network, and a method, a machine readable medium and a device for training a machine learning module for determining a route connecting a plurality of destinations in a road network. The method for determining a route connecting a plurality of destinations in a road network comprises receiving input information, which comprises information on distances between the plurality of destinations in the road network. The method further comprises inputting the input information on the distances into a trained machine learning module and providing output information on the route connecting the plurality of destinations based on an output of the trained machine learning module.

## Claims

### Claim 1

A method for determining a route connecting a plurality of destinations in a road network, the method comprising
receiving input information, which comprises information on distances between the plurality of destinations in the road network;
inputting the input information on the distances into a trained machine learning module; and
providing output information on the route connecting the plurality of destinations based on an output of the trained machine learning module.

### Claim 2 (depends on 1)

The method of claim 1, wherein the input information further comprises information on a time window constraint for at least one of the plurality of destinations, and further comprising inputting the information on the time window constraint into the trained machine learning module.

### Claim 3 (depends on 1)

The method of claim 1, wherein the information on the distances between the destinations comprises a matrix with mutual distances between pairs of the plurality of destinations.

### Claim 4 (depends on 3)

The method of claim 3, wherein the mutual distances between the pairs are at least partly asymmetric.

### Claim 5 (depends on 1)

The method of claim 1, further comprising determining embedding information for the machine learning module.

### Claim 6 (depends on 5)

The method of claim 5, wherein the embedding information comprises a vector with a predetermined size.

### Claim 7 (depends on 1)

The method of claim 1, further comprising adapting the input information to a predetermined number of destinations.

### Claim 8 (depends on 7)

The method of claim 7, wherein the adapting comprises complementing the plurality of destinations to the predetermined number of destinations by introducing virtual destinations.

### Claim 9 (depends on 7)

The method of claim 7, wherein the adapting comprises complementing destinations without a time window constraint with a non-restrictive time window constraint.

### Claim 10 (depends on 1)

A device comprising processing circuitry configured to perform the method of claim 1.

### Claim 11 (depends on 10)

A vehicle comprising the device of claim 10.

### Claim 12

A method for training a machine learning module for determining a route connecting a plurality of destinations in a road network, the method comprising
generating coordinates for the plurality of destinations;
calculating distances between the plurality of destinations based on the coordinates;
introducing at least one asymmetry to the distances to obtain asymmetric distances; and
training the machine learning module based on the asymmetric distances.

### Claim 13 (depends on 12)

The method of claim 12, wherein the generating comprises generating at least two random coordinates per destination and combining at least two distances based on the at least two coordinates per destination for calculating the distances.

### Claim 14 (depends on 12)

The method of claim 12, further comprising generating time window constraint information for the plurality of destinations.

### Claim 15 (depends on 14)

The method of claim 14, wherein the generating of the time window constraint information is based on the asymmetric distances.

### Claim 16 (depends on 15)

The method of claim 15, wherein the generating of the time window constraint information assumes a random sequence of the asymmetric distances and assigns at least partly rational time window constraints to destinations fitting the given random sequence.

### Claim 17 (depends on 12)

The method of claim 12, wherein the training of the machine learning module comprises determining rewards for candidate routes determined by the machine learning module.

### Claim 18 (depends on 17)

The method of claim 17, wherein the determining of the rewards is based on an overall distance of a candidate route.

### Claim 19 (depends on 18)

The method of claim 18, wherein the determining of the rewards is further based on a compliance of a sequence of the plurality of destinations in a candidate route with predetermined time window constraints for the plurality of destinations.
