Optimized placement of electric vehicle charging stations

• US 10,083,413 B2
• Filed: 04/08/2015
• Issued: 09/25/2018
• Est. Priority Date: 04/08/2015
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Sun, Gufei, Wang, Heng, Li, Wen-Syan
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US14/682,049
• Publication Number:
  US 20160300170A1
• Time in Patent Office: 1,266 Days
• CPC Class Codes: B60L 53/31 Charging columns specially adapted for electric vehicles
• CPC Class Codes: B60L 53/665 Methods related to measuring, billing or payment
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 50/06 Energy or water supply
• CPC Class Codes: Y02T 10/70 Energy storage systems for electromobility, e.g. batteries
• CPC Class Codes: Y02T 10/7072 Electromobility specific charging systems or methods for batteries, ultracapacitors, supercapacitors or double-layer capacitors
• CPC Class Codes: Y02T 90/12 Electric charging stations
• CPC Class Codes: Y02T 90/14 Plug-in electric vehicles
• CPC Class Codes: Y02T 90/16 Information or communication technologies improving the operation of electric vehicles
• CPC Class Codes: 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]
• CPC Class Codes: Y04S 30/14 Details associated with the interoperability, e.g. vehicle recognition, authentication, identification or billing

Abstract

Disclosed herein are technologies for facilitating placement of charging stations. In accordance with one aspect, sensor data of electric vehicles is received. A charging demand distribution over a set of locations is determined based on the sensor data. Candidate locations are selected from the set of locations based on the charging demand distribution. Placement of charging stations at one or more of the candidate locations is then optimized.

Claims

1. A system for placing charging stations, comprising:

a non-transitory memory device for storing computer readable program code; and

a processor device in communication with the memory device, the processor device being operative with the computer readable program code to perform steps including

receive historical battery level data and location data of electric vehicles, the historical battery level data including initial battery level data and final battery level data,

predict, based on the historical battery level data and the location data, a charging demand distribution over a set of locations by determining, based on the initial battery level data, a probability that a driver will choose to charge an electric vehicle given an initial battery level and determining, based on the final battery level data, an average charging time,

select, from the set of locations, candidate locations based on the charging demand distribution,

optimize placement and sizes of the charging stations at one or more of the candidate locations,

present, via an output device, the optimized placement and sizes of the charging stations; and

placing a charging station at one of the candidate locations in accordance with the optimized placement and sizes of the charging stations.

2. The system of claim 1 wherein the electric vehicles comprise electric cars.

3. The system of claim 1 wherein the processor device is operative with the computer readable program code to optimize the placement and sizes of the charging stations by determining a solution that minimizes construction cost of the charging stations and maximizes coverage rate provided by the charging stations.

4. The system of claim 1 wherein the processor device is operative with the computer readable program code to optimize the placement and sizes of the charging stations by fulfilling one or more constraints based on a maximum number of charging piles that can be installed, a maximum budget for building new charging stations or a minimum coverage rate.

5. A method for placing charging stations, comprising:

receiving, by a processor device, sensor data of electric vehicles, wherein the sensor data comprises location data, initial battery level data and final battery level data;

predicting, by the processor device and based on the sensor data, a charging demand distribution over a set of locations by determining, based on the initial battery level data, a probability that a driver will choose to charge an electric vehicle given an initial battery level and determining, based on the final battery level data, an average charging time;

selecting, by the processor device and from the set of locations, candidate locations based on the charging demand distribution;

optimizing, by the processor device, placement of the charging stations at one or more of the candidate locations; and

placing a charging station at one of the candidate locations in accordance with the optimized placement of the charging stations.

6. The method of claim 5 wherein the set of locations comprises locations where stopping times of the electric vehicles are longer than a predetermined period.

7. The method of claim 5 wherein predicting the charging demand distribution further comprises determining an expectation of charging time based on the probability and the average charging time.

8. The method of claim 7 further comprising adjusting the expectation of charging time based on recorded parking times.

9. The method of claim 5 wherein predicting the charging demand distribution comprises accumulating expectations of charging time for multiple cars at different time points.

10. The method of claim 5 wherein selecting the candidate locations from the set of locations comprises selecting the candidate locations that are associated with a predicted demand that is greater than a predetermined number.

11. The method of claim 5 wherein optimizing the placement of the charging stations comprises performing an integer programming method.

12. The method of claim 5 wherein optimizing the placement of the charging stations comprises determining a solution that fulfills one or more constraints based on a maximum number of charging piles that can be installed, a maximum budget for building new charging stations or a minimum coverage rate.

13. A method for placing charging stations, comprising:

receiving, by a processor device, sensor data of electric vehicles;

predicting, by the processor device and based on the sensor data, a charging demand distribution over a set of locations;

selecting, by the processor device and from the set of locations, candidate locations based on the charging demand distribution;

optimizing, by the processor device, placement of the charging stations at one or more of the candidate locations, wherein optimizing the placement of the charging stations comprises determining a solution that minimizes construction cost of the charging stations, maximizes coverage rate provided by the charging stations and minimizes a penalty value determined by summarizing distances between the electric vehicles and their respective nearest charging stations; and

placing a charging station at one of the candidate locations in accordance with the placement of the charging stations solution.

14. A method for placing charging stations, comprising:

generating a non-transitory computer readable medium embodying a program of instructions executable by a machine to perform steps for placing charging stations, comprising;

receiving sensor data of electric vehicles, wherein the sensor data comprises location data, initial battery level data and final battery level data;

predicting, based on the sensor data, a charging demand distribution over a set of locations by determining, based on the initial battery level data, a probability that a driver will choose to charge an electric vehicle given an initial battery level and determining, based on the final battery level data, an average charging time;

selecting, from the set of locations, candidate locations based on the charging demand distribution;

optimizing placement of the charging stations at one or more of the candidate locations; and

placing a charging station at one of the candidate locations in accordance with the optimized placement of the charging stations.

15. The method of claim 14 wherein predicting the charging demand distribution comprises accumulating expectations of charging time for multiple cars at different time points.

16. The method of claim 14 wherein optimizing the placement of the charging stations comprises determining a solution that minimizes construction cost of the charging stations and maximizes coverage rate provided by the charging stations.