pseudonerd / evse-location Goto Github PK

This project includes a Python implementation of our solution to the Electric Vehicle Charger Placement problem. The problem is to find an optimal placement of electric vehicle chargers in an area such that we minimize uneven power load distribution and costs such as driving distance and building costs. Our solution involves mapping this problem to the uncapacitated facility location problem as described in the Design of Approximate Algorithms text. This problem takes in a set of clients, a set of possible facility locations, associated building costs, and client costs for each facility and asks for an output that minimizes costs and creates an optimal opening of facilities and pairing of clients. Our mapping uses the facilities as possible charger locations and clients as electric vehicle users. Currently, we have implemented two algorithms (algorithm.py) for the facility location problem, a deterministic rounding algorithm (4-approximation) and a randomized rounding algorithm (3-approximation). These algorithms both involve a given linear programming formulation of the problem that we have solved and described in lp.py. We used the CVXOPT library to solve the LP. To test this implemented, we have provided a driver.py that takes in a file input and returns a dictionary representing the optimal charger placement.