# US 2019/0316924 A1 · Vehicle routing

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

- Number: US 2019/0316924 A1
- Document ID: US20190316924A1
- Status: Published application
- Kind: A1
- Application number: 16/046,755
- Filed: 2018-07-26
- Published: 2019-10-17
- Earliest claimed: 2018-04-16
- Assignees: Morgan Brown Consultancy Ltd.
- Applicants: Morgan Brown Consultancy Ltd.
- Inventors: David MORGAN-BROWN
- Web page: https://patentgrep.com/patent/US20190316924A1

## CPC

- G01C 21/3476: {using point of interest [POI] information, e.g. a route passing visible POIs}
- B60L 58/12: responding to state of charge [SoC]
- G01C 21/3469: {Fuel consumption; Energy use; Emission aspects}
- G01C 21/3676: {Overview of the route on the road map}
- G01C 21/3697: {Output of additional, non-guidance related information, e.g. low fuel level (G01C21/3679 takes precedence)}
- G06N 3/0499: Feedforward networks
- G06N 3/09: Supervised learning
- G06N 3/08: Learning methods
- G06N 20/00: Machine learning
- Y02T 10/70: Energy storage systems for electromobility, e.g. batteries
- Y02T 90/16: Information or communication technologies improving the operation of electric vehicles
- Y02T 90/167: Systems integrating technologies related to power network operation and communication or information technologies for supporting the interoperability of electric or hybrid vehicles, i.e. smartgrids as interface for battery charging of electric vehicles [EV] or hybrid vehicles [HEV]
- Y04S 30/12: Remote or cooperative charging
- 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)
- B60L: PROPULSION OF ELECTRICALLY-PROPELLED VEHICLES (arrangements or mounting of electrical propulsion units or of plural diverse prime-movers for mutual or common propulsion in vehicles B60K1/00, B60K6/20; arrangements or mounting of electrical gearing in vehicles B60K17/12, B60K17/14; preventing wheel slip by reducing power in rail vehicles B61C15/08; dynamo-electric machines H02K; control or regulation of electric motors H02P); SUPPLYING ELECTRIC POWER FOR AUXILIARY EQUIPMENT OF ELECTRICALLY-PROPELLED VEHICLES (electric coupling devices combined with mechanical couplings of vehicles B60D1/64; electric heating for vehicles B60H1/00); ELECTRODYNAMIC BRAKE SYSTEMS FOR VEHICLES IN GENERAL (control or regulation of electric motors H02P); MAGNETIC SUSPENSION OR LEVITATION FOR VEHICLES; MONITORING OPERATING VARIABLES OF ELECTRICALLY-PROPELLED VEHICLES; ELECTRIC SAFETY DEVICES FOR ELECTRICALLY-PROPELLED VEHICLES
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- Y02T: CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
- Y04S: SYSTEMS INTEGRATING TECHNOLOGIES RELATED TO POWER NETWORK OPERATION, COMMUNICATION OR INFORMATION TECHNOLOGIES FOR IMPROVING THE ELECTRICAL POWER GENERATION, TRANSMISSION, DISTRIBUTION, MANAGEMENT OR USAGE, i.e. SMART GRIDS

## Abstract

An electric vehicle routing system comprising a route determination module configured to receive, via a graphical user interface (GUI) module, user input data defining, for a desired journey of a vehicle in which the vehicle routing system is installed, a start location in a road network, a destination location in the road network, and at least one waypoint in the road network. On the basis of the received user input data, data received from a vehicle battery status monitoring module, data retrieved from a road network storage database and data retrieved from a charging network storage database, the route determination module determines at least one route in the road network from the start location to the destination location via the at least one waypoint and transmits data associated with the at least one determined route to the GUI module.

## Claims

### Claim 1

An electric vehicle routing system comprising:
a route determination module;
an electric vehicle battery status monitoring module;
a road network storage database for storing data associated with a road network;
a charging network storage database for storing data associated with a plurality of electric vehicle battery charging locations in the road network; and
a graphical user interface (GUI) module,
the route determination module being configured to:
receive, via the GUI module, user input data defining, for a desired journey of a vehicle in which the vehicle routing system is installed, a start location in the road network, a destination location in the road network, and at least one waypoint in the road network;
receive, from the vehicle battery status monitoring module, at least one parameter associated with a status of a battery of the vehicle;
retrieve data from the road network storage database;
retrieve data from the charging network storage database;
on the basis of the received user input data, the data received from the vehicle battery status monitoring module, the data retrieved from the road network storage database and the data retrieved from the charging network storage database, determine at least one route in the road network from the start location to the destination location via the at least one waypoint; and
transmit data associated with the at least one determined route to the GUI module, the transmitted data being operable to cause the GUI module to display data indicative of the at least one determined route.

### Claim 2 (depends on 1)

An electric vehicle routing system according to claim 1, wherein the determining comprises first determining at least one first path from the start location to one or more electric vehicle battery charging locations in the plurality of electric vehicle battery charging locations.

### Claim 3 (depends on 1)

An electric vehicle routing system according to claim 1, wherein the determining comprises second determining at least one second path from one or more electric vehicle battery charging locations in the plurality of electric vehicle battery charging locations to the destination location.

### Claim 4 (depends on 1)

An electric vehicle routing system according to claim 1, wherein the determining comprises third determining at least one third path from one or more electric vehicle battery charging locations in the plurality of electric vehicle battery charging locations to one or more other electric vehicle battery charging locations in the plurality of electric vehicle battery charging locations.

### Claim 5 (depends on 2)

An electric vehicle routing system according to claim 2, wherein the determining comprises associating one or more cost parameters with the at least one first path, the at least one second path and the at least one third path.

### Claim 6 (depends on 5)

An electric vehicle routing system according to claim 5, wherein the one or more cost parameters for a given path comprise one or more of:
a distance travelled,
a time taken,
an elevation change,
a distance travelled in one or more compass directions, and
an energy saving parameter associated with an induction charging road.

### Claim 7 (depends on 5)

An electric vehicle routing system according to claim 5, wherein the determining comprises:
representing the start location, one or more of the electric vehicle battery charging locations in the plurality of electric vehicle battery charging locations and the destination location as nodes in a node network with paths between each node; and
calculating a minimum cost metric from the start location node to one or more other nodes in the node network by traversing paths in the node network from the start location node to the one or more other nodes in the node network, wherein the calculating comprises accumulating the one or more cost parameters associated with each traversed path.

### Claim 8 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating comprises accumulating a plurality of cost parameters for each traversed path.

### Claim 9 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating is carried out at least in part using a breadth first search process for each cost parameter.

### Claim 10 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating is carried out at last in part on an initial charge energy of the battery of the vehicle.

### Claim 11 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating comprises calculating a decrease in charge energy of the battery of the vehicle due to charge energy consumed when traversing each path.

### Claim 12 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating comprises calculating an increase in charge energy of the battery of the vehicle due to charge energy added when charging the battery at each respective electric vehicle battery charging location.

### Claim 13 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating is carried out at least on the basis of one or more parameters associated with a current state of the vehicle.

### Claim 14 (depends on 13)

An electric vehicle routing system according to claim 13, wherein the one or more parameters associated with a current state of the vehicle comprise one or more of:
vehicle battery temperature,
elevation change,
wind direction, and
ambient temperature.

### Claim 15 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating comprises identifying which path traversals are on the lowest cost route from the start location node to each other node in the node network.

### Claim 16 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating comprises dynamically calculating which path traversals are viable and which path traversals are not viable and pruning path traversals which are not viable from the node network.

### Claim 17 (depends on 16)

An electric vehicle routing system according to claim 16, wherein the dynamic calculating comprises for each path traversal from a given electric vehicle battery charging location node:
first calculating whether the charge energy consumed traversing from the given electric vehicle battery charging location node to a given other node is greater than the maximum charge energy of the electric vehicle battery minus a minimum allowed charge energy for the electric vehicle battery; and
in response to a positive first calculation, concluding that the respective path traversal is not viable.

### Claim 18 (depends on 17)

An electric vehicle routing system according to claim 17, wherein, in response to a negative first calculation, the dynamic calculating comprises:
second calculating whether the charge energy consumed traversing from the given electric vehicle battery charging location node to the given other node is lower than a current predicted charge energy of the electric vehicle battery minus the minimum allowed charge energy for the electric vehicle battery; and
in response to a positive second calculation, concluding that the respective path traversal is viable without charging.

### Claim 19 (depends on 18)

An electric vehicle routing system according to claim 18, wherein, in response to a negative second calculation, the dynamic calculating comprises:
concluding that the respective path traversal is viable with a cost equal to the cost of charging the electric vehicle battery with the minimum charge energy required for reaching the given other node from the given electric vehicle battery charging location node plus the charge energy consumed traversing from the given electric vehicle battery charging location node to the given other node.

### Claim 20 (depends on 18)

An electric vehicle routing system according to claim 18,
wherein the given electric vehicle battery charging location node is associated with a relatively fast charger and the given other node is associated with a relatively slow charger, and
wherein, in response to a negative second calculation, the dynamic calculating comprises:
creating an additional node in the node network comprising a copy of the given other node,
creating an additional viable path in the node network from the given electric vehicle battery charging location node to the additional node; and
allocating, to the additional viable path, a cost equal to the cost of charging the vehicle battery to full charge energy plus the charge energy consumed traversing from the given electric vehicle battery charging location node to the given other node.

### Claim 21 (depends on 16)

An electric vehicle routing system according to claim 16, wherein the dynamic calculating comprises for each path traversal from a given non-electric vehicle battery charging location node:
third calculating whether the charge energy consumed traversing from the given non-electric vehicle battery charging location node to another node is greater than a current predicted charge energy of the electric vehicle battery minus the minimum allowed charge energy for the electric vehicle battery;
in response to a positive third calculation, concluding that the respective path traversal is not viable; and
in response to a negative third calculation, concluding that the respective path traversal is viable.

### Claim 22 (depends on 17)

An electric vehicle routing system according to claim 17, wherein the minimum allowed charge energy for the electric vehicle battery is defined according to received user input data.

### Claim 23 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating is carried out at least in part on a predicted time taken to wait for a vehicle battery charger to become available at a respective electric vehicle battery charging location.

### Claim 24 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the calculating comprises allocating a cost penalty for each electric vehicle battery charging location node which is traversed.

### Claim 25 (depends on 1)

An electric vehicle routing system according to claim 1, wherein the route determination module is configured to, prior to receipt of the user input data, perform at least a part of the determining and/or calculating in advance and using at least a part of the results of the advance determining and/or calculating in the determining and/or calculating performed after receipt of the user input data.

### Claim 26 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the determining comprises determining a plurality of paths from the source location node to one or more copies of the destination location node with different time costs based upon one or more maximum speeds at which the vehicle should not exceed.

### Claim 27 (depends on 26)

An electric vehicle routing system according to claim 26, wherein the one or more maximum speeds are lower than the legal speed limit for at least a part of the plurality of paths.

### Claim 28 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the determining comprises:
representing the at least one waypoint as a node in the node network; and
fourth determining at least one fourth path to the destination location node via the at least one waypoint node.

### Claim 29 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the determining comprises fifth determining at least one fifth path to one or more of the electric vehicle battery charging location nodes via the at least one waypoint node.

### Claim 30 (depends on 28)

An electric vehicle routing system according to claim 28, wherein the determining comprises:
creating one or more copies of one or more charge nodes dynamically based upon whether the at least waypoint node has been traversed or not; and
sixth determining at least one sixth path to one or more other nodes from the one or more copies of the one or more charge nodes.

### Claim 31 (depends on 7)

An electric vehicle routing system according to claim 7, wherein the received user input data defines a plurality of waypoints, and wherein the determining comprises:
representing one or more other waypoints in the plurality of waypoints as nodes in the node network; and
seventh determining at least one seventh path from the at least one waypoint node to the one or more other waypoint nodes.

### Claim 32 (depends on 1)

An electric vehicle routing system according to claim 1, wherein the route determination module is configured to identify a subset of electric vehicle battery charging locations from the data retrieved from the charging network storage database and ignore the identified subset of electric vehicle battery charging locations for the purposes of the route determination.

### Claim 33 (depends on 32)

An electric vehicle routing system according to claim 32, wherein electric vehicle battery charging locations in the identified subset are those electric vehicle battery charging locations which are greater than a predefined distance from the great circle lines between the start location, the at least one waypoint and the destination location.

### Claim 34 (depends on 33)

An electric vehicle routing system according to claim 33, wherein the predetermined distance comprises the theoretical maximum range of the vehicle.

### Claim 35 (depends on 33)

An electric vehicle routing system according to claim 33, wherein the predetermined distance varies across the length of the desired journey.

### Claim 36 (depends on 35)

An electric vehicle routing system according to claim 35, wherein the predetermined distance is reduced where electric vehicle battery charging locations are located more densely and increased where electric vehicle battery charging locations are located more sparsely.

### Claim 37 (depends on 25)

An electric vehicle routing system according to claim 25, wherein the advance determining and/or calculating comprises computing the haversine distance between a particular geographic coordinate and another and estimating one or more of distance, time and other costs based upon the computed haversine distance.

### Claim 38 (depends on 25)

An electric vehicle routing system according to claim 25, wherein the advance determining and/or calculating comprises computing cost parameters between locations for a particular geographical area and using these to calculate a set of weights that can be applied to computed haversine distances to create a prediction of cost parameters.

### Claim 39 (depends on 25)

An electric vehicle routing system according to claim 25, wherein the advance determining and/or calculating comprises:
computing cost parameters between a candidate set of source locations and a candidate set of target locations; and
estimating cost parameters from a given first candidate location to a given second candidate location on the basis of:
the nearest source location to the given first candidate location, the nearest target location to the given second candidate location, and a sum of an estimated cost from the given first candidate location, a pre-calculated cost from the nearest source location to the nearest target location, and an estimated cost from the nearest target location to the given first candidate location.

### Claim 40 (depends on 25)

An electric vehicle routing system according to claim 25, wherein the advance determining and/or calculating comprises computing cost parameters between a number of source locations and target locations and using these to train a machine learning model.

### Claim 41 (depends on 25)

An electric vehicle routing system according to claim 25, wherein the advance determining and/or calculating comprises computing cost parameters from a set of landmarks to all other locations and using these to estimate cost parameters from a given first other location to a given second other location.

### Claim 42

A method of operating an electric vehicle routing system, the system comprising:
a route determination module;
an electric vehicle battery status monitoring module;
a road network storage database for storing data associated with a road network;
a charging network storage database for storing data associated with a plurality of electric vehicle battery charging locations in the road network; and
a graphical user interface (GUI) module,
the method comprising, at the route determination module:
receiving, via the GUI module, user input data defining, for a desired journey of a vehicle in which the vehicle routing system is installed, a start location in the road network, a destination location in the road network, and at least one waypoint in the road network;
receiving, from the vehicle battery status monitoring module, at least one parameter associated with a status of a battery of the vehicle;
retrieving data from the road network storage database;
retrieving data from the charging network storage database;
on the basis of the received user input data, the data received from the vehicle battery status monitoring module, the data retrieved from the road network storage database and the data retrieved from the charging network storage database, determining at least one route in the road network from the start location to the destination location via the at least one waypoint; and
transmitting data associated with the at least one determined route to the GUI module, the transmitted data being operable to cause the GUI module to display data indicative of the at least one determined route.

### Claim 43

A non-transitory, computer-readable medium comprising a set of instructions, which, when executed by processor of a computerized device, cause the computerized device to perform a method of operating an electric vehicle routing system, the system comprising:
a route determination module;
an electric vehicle battery status monitoring module;
a road network storage database for storing data associated with a road network;
a charging network storage database for storing data associated with a plurality of electric vehicle battery charging locations in the road network; and
a graphical user interface (GUI) module,
the method comprising, at the route determination module:
receiving, via the GUI module, user input data defining, for a desired journey of a vehicle in which the vehicle routing system is installed, a start location in the road network, a destination location in the road network, and at least one waypoint in the road network;
receiving, from the vehicle battery status monitoring module, at least one parameter associated with a status of a battery of the vehicle;
retrieving data from the road network storage database;
retrieving data from the charging network storage database;
on the basis of the received user input data, the data received from the vehicle battery status monitoring module, the data retrieved from the road network storage database and the data retrieved from the charging network storage database, determining at least one route in the road network from the start location to the destination location via the at least one waypoint; and
transmitting data associated with the at least one determined route to the GUI module, the transmitted data being operable to cause the GUI module to display data indicative of the at least one determined route.

### Claim 44

An electric vehicle routing system comprising:
a route determination module;
an electric vehicle battery status monitoring module;
a road network storage database for storing data associated with a road network;
a charging network storage database for storing data associated with a plurality of electric vehicle battery charging locations in the road network; and
a graphical user interface (GUI) module,
the route determination module being configured to:
receive, via the GUI module, user input data defining, for a desired journey of a vehicle in which the vehicle routing system is installed, a start location in the road network, and a destination location in the road network;
receive, from the vehicle battery status monitoring module, at least one parameter associated with a status of a battery of the vehicle, the at least one received parameter indicating a current temperature of the battery;
retrieve data from the road network storage database;
retrieve data from the charging network storage database;
on the basis of the received user input data, the data received from the vehicle battery status monitoring module, the data retrieved from the road network storage database and the data retrieved from the charging network storage database, determine at least one route in the road network from the start location to the destination location; and
transmit data associated with the at least one determined route to the GUI module, the transmitted data being operable to cause the GUI module to display data indicative of the at least one determined route.

### Claim 45

An electric vehicle routing system comprising:
a route determination module;
an electric vehicle battery status monitoring module;
a road network storage database for storing data associated with a road network;
a charging network storage database for storing data associated with a plurality of electric vehicle battery charging locations in the road network; and
a graphical user interface (GUI) module,
the route determination module being configured to:
receive, via the GUI module, user input data defining, for a desired journey of a vehicle in which the vehicle routing system is installed, a start location in the road network, and a destination location in the road network;
receive, from the vehicle battery status monitoring module, at least one parameter associated with a status of a battery of the vehicle;
retrieve data from the road network storage database;
retrieve data from the charging network storage database;
on the basis of the received user input data, the data received from the vehicle battery status monitoring module, the data retrieved from the road network storage database and the data retrieved from the charging network storage database, determine at least one route in the road network from the start location to the destination location; and
transmit data associated with the at least one determined route to the GUI module, the transmitted data being operable to cause the GUI module to display data indicative of the at least one determined route.

### Claim 46

A device for determining routes in a road network, the device comprising:
a route determination module;
a wireless transceiver; and
a graphical user interface (GUI) module,
the GUI module being configured to receive user input data defining, for a desired journey, a start location in the road network and a destination location in the road network,
the wireless transceiver being configured to:
receive, at least one parameter associated with a status of a battery of a vehicle;
receive data from a road network storage database; and
receive data from a charging network storage database associated with a plurality of electric vehicle battery charging locations in the road network, the route determination module being configured to:
on the basis of the received user input data, the received at least one vehicle battery status parameter, the data received from the road network storage database and the data received from the charging network storage database, determine at least one route in the road network from the start location to the destination location; and
provide data associated with the at least one determined route to the GUI module, the provided data being operable to cause the GUI module to display data indicative of the at least one determined route.
