FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
METHOD AND SYSTEM FOR IDENTIFICATION OF CHARGING STATION LOCATION BASED ON DATA DRIVEN OPTIMIZATION
Applicant
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India
Preamble to the description:
The following specification particularly describes the invention and the manner in which it is to be performed.
2
TECHNICAL FIELD
[001]
The disclosure herein generally relates to identification of charging station location and, more particularly, to a method and a system for identification of charging station location based on data driven optimization.
5
BACKGROUND
[002]
The green technology revolution has led to a rise in popularity of electric vehicles. The adoption of environmentally friendly modes of transportation such as Electric vehicle (EV) leads to significant reduction in greenhouse gas emissions. Unlike conventional petrol, gasoline or diesel-powered vehicles, EVs 10 produce lower or zero tailpipe emissions, thus mitigating climate change.
[003]
Despite the rapid growth seen in adoption of EVs, several barriers such as high purchase costs, limited range, long charging time and lack of widespread charging infrastructures remain challenges. The major concern with EVs is the lack of power and charging infrastructure. While planning charging 15 infrastructure, choosing the correct location of the charging infrastructure is crucial.
[004]
The state-of-art techniques to identify the location of charging infrastructure/station are based on pure optimization techniques. The optimization techniques are based on a static number of charging stations, hence may not effectively output the global optimal solution for the city. Further very few 20 techniques are implemented using data-based techniques, wherein the objective functions are selected based on nature of the data, which may leave gaps in the solution. Further, most existing techniques are not performed at real-time. Hence there is a requirement for a more robust technique for identification of the location of charging infrastructure in real-time. 25
SUMMARY
[005]
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one 30
3
embodiment, a method for
identification of charging station location based on data driven optimization is provided.
[006]
The system includes a memory storing instructions, one or more communication interfaces, and one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more 5 hardware processors are configured by the instructions to receive a plurality of inputs comprising a city map of a city, a traffic count location, a daily traffic count for the traffic count location, a traffic threshold, and a location count threshold, a distance threshold and a traffic load threshold. The system is further configured to divide the city map into a first set of grids, via the one or more hardware processors, 10 wherein the first set of grids are equal size grids covering the city. The system is further configured to identify one or more of the first set of grids as a plurality of candidate grids, via the one or more hardware processors, based on a grid identification technique. The system is further configured to estimate a traffic density for each of the candidate grids, via the one or more hardware processors, 15 based on the daily traffic count for the traffic count location. The system is further configured to cluster the first set of grids and the plurality of candidate grids to generate a set of clustered grids, via the one or more hardware processors, using a clustering technique based on a computed cumulative sum. The system is further configured to compute a total score, via the one or more hardware processors, 20 wherein the total score is a summation of a distance penalty and a traffic penalty, wherein, the distance penalty is computed based on the distance threshold and a maximum distance, wherein the maximum distance is computed between the first set of grids and the plurality of candidate grids, and the traffic penalty is computed based on the traffic density and the traffic load threshold in the first set of grids. 25 The system is further configured to identify a final set of candidate locations from the set of clustered grids using the traffic density, the distance, the traffic load threshold, and the distance threshold, based on an iterative optimization technique, via the one or more hardware processors, wherein the iterative optimization technique comprises performing for all sub-clusters in the set of clustered grids: 30 identifying an candidate cluster from the set of clustered grids based on the traffic
4
density, the distance, and the total score with the distance threshold and the traffic
load threshold; identifying atleast one candidate grid from the candidate cluster based on the total score and removing all the other grids except for the identified candidate grid from the set of clustered grids based on a selection-removal process; and selecting an candidate location from the identified at least one candidate grid, 5 wherein the candidate location is selected for all sub-clusters in the set of clustered grids to form the final set of candidate locations.
[007]
In another aspect, a method for identification of charging station location based on data driven optimization is provided. The method includes receiving, via one or more hardware processors, a plurality of inputs comprising a 10 city map of a city, a traffic count location, a daily traffic count for the traffic count location, a traffic threshold, and a location count threshold, a distance threshold and a traffic load threshold. The method includes dividing the city map into a first set of grids, via the one or more hardware processors, wherein the first set of grids are equal size grids covering the city. The method includes identifying one or more of 15 the first set of grids as a plurality of candidate grids, via the one or more hardware processors, based on a grid identification technique. The method includes estimating a traffic density for each of the candidate grids, via the one or more hardware processors, based on the daily traffic count for the traffic count location. The method includes clustering the first set of grids and the plurality of candidate 20 grids to generate a set of clustered grids, via the one or more hardware processors, using a clustering technique based on a computed cumulative sum. The method includes computing a total score, via the one or more hardware processors, wherein the total score is a summation of a distance penalty and a traffic penalty, wherein, the distance penalty is computed based on the distance threshold and a maximum 25 distance, wherein the maximum distance is computed between the first set of grids and the plurality of candidate grids, and the traffic penalty is computed based on the traffic density and the traffic load threshold in the first set of grids. The method includes identifying a final set of candidate locations from the set of clustered grids using the traffic density, the distance, the traffic load threshold, and the distance 30 threshold, based on an iterative optimization technique, via the one or more
5
hardware processors, wherein the iterative optimization technique comprises
performing for all sub-clusters in the set of clustered grids: identifying an candidate cluster from the set of clustered grids based on the traffic density, the distance, and the total score with the distance threshold and the traffic load threshold; identifying atleast one candidate grid from the candidate cluster based on the total score and 5 removing all the other grids except for the identified candidate grid from the set of clustered grids based on a selection-removal process; and selecting an candidate location from the identified at least one candidate grid, wherein the candidate location is selected for all sub-clusters in the set of clustered grids to form the final set of candidate locations. 10
[008]
In yet another aspect, a non-transitory computer readable medium for identification of charging station location based on data driven optimization is provided. The method includes receiving, via one or more hardware processors, a plurality of inputs comprising a city map of a city, a traffic count location, a daily traffic count for the traffic count location, a traffic threshold, and a location count 15 threshold, a distance threshold and a traffic load threshold. The method includes dividing the city map into a first set of grids, via the one or more hardware processors, wherein the first set of grids are equal size grids covering the city. The method includes identifying one or more of the first set of grids as a plurality of candidate grids, via the one or more hardware processors, based on a grid 20 identification technique. The method includes estimating a traffic density for each of the candidate grids, via the one or more hardware processors, based on the daily traffic count for the traffic count location. The method includes clustering the first set of grids and the plurality of candidate grids to generate a set of clustered grids, via the one or more hardware processors, using a clustering technique based on a 25 computed cumulative sum. The method includes computing a total score, via the one or more hardware processors, wherein the total score is a summation of a distance penalty and a traffic penalty, wherein, the distance penalty is computed based on the distance threshold and a maximum distance, wherein the maximum distance is computed between the first set of grids and the plurality of candidate 30 grids, and the traffic penalty is computed based on the traffic density and the traffic
6
load threshold in the
first set of grids. The method includes identifying a final set of candidate locations from the set of clustered grids using the traffic density, the distance, the traffic load threshold, and the distance threshold, based on an iterative optimization technique, via the one or more hardware processors, wherein the iterative optimization technique comprises performing for all sub-clusters in the set 5 of clustered grids: identifying an candidate cluster from the set of clustered grids based on the traffic density, the distance, and the total score with the distance threshold and the traffic load threshold; identifying atleast one candidate grid from the candidate cluster based on the total score and removing all the other grids except for the identified candidate grid from the set of clustered grids based on a selection-10 removal process; and selecting an candidate location from the identified at least one candidate grid, wherein the candidate location is selected for all sub-clusters in the set of clustered grids to form the final set of candidate locations.
[009]
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not 15 restrictive of the invention, as claimed.
BRIEF DESCRIPTION OF THE DRAWINGS
[010]
The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together 20 with the description, serve to explain the disclosed principles:
[011]
FIG.1 illustrates an exemplary system for identification of charging station location based on data driven optimization according to some embodiments of the present disclosure.
[012]
FIG.2 is a functional block diagram for identification of charging 25 station location based on data driven optimization according to some embodiments of the present disclosure.
[013]
FIGS.3A-3C is a flow diagram illustrating a method (300) for identification of charging station location based on data driven optimization in accordance with some embodiments of the present disclosure. 30
7
[014]
FIG.4 illustrates a city map along with a plurality of grids in accordance with some embodiments of the present disclosure.
[015]
FIG.5 is a flow diagram illustrating a method (500) for grid identification technique in accordance with some embodiments of the present disclosure. 5
[016]
FIG.6 illustrates plurality of candidate grids identified in the city map in accordance with some embodiments of the present disclosure.
[017]
FIG.7 illustrates the clustered grids in the city map in accordance with some embodiments of the present disclosure.
[018]
FIG.8 is a flow diagram illustrating a method (800) for performing 10 the clustering technique in accordance with some embodiments of the present disclosure.
[019]
FIG.9 to FIG.18 illustrate the identification of a final set of candidate locations in the city map in accordance with some embodiments of the present disclosure. 15
[020]
FIG.19 illustrates grid wise average traffic density during the experimentation for identification of charging station location based on data driven optimization in accordance with some embodiments of the present disclosure.
[021]
FIG.20 illustrates a final set of candidate locations identified during the experimentation for identification of charging station location based on data 20 driven optimization in accordance with some embodiments of the present disclosure.
DETAILED DESCRIPTION OF EMBODIMENTS
[022]
Exemplary embodiments are described with reference to the 25 accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are 30 possible without departing from the scope of the disclosed embodiments.
8
[023]
Electric vehicles (EVs) have rapidly become popular as a green mode of transport. This has brought on a revolution in both technology and government policy . However, despite the rapid growth seen in adoption of EVs, several barriers still exist, such as high purchase costs, limited range, long charging time and lack of widespread charging infrastructures etc, these are big hurdles to 5 the future growth of the EV market. In the planning of EV related infrastructure, the location of the battery charging station has great importance. The current disclosure is a flow-based solution approach for identification of charging station location that is based on daily traffic count data using data driven optimization techniques. 10
[024]
Referring now to the drawings, and more particularly to FIG.1 through FIG.20, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments, and these embodiments are described in the context of the following exemplary system and/or method. 15
[025]
FIG.1 is an exemplary block diagram of a system 100 for identification of charging station location based on data driven optimization in accordance with some embodiments of the present disclosure.
[026]
In an embodiment, the system 100 includes a processor(s) 104, communication interface device(s), alternatively referred as input/output (I/O) 20 interface(s) 106, and one or more data storage devices or a memory 102 operatively coupled to the processor(s) 104. The system 100 with one or more hardware processors is configured to execute functions of one or more functional blocks of the system 100.
[027]
Referring to the components of the system 100, in an embodiment, 25 the processor(s) 104, can be one or more hardware processors 104. In an embodiment, the one or more hardware processors 104 can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other 30 capabilities, the one or more hardware processors 104 is configured to fetch and
9
execute computer
-readable instructions stored in the memory 102. In an embodiment, the system 100 can be implemented in a variety of computing systems including laptop computers, notebooks, hand-held devices such as mobile phones, workstations, mainframe computers, servers, a network cloud and the like.
[028]
The I/O interface(s) 106 can include a variety of software and 5 hardware interfaces, for example, a web interface, a graphical user interface, a touch user interface (TUI) and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface (s) 106 can include one or more ports 10 for connecting a number of devices (nodes) of the system 100 to one another or to another server.
[029]
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random-access memory (SRAM) and dynamic random-access memory (DRAM), and/or 15 non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
[030]
Further, the memory 102 may include a database 108 configured to include information regarding for identification of charging station location based on data driven optimization. The memory 102 may comprise information pertaining 20 to input(s)/output(s) of each step performed by the processor(s) 104 of the system 100 and methods of the present disclosure. In an embodiment, the database 108 may be external (not shown) to the system 100 and coupled to the system via the I/O interface 106.
[031]
Functions of the components of system 100 are explained in 25 conjunction with functional overview of the system 100 in FIG.2 and flow diagram of FIGS.3A and FIG.3C for identification of charging station location based on data driven optimization.
[032]
The system 100 supports various connectivity options such as BLUETOOTH®, USB, ZigBee and other cellular services. The network 30 environment enables connection of various components of the system 100 using
10
any communication link including Internet, WAN, MAN, and so on. In an
exemplary embodiment, the system 100 is implemented to operate as a stand-alone device. In another embodiment, the system 100 may be implemented to work as a loosely coupled device to a smart computing environment. The components and functionalities of the system 100 are described further in detail. 5
[033]
FIG.2 is an example functional block diagram of the various modules of the system of FIG.1, in accordance with some embodiments of the present disclosure. As depicted in the architecture, the FIG.2 illustrates the functions of the modules of the system 100 that includes for identification of charging station location based on data driven optimization. 10
[034]
As depicted in FIG.2, the functional system 200 of the system 100 is configured for identification of charging station location based on data driven optimization.
[035]
The system 200 comprises an input module 202 configured for receiving a plurality of inputs comprising a city map of a city, a traffic count 15 location, a daily traffic count for the traffic count location, a traffic threshold, and a location count threshold, a distance threshold and a traffic load threshold. The system 200 further comprises a divider 204 configured for dividing the city map into a first set of grids, wherein the first set of grids are equal size grids covering the city. The system 200 further comprises a grid identifier 206 configured for 20 identifying one or more of the first set of grids as a plurality of candidate grids, based on a grid identification technique. The system 200 further comprises a traffic density estimator 208 configured for estimating the traffic density for each of the candidate grids based on the daily traffic count for each of the traffic count location. The system 200 further comprises clusterer 210 configured for clustering the first 25 set of grids and the plurality of candidate grids to generate a set of clustered grids, using a clustering technique based on computing a cumulative sum. The system 200 further comprises scorer 212 configured for computing a total score, wherein the total score is a summation of a distance penalty and a traffic penalty. The system 200 further comprises optimizer 214 configured for identifying a final set of 30 candidate locations from the set of clustered grids using the traffic density and the
11
distance threshold based on an iterative optimization technique, wherein the
iterative optimization technique comprises performing for all sub-clusters in the set of clustered grids.
[036]
The various modules of the system 100 and the functional blocks in FIG.2 are configured for identification of charging station location based on data 5 driven optimization are implemented as at least one of a logically self-contained part of a software program, a self-contained hardware component, and/or, a self-contained hardware component with a logically self-contained part of a software program embedded into each of the hardware component that when executed perform the above method described herein. 10
[037]
Functions of the components of the system 200 are explained in conjunction with functional modules of the system 100 stored in the memory 102 and further explained in conjunction with flow diagram of FIGS.3A-3C. The FIGS.3A-3C with reference to FIG.1, is an exemplary flow diagram illustrating a method 300 for identification of charging station location based on data driven 15 optimization using the system 100 of FIG.1 according to an embodiment of the present disclosure.
[038]
The steps of the method of the present disclosure will now be explained with reference to the components of the system 100 of FIG.1 for identification of charging station location based on data driven optimization and the 20 modules 202-214 as depicted in FIG.2 and the flow diagrams as depicted in FIGS.3A-3C. Although process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the 25 steps to be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.
[039]
At step 302 of method 300, a plurality of inputs is received in the input module 202. The plurality of inputs comprising a city map of a city, a traffic 30
12
count location, a daily traffic count for the traffic count location, a
traffic threshold, a location count threshold, a distance threshold, and a traffic load threshold.
[040]
In an embodiment, the city map includes data in terms of co-ordinates, wherein the co-ordinates are translated from geographic data. The traffic count locations represent locations in the city where traffic count is measured. The 5 daily traffic count indicates number of vehicles that have passed through the traffic count locations in a day. Further, the traffic threshold is determined based on a plurality of statistical techniques as a number above which traffic count location is categorized as high density/ highly visited location and is used to find high density/ highly visited locations. The location count threshold is utilized to identify the 10 candidate street in the city.
[041]
The distance threshold is the maximum distance between a user vehicle and the nearest charging station when a user is travelling through the city. The distance threshold helps user get services without depleting too much vehicle battery charge while searching and travelling towards a battery recharge location. 15 The traffic load threshold is maximum traffic limit in the service area of charging station. The city map also comprises a plurality of locations and a plurality of street.
[042]
At step 304 of method 300, the city map is divided into a first set of grids in divider 204. The first set of grids are equal size grids covering the city.
[043]
In an embodiment, the first set of grids are equal size grids - wherein 20 in an example scenario the grid is one of a square shaped grid or a rectangular shaped grid. The entire city map is divided it several grids of a pre-defined size, wherein the pre-defined size is determined such that the grids formed are equal sized. In an example scenario the city map is a 2-Dimensional diagram with a X- axis and a Y- Axis, where a lower limit and an upper limit is defined at both the X- 25 axis and the Y- Axis and the city map is partitioned into several intervals (pre-defined size) and perpendicular lines drawn through the city map from those intervals creating the square/rectangular grids. Similarly, several types of logic grids with different shapes can be generated.
[044]
In an example scenario, as shown in FIG.4 the city map is divided 30 into 10x10 equal square grids.
13
[045]
At step 306 of method 300, one or more of the first set of grids are identified as a plurality of candidate grids in grid identifier 206. The identification of plurality of candidate grids is based on a grid identification technique. The grid identification technique is explained using FIG.5.
[046]
At step 502 of method 500, a plurality of high-density locations is 5 identified based on the traffic threshold.
[047]
In an embodiment, the high-density location is identified from the plurality of locations, wherein a location from the plurality of locations having a daily traffic count higher than the “traffic threshold” is identified as the high-density location. 10
[048]
At step 504 of method 500, a plurality of candidate streets is identified from the plurality of streets, wherein a street from the plurality of streets is identified as a candidate street based on the plurality of high-density location and the location count threshold
[049]
In an embodiment, the plurality of candidate streets are identified 15 when the Street which has total number of the high-density locations are more than the location count threshold.
[050]
At step 506 of method 500, a plurality of candidate locations is identified based on the plurality of candidate streets and the traffic count location.
[051]
In an embodiment, upon identification of a street as a candidate 20 street, all the traffic count locations falling on those “candidate street” are selected as the candidate locations.
[052]
At step 508 of method 500, a plurality of candidate grids is identified based on the plurality of candidate location.
[053]
In an embodiment, the first set of grids which contain one of the 25 plurality of candidate locations is identified as candidate grid. The plurality of candidate grids thus identified are a subset of the first set of grids.
[054]
In an example scenario, as shown in FIG.6 the plurality of candidate grids is identified and highlighted in the FIG.6, where the highlighted grid indicates the plurality of candidate grids while the remaining grids indicate the first set of 30 grids. At step 308 of method 300, the traffic density is estimated for each of the
14
candidate grids
in traffic density estimator 208. The traffic density is estimated based on the daily traffic count for each of the traffic count location.
[055]
In an embodiment, the traffic density is defined as follows:
T𝐷𝑗= Σ𝑇𝑖𝑗𝑛𝑗𝑖=1𝑛𝑗,∀ 𝑖 ∈𝑔𝑟𝑖𝑑𝑗 = 0,𝑖𝑓 𝑇𝑖𝑗 =𝜙 ∀ 𝑖 ∈𝑔𝑟𝑖𝑑𝑗
where, 𝑛𝑗=𝑡𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑐𝑜𝑢𝑛𝑡 𝑝𝑜𝑖𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑔𝑟𝑖𝑑𝑗 𝑇𝑖𝑗= 𝐷𝑎𝑖𝑙𝑦 𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑐𝑜𝑢𝑛𝑡 𝑖𝑛 𝑖𝑡ℎ 𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛 𝑓𝑟𝑜𝑚 𝑗𝑡ℎ 𝑔𝑟𝑖𝑑,𝑎𝑛𝑑 𝑇𝐷𝑗= 𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑑𝑒𝑛𝑠𝑖𝑡𝑦 𝑎𝑡 𝑔𝑟𝑖𝑑𝑗
(1)
[056]
At step 310 of method 300, the first set of grids and the plurality of candidate grids is clustered to generate a set of clustered grids in the clusterer 210. 5 In an example scenario, the grids are clustered as shown in FIG.7.
[057]
Clustering is performed using a clustering technique based on computing a cumulative sum. The clustering technique is explained with reference to FIG.8 as below:
[058]
At step 802 of method 800, a distance is computed between the 10 candidate grid and the first set of grids.
[059]
In an embodiment, the distance is computed for each candidate grid from the plurality of candidate grids with all the first set of grids from the first set of grids based on a shortest distance algorithm that includes one of a Dijkstra's algorithm, Kruskal’s algorithm based on distance metric such as Haversine 15 distance, Manhatten distance, Euler distance and so on.
[060]
In an example scenario, given a city map of Bengaluru city with a Distance Threshold equal to 10 km, and the Traffic Load Threshold equal to 11000 vehicle/day and the traffic load is given. The distance is computed between the candidate grid and the first set of grids as shown below: 20
First set of Grid Number
Distance
Traffic load
1
1
1321
15
2
1
1110
3
10
1822
4
7
2183
5
4
1139
6
12
1460
7
13
2129
8
6
619
9
13
561
10
13
2047
11
3
1032
12
2
1507
13
6
564
14
5
2185
15
13
1256
Table 1: Distance computed
[061]
At step 804 of method 800, a subset of first set of grids is selected based on the distance threshold.
[062]
In an embodiment, a subset of first set of grids selected from the first set of grids, wherein all first set of grids having a distance less than the distance 5 threshold are selected for next step as the subset of first set of grid.
[063]
In an example scenario, with furtherance to Table 1, the subset of first set of grid is selected based on the distance threshold, which in the given case is 10 Kms, hence the first set of grids with distance more than 10 is not considered. The subset of first set of grids is selected is shared below: 10
First set of Grid Number
Distance
Traffic load
16
1
1
1321
2
1
1110
12
2
1507
11
3
1032
5
4
1139
14
5
2185
8
6
619
13
6
564
4
7
2183
3
10
1822
Table 2: Selected subset of first set of grids.
[064]
At step 806 of method 800, a cumulative sum is computed based on the distance between the subset of first set of grids and plurality of candidate grids. The cumulative sum represents a cumulative sum of the traffic density.
[065]
In an embodiment, each first set of grid from the subset of “first set 5 of grid” are sorted in an increasing order based on the distance between them and a selected “candidate grid”. Upon ordering the subset of first set of grids, a cumulative traffic density is computed between consecutive first set of grid as shown below for the example scenario used in Table 1 and Table 2and the same is shared below in Table 3; 10
17
Table 3 : Computation of cumulative sum
[066]
At step 808 of method 800, the subset of first set of grids and the plurality of candidate grids is clustered to generate the set of clustered grids. The set of clustered grids comprises atleast one candidate grids.
[067]
The set of clustered grids is generated based on a cumulative sum of 5 traffic density, the traffic load threshold, and the distance threshold.
[068]
In an embodiment, the subset of first set of grids is selected based on the distance threshold. The selected set of clustered grids is generated from
First set of Grid number
Distance
Traffic load
Cumulative Traffic Load
1
1
1321
1321
2
1
1110
2431
12
2
1507
3938
11
3
1032
4970
5
4
1139
6109
14
5
2185
8294
8
6
619
8913
13
6
564
9477
4
7
2183
11660
3
10
1822
13482
18
subset of
first set of grids with their corresponding cumulative traffic density lower that the traffic load threshold.
[069]
In furtherance to the example scenario shared in Table1, 2 and 3, The set of clustered grids is generated based on a comparison between the cumulative sum of traffic density and the traffic load threshold, wherein for the 5 given scenario the traffic load threshold is equal to 11000 vehicle/day. Hence the first set of grids with traffic load threshold less than 11000 vehicle/day is clustered into a candidate cluster.
First set of Grid Number
Distance
Traffic load
Cumulative Traffic Load
1
1
1321
1321
2
1
1110
2431
12
2
1507
3938
11
3
1032
4970
5
4
1139
6109
14
5
2185
8294
8
6
619
8913
13
6
564
9477
Table 4: Selection of subset of first set of grids for candidate cluster.
[070]
The set of clustered grids contains atleast one “candidate grid”, 10 including selected “candidate grid”.
19
[071]
At step 312 of the method 300, a total score is computed in the scorer 212. The total score is a summation of a distance penalty and a traffic penalty, where:
•
The distance penalty is computed based on the distance threshold and a maximum distance, wherein the maximum distance is computed between 5 the first set of grids and the plurality of candidate grids.
•
The traffic penalty is computed based on the traffic density and the traffic load threshold in the first set of grids.
[072]
In an embodiment, the distance penalty is computed as:
𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗=𝑀𝑎𝑥𝑑𝑖𝑠𝑡𝐷𝑖𝑠𝑡𝑇ℎ𝑟𝑒𝑠 (2) 10
where, 𝑀𝑎𝑥𝑑𝑖𝑠𝑡=𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑡ℎ𝑒 𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑒𝑑 𝐶ℎ𝑎𝑟𝑔𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 𝑎𝑛𝑑 𝑡ℎ𝑒 𝐹𝑖𝑙𝑡𝑒𝑟𝑒𝑑 𝑔𝑟𝑖𝑑𝑠 𝑖𝑛𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑑 𝑤𝑖𝑡ℎ 𝑖𝑡 𝑖 𝐷𝑖𝑠𝑡𝑡ℎ𝑒𝑠15 =𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑡ℎ𝑎𝑡 𝑐ℎ𝑎𝑟𝑔𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 𝑠ℎ𝑜𝑢𝑙𝑑 𝑖𝑑𝑒𝑎𝑙𝑙𝑦 𝑠𝑒𝑟𝑣𝑒 𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗=𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑
[073]
In an embodiment, the traffic penalty is computed as:
𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗=𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠−𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑 𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠,𝑖𝑓 |𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠−𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑|>𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑡𝑜𝑙 = 0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
(3)
where, 20
𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑= Σ𝑇𝐷𝑖 ∀ 𝑖 𝑚𝑎𝑝𝑝𝑒𝑑 𝑡𝑜 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑙𝑒 𝑔𝑟𝑖𝑑𝑖 𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑡𝑜𝑙=𝑇𝑜𝑙𝑒𝑟𝑒𝑛𝑐𝑒 𝑏𝑎𝑛𝑑 𝑓𝑜𝑟 𝑡𝑜𝑡𝑎𝑙 𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑡𝑜 𝑏𝑒 𝑠𝑒𝑟𝑣𝑒𝑑 𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗=𝑇𝑟𝑎𝑓𝑓𝑖𝑐 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑
(4)
20
[074]
In an embodiment, the total score is computed as:
𝑇𝑜𝑡𝑎𝑙𝑠𝑐𝑜𝑟𝑒𝑗 = (𝑤1∗𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗 + 𝑤2∗𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗) (5)
where,
{𝑤1 ,𝑤2} 𝑎𝑟𝑒 𝑡ℎ𝑒 𝑤𝑒𝑖𝑔ℎ𝑡𝑎𝑔𝑒𝑠, and 5
𝑇𝑜𝑡𝑎𝑙𝑠𝑐𝑜𝑟𝑒𝑗 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑.
[075]
At step 314 of method 300, a final set of candidate locations is identified from the set of clustered grids in the optimizer 214. The final set of candidate locations is identified using the traffic density, the traffic load threshold and the distance threshold based on an iterative optimization technique. The 10 iterative optimization technique is a data-driven technique, that comprises of performing steps 314A to 314C for all sub-clusters in the set of clustered grids:
[076]
At step 314A of method 300, a candidate cluster is identified from the set of clustered grids based on the traffic density and the total score.
[077]
In an embodiment, the first set of grids having cumulative 15 summation of traffic density less than the traffic_load threshold is selected as the set of first set of grids. The set of first set of grids is also referred to as a set of clusters. The total score is computed for each iteration, hence a candidate grid is identified as the first set of grids having cumulative summation of traffic density less than the traffic_load threshold for every iteration. 20
[078]
At step 314B of method 300, atleast one candidate grid is identified from the candidate cluster based on the total score.
[079]
Further, all the other grids except for the identified candidate grid are removed from the set of clustered grids based on a selection-removal process. The identified candidate grid is further included in the final set of candidate 25 locations and will not be used for the next iterations.
[080]
In an embodiment, the clusters having lower scores are identified as the candidate cluster.
21
[081]
In the example scenario as shown in FIG.9, the total score is estimated for each of the clusters, wherein the cluster 3 with total score 4.5 is identified as the cluster with least score. The candidate grid is selected and removed while the other grids are retained as shown in FIG.10.
[082]
At step 314C of method 300, a candidate location is selected from 5 the identified candidate grid. The candidate location selected for all sub-clusters in the set of clustered grids to form the final set of candidate locations.
[083]
In an embodiment, any candidate location falling within the candidate grid is selected as final location. The high-density location within the selected grid may have more than one candidate location, in such a case, the 10 candidate location with lowest total score is selected as candidate location. The selection of the candidate location from the identified candidate grid. The selection of the candidate location from the identified candidate grid is explained in example scenario as shown in FIG.10 and FIG.11, the cluster 3 has two high-density locations, with total scores 3 (co-ordinates 4,7) and 7 (co-ordinates 3,9). In this 15 example, the high-density locations with total scores 3 is selected as an candidate location as it has a lower total score compared to the high-density locations with total scores 7
[084]
The above steps 314A to 314C is performed for all sub-clusters in the set of clustered grids to identify the final set of candidate locations. 20
[085]
In the first iteration, the cluster 3 has lowest total score, hence the candidate location within cluster 3 is identified within the final set of candidate locations as CS-1, and the cluster 3 is removed. For the second iteration, the traffic density and the total score are updated and then the candidate cluster is selected, wherein cluster 3 has a lowest total score of 3 at co-ordinates 4,7. Further cluster 3 25 also has another candidate location with a total score of 8 at co-ordinate 3,9. However among the two candidate locations, the candidate location with lower score is selected as CS-2 as shown in FIG.11 and FIG.12. Further for the third iteration, the total score are updated and then the candidate cluster is selected, wherein cluster 2 is identified as the candidate cluster and the high-density locations 30 with total scores 8 is selected as a candidate location for the final set of candidate
22
locations
as CS-3 as shown in FIG.13 and FIG.14 . For the fourth iteration, the total score are updated and then the candidate cluster is selected, wherein cluster 1 is identified as the candidate cluster and the high-density locations with total scores 11 is selected as a candidate location for the final set of candidate locations as CS-4 as shown in FIG.15 and FIG.16. For the final iteration, the remaining cluster 1 is 5 identified as the candidate cluster and the high-density locations with total scores 14 is selected as a candidate location for the final set of candidate locations as CS-5 as shown in FIG.17 and FIG.18. Hence in FIG.18, the final set of candidate locations are identified.
[086]
EXPERIMENTS: 10
[087]
An experiment has been set-up to understand the performance of the for identification of charging station location based on data driven optimization by considering an use case example of City of Chicago. Chicago has very good road connectivity. The length of the road network totals to ~1900 km in length that spans to all parts of the city. All the road network data including geometric data of 15 networks within the city is collected from Candidate streets data made available by Chicago municipal corporation and the streets are classified into 15 street types. Further average traffic count data made available by Chicago municipal corporation is used for this analysis. Data is collected for 1279 locations, falling on 251 streets, which contains total number of vehicles passing through each location in one day. 20 Dataset also contains the coordinates of those locations in terms of latitude and longitude, as well as date of count. Average traffic count data contains a traffic count of important locations in the city. It has a range of 700 to 165200 vehicles passing through traffic collection point in a day. Most of the traffic count points see total number of vehicles from ~10000 to ~50000 in day passing from it. Using this 25 data, average traffic per grid is calculated as per described in the equation (1). Grid wise average traffic density is shown in the FIG.19. The disclosed technique is applied on the Chicago city map and a final set of candidate locations is as shown in the FIG.20.
[088]
Further, the disclosed technique has been compared with a K-30 medoids algorithm, wherein the K-Medoids algorithm selects the cluster centers
23
from the data points provided for the training.
The disclosed technique recommends a total number of 46 charging stations to be established to cover entire the city meeting all the criterions of maximum distance and maximum traffic load, while the K-Medoids algorithm suggested total number of 43 clusters, i.e. to open charging center at 43 medoids. Hence it can inferred that the disclosed technique 5 performs better than the K-medoids algorithm.
[089]
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are 10 intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.
[090]
This disclosure relates generally to identification of charging station location based on data driven optimization. The disclosed technique is a flow-based 15 solution approach that is based on Daily traffic count data. The disclosed technique analyses, traffic condition from vehicle count data, geography of the city or area of interest, road networks, charging station operation constraints etc. to identify a set of candidate locations required to cover entire city or area of the interest based on a score-based ranking of each candidate location 20
[091]
It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device 25 can be any kind of device which can be programmed including e.g., any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g., hardware means like e.g., an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g., an 30 ASIC and an FPGA, or at least one microprocessor and at least one memory with
24
software
processing components located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g., using a plurality of CPUs. 5
[092]
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various components described herein may be implemented in other components or combinations of other components. For the purposes of this description, a 10 computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
[093]
The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological 15 development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are 20 appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are 25 intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise. 30
25
[094]
Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more 5 processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, 10 nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
[095]
It is intended that the disclosure and examples be considered as exemplary only, with a true scope of disclosed embodiments being indicated by the following claims. 15

We Claim:
1.
A processor implemented method (300), comprising:
receiving, via one or more hardware processors, a plurality of inputs comprising a city map of a city, a traffic count location, a daily traffic count for the traffic count location, a traffic threshold, and a location count threshold, a distance threshold and a traffic load threshold (302);
dividing the city map into a first set of grids, via the one or more hardware processors, wherein the first set of grids are equal size grids covering the city (304);
identifying one or more of the first set of grids as a plurality of candidate grids, via the one or more hardware processors, based on a grid identification technique (306);
estimating a traffic density for each of the candidate grids, via the one or more hardware processors, based on the daily traffic count for the traffic count location (308);
clustering the first set of grids and the plurality of candidate grids to generate a set of clustered grids, via the one or more hardware processors, using a clustering technique based on a computed cumulative sum (310);
computing a total score (312), via the one or more hardware processors, wherein the total score is a summation of a distance penalty and a traffic penalty, wherein,
the distance penalty is computed based on the distance threshold and a maximum distance, wherein the 25 maximum distance is computed between the first set of grids and the plurality of candidate grids, and
the traffic penalty is computed based on the traffic density and the traffic load threshold in the first set of grids; and

identifying a final set of locations from the set of clustered grids using the traffic density, the distance, the traffic load threshold, and the distance threshold, based on an iterative optimization technique (314), via the one or more hardware processors, wherein the iterative optimization technique 5 comprises performing for all sub-clusters in the set of clustered grids:
identifying a cluster from the set of clustered grids based on the traffic density, the distance, and the total score with the distance threshold and the traffic load threshold (314A);
identifying atleast one candidate grid from the identified cluster based on the total score and removing all the other grids except for the identified grid from the set of clustered grids based on a selection-removal process (314B); and
selecting a candidate location from the identified at least one candidate grid, wherein the candidate location is selected for all sub-clusters in the set of clustered grids to form the final set of candidate locations (314C).
2.
The method as claimed in claim 1, wherein the grid identification technique (500) comprises:
identifying a plurality of high-density locations based on the traffic threshold (502);
identifying a plurality of candidate streets based on the plurality of high-density location and the location count threshold (504);
identifying a plurality of candidate locations based on the plurality of candidate streets and the traffic count location (506); and
identifying a plurality of candidate grids based on the plurality of candidate location (510).

3.
The method as claimed in claim 1, wherein the clustering technique (800) performed for each candidate grid from the plurality of candidate grids, comprises:
computing a distance score between the candidate grid and the first set of grids (802);
selecting a subset of first set of grids based on the distance threshold (804);
computing a cumulative sum based on a distance between the subset of first set of grids and plurality of candidate grids, wherein the cumulative sum represents a cumulative sum of the traffic density (806); and
clustering the subset of first set of grids and the plurality of candidate grids to generate the set of clustered grids based on the cumulative sum of traffic density, the traffic load threshold, the distance threshold, wherein the set of clustered grids comprises atleast one candidate grids (808).
4.
The method as claimed in claim 1, wherein computation of the distance penalty is expressed as :
𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗=𝑀𝑎𝑥𝑑𝑖𝑠𝑡𝐷𝑖𝑠𝑡𝑇ℎ𝑟𝑒𝑠
where, 𝑀𝑎𝑥𝑑𝑖𝑠𝑡=𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑡ℎ𝑒 𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑒𝑑 𝐶ℎ𝑎𝑟𝑔𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 𝑎𝑛𝑑
𝑡ℎ𝑒 𝐹𝑖𝑙𝑡𝑒𝑟𝑒𝑑 𝑔𝑟𝑖𝑑𝑠 𝑖𝑛𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑑 𝑤𝑖𝑡ℎ 𝑖𝑡 𝑖,
𝐷𝑖𝑠𝑡𝑡ℎ𝑒𝑠=𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑡ℎ𝑎𝑡 𝑐ℎ𝑎𝑟𝑔𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 𝑠ℎ𝑜𝑢𝑙𝑑 𝑖𝑑𝑒𝑎𝑙𝑙𝑦 𝑠𝑒𝑟𝑣𝑒, and
𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗=𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑.

5.
The method as claimed in claim 1, wherein computation of the traffic penalty is expressed as:
𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗=𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠−𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑 𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠,𝑖𝑓 |𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠−𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑|>𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑡𝑜𝑙 = 0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
where,
𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑= Σ𝑇𝐷𝑖 ∀ 𝑖 𝑚𝑎𝑝𝑝𝑒𝑑 𝑡𝑜 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑙𝑒 𝑔𝑟𝑖𝑑𝑖 𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑡𝑜𝑙=𝑇𝑜𝑙𝑒𝑟𝑒𝑛𝑐𝑒 𝑏𝑎𝑛𝑑 𝑓𝑜𝑟 𝑡𝑜𝑡𝑎𝑙 𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑡𝑜 𝑏𝑒 𝑠𝑒𝑟𝑣𝑒𝑑 𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗=𝑇𝑟𝑎𝑓𝑓𝑖𝑐 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑

6.
A system (100), comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
receive, via one or more hardware processors, a plurality of inputs comprising a city map of a city, a traffic count location, a daily traffic count for the traffic count location, a traffic threshold, and a location count threshold, a distance threshold and a traffic load threshold;
divide the city map into a first set of grids, via the one or more hardware processors, wherein the first set of grids are equal size grids covering the city;

identify one or more of the first set of grids as a plurality of candidate grids, via the one or more hardware processors, based on a grid identification technique;
estimate the traffic density for each of the candidate grids, via the one or more hardware processors, based on the daily traffic count for each of the traffic count location;
cluster the first set of grids and the plurality of candidate grids to generate a set of clustered grids, via the one or more hardware processors, using a clustering technique based on computing a cumulative sum;
compute a total score, via the one or more hardware processors, wherein the total score is a summation of a distance penalty and a traffic penalty, where:
the distance penalty is computed based on the distance threshold and a maximum distance, wherein the maximum distance is computed between the first set of grids and the plurality of candidate grids; and
the traffic penalty is computed based on the traffic density and the traffic load threshold in the first set of grids;
identify a final set of candidate locations from the set of clustered grids using the traffic density, the distance, the traffic load threshold and the distance threshold based on an iterative optimization technique, via the one or more hardware processors, wherein the iterative optimization technique comprises performing for all sub-clusters in the set of clustered grids:
identifying an candidate cluster from the set of clustered grids based on the traffic density, the distance, and the total score with the distance threshold and the traffic load threshold;

identifying atleast one candidate grid from the candidate cluster based on the total score and removing all the other grids except for the identified candidate grid from the set of clustered grids based on a selection-removal process; and
selecting an candidate location from the identified candidate grid, wherein the candidate location selected for all sub-clusters in the set of clustered grids to form the final set of candidate locations.

7.
The system (100) as claimed in claim 6, wherein the grid identification technique comprises;
identifying a plurality of high-density locations based on the traffic threshold;
identifying a plurality of candidate streets based on the plurality of high-density location and the location count threshold;
identifying a plurality of candidate locations based on the plurality of candidate streets and the traffic count location; and
identifying a plurality of candidate grids based on the plurality of candidate location.
8.
The system (100) as claimed in claim 6, wherein the clustering technique is performed for each candidate grid from the plurality of candidate grids, comprises:
computing a distance score between the candidate grid and the 25 first set of grids;
selecting a subset of first set of grids based on the distance threshold;
computing a cumulative sum based on a distance between the subset of first set of grids and plurality of candidate grids, wherein the 30 cumulative sum represents a cumulative sum of the traffic density; and

clustering the subset of first set of grids and the plurality of candidate grids to generate the set of clustered grids based on the cumulative sum of traffic density, the traffic load threshold, the distance threshold, wherein the set of clustered grids comprises atleast one candidate grids.
9.
The system (100) as claimed in claim 6, the distance penalty is computed as :
𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗=𝑀𝑎𝑥𝑑𝑖𝑠𝑡𝐷𝑖𝑠𝑡𝑇ℎ𝑟𝑒𝑠
where,
𝑀𝑎𝑥𝑑𝑖𝑠𝑡=𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑡ℎ𝑒 𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑒𝑑 𝐶ℎ𝑎𝑟𝑔𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 𝑎𝑛𝑑 𝑡ℎ𝑒 𝐹𝑖𝑙𝑡𝑒𝑟𝑒𝑑 𝑔𝑟𝑖𝑑𝑠 𝑖𝑛𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑑 𝑤𝑖𝑡ℎ 𝑖𝑡 𝑖 𝐷𝑖𝑠𝑡𝑡ℎ𝑒𝑠 =𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑡ℎ𝑎𝑡 𝑐ℎ𝑎𝑟𝑔𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 𝑠ℎ𝑜𝑢𝑙𝑑 𝑖𝑑𝑒𝑎𝑙𝑙𝑦 𝑠𝑒𝑟𝑣𝑒 𝐷𝑖𝑠𝑡𝑝𝑒𝑛𝑗=𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑
10.
The system (100) as claimed in claim 6, the traffic penalty is computed as:
𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗=𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠−𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑 𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠,𝑖𝑓 |𝑇𝑟𝑎𝑓𝑙𝑜𝑎𝑑𝑡ℎ𝑟𝑒𝑠−𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑|>𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑡𝑜𝑙 = 0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
where,
𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑙𝑜𝑎𝑑= Σ𝑇𝐷𝑖 ∀ 𝑖 𝑚𝑎𝑝𝑝𝑒𝑑 𝑡𝑜 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑙𝑒 𝑔𝑟𝑖𝑑𝑖 𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑡𝑜𝑙=𝑇𝑜𝑙𝑒𝑟𝑒𝑛𝑐𝑒 𝑏𝑎𝑛𝑑 𝑓𝑜𝑟 𝑡𝑜𝑡𝑎𝑙 𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑡𝑜 𝑏𝑒 𝑠𝑒𝑟𝑣𝑒𝑑

𝑇𝑟𝑎𝑓𝑓𝑖𝑐𝑝𝑒𝑛𝑗=𝑇𝑟𝑎𝑓𝑓𝑖𝑐 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 𝑓𝑜𝑟 𝑗𝑡ℎ 𝑒𝑙𝑖𝑔𝑖𝑏𝑙𝑒 𝑔𝑟𝑖𝑑