Electric vehicle (EV) charging infrastructure with charging stations optimumally sited

• US 9,132,742 B2
• Filed: 02/23/2012
• Issued: 09/15/2015
• Est. Priority Date: 02/23/2012
• Status: Expired due to Fees

• Current Assignee: Graphite Charging Company LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Dai, Jing D., Deshpande, Ajay A., Kim, Younghun, Li, Ming, Murali, Pavankumar, Sahu, Sambit
• Primary Examiner(s): SMALL, NAOMI J
• Application Number:
  US13/403,046
• Publication Number:
  US 20130222158A1
• Time in Patent Office: 1,300 Days
• Field of Search: 340/995.13
• US Class Current: 1/1
• CPC Class Codes: B60L 2200/12 Bikes
• CPC Class Codes: B60L 2200/18 Buses
• CPC Class Codes: B60L 2240/622 by satellite navigation
• CPC Class Codes: B60L 2240/68 Traffic data
• CPC Class Codes: B60L 2240/70 Interactions with external data bases, e.g. traffic centres
• CPC Class Codes: B60L 2240/72 Charging station selection relying on external data
• CPC Class Codes: B60L 2240/80 Time limits
• CPC Class Codes: B60L 53/14 Conductive energy transfer
• CPC Class Codes: B60L 53/63 in response to network capacity
• CPC Class Codes: B60L 53/68 Off-site monitoring or control, e.g. remote control
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: Y02E 60/00 Enabling technologies; Technologies with a potential or indirect contribution to GHG emissions mitigation
• 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 10/72 Electric energy management in electromobility
• 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: Y04S 10/126 the energy generation units being or involving electric vehicles [EV] or hybrid vehicles [HEV], i.e. power aggregation of EV or HEV, vehicle to grid arrangements [V2G]

Abstract

A system, method and program product for siting charging stations. A mobility detection module collects traffic data from vehicle sensors distributed in an area. A map matching module maps detected traffic in the area. A vehicle flow module temporally characterizes mapped traffic flow. An electric vehicle (EV) requirements (EVR) evaluator determines an optimal number of charging stations and respective locations for siting the charging stations.

Claims

1. A method of locating charging stations comprising:

collecting traffic information from a plurality of traffic sensors;

mapping traffic in an area;

determining flow through zones in said area with respect to time;

recursively determining a number of charging stations and respective locations for siting said charging stations, wherein recursively determining comprises;

providing a set of locations for siting charging stations in said area,

modeling charge demand, the charge demand model identifying a subset of said set of locations with charging EVs as a set of candidate locations and indicating charger use of a plurality of chargers located in each of said set of candidate locations,

modeling facility locations, constraining the facility location model according charger capability at each location, budget constraints, and distances between zones to cull said set of candidate locations,

comparing said set of candidate locations against said set of locations, and when the sets match

providing said set of candidate locations and chargers at each location, said set of candidate locations being a set of locations for EV stations; and

displaying recursively determined charging station sites.

2. A method as in claim 1, wherein for the set of chargers M;

the set of charge demands I;

the set of start time T of time slots;

processing time p_i,m of each demand i on each charger m;

the time r_i at which demand i is ready to begin charging;

the required dwell time w_i of each demand i;

the time d_i at which demand i departs, that is, begin time plus dwell (r_i+w_i);

the cost C_m of installing charger m; and

said charge demand model has the form

3. A system as in claim 1, wherein for the set of candidate locations I to site EV charging stations;

a charger type t, where t=1, 2, 3;

the maximum number of chargers N_tⁱ of type t to be located at i; and

, the distance d_ij between candidate locations i and j;

the total daily demand D_tⁱ for charger type t at i;

a distance threshold Z;

charging capacity w_t of charger type t;

cost C_t of installing a charger of type t; and

total constraint on the budget B;

the actual number of chargers X_tⁱ of type t located at i, the actual demand Y_t^ij for charger type t at i satisfied at j, and the actual demand Y_tⁱ for charger type t located at i satisfied at i, where X_tⁱ, Y_tⁱ, Y_t^ij≧

0;

said facility location model, has the form

4. A method of as in claim 1, whenever said set of candidate locations does not match said set of locations, returning to model charge demand with said set of candidate locations as said set of locations, said method further comprising locating ones of said charging stations at each said respective location in said set of locations for EV stations.

5. A method as in claim 1, wherein collecting traffic information comprises identifying an associated mode of travel for collected data.

6. A method as in claim 5, wherein associated modes of travel include car, bus and bike, and recursively determining further determines the type of chargers at said each respective location.

7. A computer program product for locating charging stations, said computer program product comprising a computer usable medium having computer readable program code stored thereon, said computer readable program code causing a computer executing said code to:

collect traffic information from a plurality of traffic sensors;

map traffic in an area;

determine flow through zones in said area with respect to time;

recursively determine a number of charging stations and respective locations for siting said charging stations in said area, wherein recursively determining further causes said computer to;

provide a set of locations for siting charging stations in said area,

solve a charge demand objective function, the charge demand objective function solution identifying locations with charging EVs as a set of candidate locations and indicating charger use of a plurality of chargers located in each of said set of candidate locations,

solve a facility location objective function, the facility location objective function solution culling said set of candidate locations according charger capability at each location, budget constraints, and distances between zones,

compare said set of candidate locations against said set of locations,

return to solve said charge demand objective function with said set of candidate locations as said set of locations until said set of candidate locations match said set of locations, and when the sets match

provide said set of candidate locations and chargers at each location, said set of candidate locations being a set of locations for EV stations; and

display recursively determined charging station sites.

8. A computer program product for routing travel as in claim 7, wherein for the set of chargers M;

the set of charge demands I;

the set of start time T of time slots;

processing time p_i,m of each demand i on each charger m;

the time r_i at which demand i is ready to begin charging;

the required dwell time w_i of each demand i;

the time d_i at which demand i departs, that is, begin time plus dwell (r_i+w_i);

the cost C_m of installing charger m; and

said charge demand objective function has the form

9. A computer program product for routing travel as in claim 7, wherein for the set of candidate locations I to site EV charging stations;

a charger type t, where t=1, 2, 3;

the maximum number of chargers N_tⁱ of type t to be located at i; and

, the distance d_ij between candidate locations i and j;

the total daily demand D_tⁱ for charger type t at i;

a distance threshold Z;

charging capacity w_t of charger type t;

cost C_t of installing a charger of type t; and

total constraint on the budget B;

the actual number of chargers X_tⁱ of type t located at i, the actual demand Y_t^ij for charger type t at i satisfied at j, and the actual demand Y_tⁱ for charger type t located at i satisfied at i, where X_tⁱ, Y_tⁱ, Y_t^ij≧

0;

said location objective function, has the form

10. A computer program product for routing travel as in claim 7, wherein collected traffic information identifies an associated mode of travel for collected data.

11. A computer program product for routing travel as in claim 10, wherein associated modes of travel include car, bus and bike, and recursively determining further causes said computer to determine the type of chargers at said each respective location.

12. A system for siting charging stations in an area, said system comprising:

a plurality of vehicle sensors distributed in an area;

a modality detection module collecting traffic data from said vehicle sensors;

a map matching module mapping detected traffic in said area;

a vehicle flow module temporally characterizing mapped traffic flow in said area; and

an electric vehicle (EV) requirements (EVR) evaluator determining a number of charging stations and respective locations for siting said charging stations in said area responsive to characterized traffic flow, wherein said modality detection module identifies an associated mode of travel for collected data and said EVR evaluator comprises;

a demand estimator estimating demand at each prospective charging station location,

a charge demand module determining the maximum number of charging station locations to meet all demand, wherein said charge demand module comprises a charge demand optimization model to determine said maximum number of charging station locations as a set of candidate locations, and wherein for the set of chargers M;

the set of charge demands I;

the set of start time T of time slots;

processing time p_i,m of each demand i on each charger m;

the time r_i at which demand i is ready to begin charging;

the required dwell time w_i of each demand i;

the time d_i at which demand i departs, that is, begin time plus dwell (r_i+w_i);

the cost C_m of installing charger m; and

said demand optimization model has the form

13. A system as in claim 12, wherein said EVR evaluator uses an objective function to determine said number of charging stations and said respective locations, said objective function comprising said charge demand module and said location module.

14. A system as in claim 13 wherein on each iteration

said charge demand module is constrained such that only one EV charges at a time in each station and, once begun charging continues until complete;

and

said location module is constrained by the maximum number of chargers at each location, budget constraints, key location database and distances between zones.

15. A system for siting charging stations in an area, said system comprising:

a plurality of vehicle sensors distributed in an area;

a modality detection module collecting traffic data from said vehicle sensors;

a map matching module mapping detected traffic in said area;

a vehicle flow module temporally characterizing mapped traffic flow in said area; and

an electric vehicle (EV) requirements (EVR) evaluator determining a number of charging stations and respective locations for siting said charging stations in said area responsive to characterized traffic flow, wherein said modality detection module identifies an associated mode of travel for collected data and said EVR evaluator comprises;

a demand estimator estimating demand at each prospective charging station location,

a charge demand module determining the maximum number of charging station locations to meet all demand, wherein said charge demand module comprises a charge demand optimization model to determine said maximum number of charging station locations as a set of candidate locations, and wherein for the set of candidate locations I to site EV charging stations;

a charger type t, where t=1, 2, 3;

the maximum number of chargers N_tⁱ of type t to be located at i; and

, the distance d_ij between candidate locations i and j;

the total daily demand D_tⁱ for charger type t at i;

a distance threshold Z;

charging capacity w_t of charger type t;

cost C_t of installing a charger of type t; and

total constraint on the budget B;

the actual number of chargers X_tⁱ of type t located at i, the actual demand Y_t^ij for charger type t at i satisfied at j, and the actual demand Y_tⁱ for charger type t located at i satisfied at i, where X_tⁱ, Y_tⁱ, Y_t^ij≧

0;

said location model, has the form

16. A system as in claim 15, wherein associated modes of travel comprises car, bus and bike.

17. A computer program product for siting charging stations in an area, said computer program product comprising a computer usable medium having computer readable program code stored thereon, said computer readable program code comprising:

computer readable program code means for receiving traffic data from a plurality of vehicle sensors distributed in an area;

computer readable program code means for collecting traffic data from said vehicle sensors;

computer readable program code means for mapping detected traffic in said area;

computer readable program code means for temporally characterizing mapped traffic flow; and

computer readable program code means for determining a number of electric vehicle (EV) charging stations and respective locations for siting said EV charging stations responsive to characterized traffic flow, wherein said computer readable program code means for collecting traffic data identifies an associated mode of travel for collected traffic data, said computer readable program code means for determining a number of EV charging stations comprising;

computer readable program code means for estimating demand at each prospective charging station location,

computer readable program code means for determining the maximum number of charging station locations to meet all demand, wherein determining the maximum number of charging station locations determines said maximum number of charging station locations as a set of candidate locations, and, wherein for the set of chargers M;

the set of charge demands I;

the set of start time T of time slots;

processing time p_i,m of each demand i on each charger m;

the time r_i at which demand i is ready to begin charging;

the required dwell time w_i of each demand i;

the time d_i at which demand i departs, that is, begin time plus dwell (r_i+w_i);

the cost C_m of installing charger m; and

wherein determining the maximum number of charging station locations has the form

18. A computer program product for siting charging stations as in claim 17, said computer readable program code means for identifying associated modes of travel selects travel mode from the group comprising car, bus and bike.

19. A computer program product for siting charging stations in an area, said computer program product comprising a computer usable medium having computer readable program code stored thereon, said computer readable program code comprising:

computer readable program code means for receiving traffic data from a plurality of vehicle sensors distributed in an area;

computer readable program code means for collecting traffic data from said vehicle sensors;

computer readable program code means for mapping detected traffic in said area;

computer readable program code means for temporally characterizing mapped traffic flow; and

computer readable program code means for determining a number of electric vehicle (EV) charging stations and respective locations for siting said EV charging stations responsive to characterized traffic flow, wherein said computer readable program code means for collecting traffic data identifies an associated mode of travel for collected traffic data, said computer readable program code means for determining a number of EV charging stations comprising;

computer readable program code means for estimating demand at each prospective charging station location,

computer readable program code means for determining the maximum number of charging station locations to meet all demand, wherein determining the maximum number of charging station locations determines said maximum number of charging station locations as a set of candidate locations, wherein for the set of candidate locations I to site EV charging stations;

a charger type t, where t=1, 2, 3;

the maximum number of chargers N_tⁱ of type t to be located at i; and

, the distance d_ij between candidate locations i and j;

the total daily demand D_tⁱ for charger type t at i;

a distance threshold Z;

charging capacity w_t of charger type t;

cost C_t of installing a charger of type t; and

total constraint on the budget B;

the actual number of chargers X_tⁱ of type t located at i, the actual demand Y_t^ij for charger type t at i satisfied at j, the actual demand Y_tⁱ for charger type t located at i satisfied at i, where X_tⁱ, Y_tⁱ, Y_t^ij≧

0; and

wherein selecting the charging station locations has the form

20. A computer program product for siting charging stations as in claim 19, wherein said computer readable program code means for determining a number of EV charging stations comprises an objective function for determining said number of EV charging stations and said respective locations.

21. A computer program product for siting charging stations as in claim 20, wherein on each iteration

said computer readable program code means for determining the maximum number of charging station locations is constrained such that only one EV charges at a time in each station and, once begun charging continues until complete;

and

said computer readable program code means for selecting the charging station locations is constrained by the maximum number of chargers at each location, budget constraints, key location database and distances between zones.