This is a paper implementation of IEEE TRANSACTIONS ON SMART GRID, VOL. 5, NO. 6, NOVEMBER 2014 on Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions published by Albert Y.S. Lam, Member, IEEE, Yiu-Wing Leung, Senior Member, IEEE, and Xiaowen Chu, Senior Member, IEEE.
This is done using Cplex Optimizer in Python API as well as using Greedy Algorithm.
Problem Explanation: Here, n numbers of nodes(N) are given which denote the possible sites for constructing the charging stations. We need to find a subset of N such that:
- cost of construction should be minimum
- drivers can easily recharge their vehicle and move throughout the city So, we need to minimize the total cost i.e. minimize C=Σc i . x i, i=1,........n (1)
such that:
Σ(fj x j )≥ F i , ∀i,j∈ N i αD (2)
x i = {0, 1}, ∀i (3)
x 0 i + y i 0i = n, ∀i ∈ N̂ (4)
0 ≤ y ijk ≤ nx i x k , ∀(j, k) ∈ Ê ∪ (0 i , i), ∀i ∈ N̂ (5)
j|(j,k)∈ Ê Σy ijk = x i x k +Σy ikl , l|(k,l)∈ Ê, ∀i, k ∈ N̂ (6)
j∈ N̂ Σx j =y i 0i , ∀i∈ N̂ (7)
0 ≤ x 0 i , ∀i ∈ N̂ (8)
x i = 1. (9)
where, N-Set of potential charging station construction sites. E-Set of connections connecting pairs of the construction sites. n-Size of N . d(i, j)-Distance of the shortest path from nodes i to j. f i-Charging capacity of node i. F i-Demand requirement of node i. D-Average traversable distance of fully charged electric vehicles. α-A discount factor. x i-Boolean variable for construction at node i. c i-Construction cost at node i. N i αD -Set of nodes within distance αD from node i. N̂ -Set of nodes in induced graph. Ê-Set of edges in induced graph. 0 i-Source node of flow attached to node i. x 0 i-Residue of flow remained in 0 i . y ijk-Amount of flow on edge (j, k) originated from 0 i .