Source-linked AI summary
Optimizing the Deployment of Electric Vehicle Charging Stations Using Pervasive Mobility Data
Mohammad M. Vazifeh, Hongmou Zhang, Paolo Santi, Carlo Ratti
TL;DR
The paper asks how public EV charging stations can be located to cover urban demand while reducing drivers’ travel discomfort. It models demand from large-scale cellphone mobility data, formulates grid-based discrete optimization, and uses greedy and genetic algorithms for near-optimal solutions. In Boston, the genetic-algorithm layouts reduce both driver discomfort and the number of stations by about 10 percent versus a randomized solution, while remaining robust across later months.
Problem
The paper addresses how to locate public EV charging stations across an urban demand region while minimizing drivers’ discomfort.
Method
The framework uses cellphone mobility data to model charging demand, formulates a geographical-grid optimization problem, and applies greedy and genetic algorithms for near-optimal layouts.
Results
About 10 percent reductions in both drivers’ discomfort and the number of charging stations are reported for genetic-algorithm optimization versus a randomized solution.
Takeaways & Limitations
A near-optimal configuration computed from single-day movements preserves its properties in later months, supporting data-driven planning for urban charging infrastructure.
Abstract
from arXiv · showhide
With recent advances in battery technology and the resulting decrease in the charging times, public charging stations are becoming a viable option for Electric Vehicle (EV) drivers. Concurrently, wide-spread use of location-tracking devices in mobile phones and wearable devices makes it possible to track individual-level human movements to an unprecedented spatial and temporal grain. Motivated by these developments, we propose a novel methodology to perform data-driven optimization of EV charging stations location. We formulate the problem as a discrete optimization problem on a geographical grid, with the objective of covering the entire demand region while minimizing a measure of drivers' discomfort. Since optimally solving the problem is computationally infeasible, we present computationally efficient, near-optimal solutions based on greedy and genetic algorithms. We then apply the proposed methodology to optimize EV charging stations location in the city of Boston, starting from a massive cellular phone data sets covering 1 million users over 4 months. Results show that genetic algorithm based optimization provides the best solutions in terms of drivers' discomfort and the number of charging stations required, which are both reduced about 10 percent as compared to a randomized solution. We further investigate robustness of the proposed data-driven methodology, showing that, building upon well-known regularity of aggregate human mobility patterns, the near-optimal solution computed using single day movements preserves its properties also in later months. When collectively considered, the results presented in this paper clearly indicate the potential of data-driven approaches for optimally locating public charging facilities at the urban scale.
I. INTRODUCTION
The paper addresses how to deploy urban public charging stations to reduce driver discomfort, using individual mobility traces to overcome limitations of traditional traffic simulations and travel surveys. It introduces a data-driven optimization framework based on massive cellphone data and evaluates it against existing approaches.
- Motivation: Public charging-station deployment should minimize the discomfort drivers experience when traveling to reach a station.The paper identifies discomfort as a factor affected by vehicle range and charging time, and frames station placement as an urban optimization problem.
- Motivation: Traditional deployment studies rely on traffic simulations and travel surveys, whose scalability, accuracy, and cost can be limiting.The paper motivates using anonymized individual trajectories as an alternative source of mobility information.
- Contribution: The proposed framework models charging demand from over 1 million cellphone users recorded across 4 months and optimizes station layouts on a geographical grid.Its objective jointly considers covering demand and reducing aggregate travel distance to the closest station.
- Related work: Prior EV charging-station studies primarily used theoretical models, simulations, aggregate transportation data, or limited trajectory sources such as taxi data.The paper positions cellphone records as a way to characterize mobility demand more broadly than taxi trajectories.
- Contribution: The paper presents cell-phone-data-based optimization as an extension of existing charging-station planning work and a possible approach for urban facility-location problems.It identifies the framework as the first optimization framework for EV charging stations based on cellphone data.
III. INTRODUCING THE FRAMEWORK
The framework uses cellphone-derived mobility patterns to model EV charging demand and optimize station locations on a geographical grid. Because the resulting set-cover problem is NP-hard, it uses greedy and genetic algorithms to find near-optimal solutions.
- Framework overview: The framework analyzes individual movement patterns from cellphone data collected over four months to support data-driven charging-station placement.The broader Boston dataset includes home-location population estimates showing higher density in Metro Boston.
- Optimization formulation: The station-location problem is formulated as a set-cover problem that minimizes drivers’ aggregate distance from trip endpoints to the nearest charging station.The objective combines coverage of the demand region with reduced travel distance to available stations.
- Optimization formulation: Because set cover is NP-hard, the framework approximates near-optimal station locations using Chvatal’s greedy algorithm and a genetic algorithm.These methods are included among the framework’s optimization procedures for finding near-optimal locations.
- Demand modelling: Demand modelling uses individual trip trajectories, stay durations, and a linear energy-consumption assumption to estimate potential fast-refuelling demand.A fraction δ of qualifying trip segments represents candidate EVs potentially demanding fast refuelling; the minimum charging interval τmin is set to 30 minutes.
- Framework overview: The region is divided into non-overlapping square cells, while time is divided into intervals such as 30-minute slots.Cells and time slots provide the spatio-temporal structure for estimating charging demand.
V. STEP 2: FORMULATING THE OPTIMIZATION MODEL
The paper models charging-station placement as a weighted set-covering problem on a cell network. It balances coverage and driver discomfort while incorporating station-capacity constraints and a binary formulation suitable for genetic algorithms.
- Coverage model: Charging stations cover demand cells within hop-distance h on a cell network built from spatially adjacent geographic cells.Increasing h expands coverage but permits fewer stations, at the cost of greater driver discomfort.
- Discomfort objective: Driver discomfort is modeled as increasing linearly with the hop distance between demand cells and charging stations.The node weight aggregates demand at each hop distance up to h.
- Optimization problem: The optimization selects station-location subsets that cover every demand cell while minimizing the sum of their discomfort weights.This is formulated as a weighted set-covering problem and then as a constrained integer linear program.
- Capacity constraints: Finite station capacity changes the coverage requirement from at least one nearby station to at least k_i nearby stations.The paper otherwise assumes sufficiently large capacity, setting k_i = 1, while noting that capacitated extensions can optimize plug counts and load distribution.
- Computational representation: The set-covering instance is represented by a binary matrix whose rows are demand cells and columns are possible station locations.Zero-demand cells can be removed, and each candidate configuration is encoded as a binary vector.
A. Dataset
The dataset contains anonymized cellphone location traces from approximately one million users in the Boston metropolitan area over four months in 2009. The preprocessing reduces repeated in-cell records into shorter movement sequences with explicit location and time boundaries.
- Data source: The dataset comprises estimated anonymous location traces from approximately one million Boston-area users collected over four months in 2009.Records include cellphone connection events such as calls, text messages, and internet connections.
- Record reduction: Continuous records from the same cell are collapsed into a shorter representation retaining the user’s movement between distinct visited cells.Intermediate in-cell records are removed because they do not add a new location transition.
- Temporal representation: The reduced sequence is relabeled with continuous indices and location-specific start and end times.The resulting tuples preserve temporal boundaries for the user’s observed cell visits.
C. Home Detection
The methodology identifies each user’s home cell so home arrivals can be excluded from public-charging demand. Home is inferred from the cell where the user spends the most cumulative time overnight during a week.
- Home identification: Each user’s home cell is identified among the cells visited in the user’s mobility trace.The procedure is required because the model assumes users do not need public charging while at home.
- Detection rule: Home location H(u_j) is determined by the cell where the user cumulatively spends the most time between 8 p.m. and 6 a.m. during one week.Only overnight observations in that interval are considered for the home-location estimate.
D. Counting the Number of Trips Ending in a Cell
Trips ending in a cell are counted by tracking each user’s traveled distance from the last charging opportunity through cells without qualifying charging stops. A trip is counted only after a sufficiently long non-home stay and a minimum travel distance.
- Distance tracking: For each user, traveled distance is accumulated from the last charging cell through intermediate cells lacking a charging opportunity.The process uses a linear search over the reduced movement records and Manhattan distances between successive cells.
- Trip criterion: A trip is counted in IN_i,t when a user stays over 30 minutes at a non-home cell after traveling at least l_min = 100km.After counting the trip, the tracking distance resets to zero until another charging cell is found.
- Aggregation: The procedure is repeated for all users to determine IN_i,t for every cell and time period.These values provide the cell-level trip-ending demand used by the optimization model.
VII. STEP 4: OPTIMIZATION METHODS
Because exact set-covering optimization is computationally infeasible, the paper develops efficient near-optimal methods. Greedy search selects charging locations by coverage-weight trade-offs and removes redundant stations.
- The optimization problem is addressed with two computationally efficient methods because exact set-covering optimization is infeasible.
- Greedy search: Greedy search repeatedly selects the available cell with the lowest average weight per uncovered cell in its coverage range.
- Greedy search: After greedy coverage, redundant charging-station cells are removed to reduce the total number of stations.
B. Generating initial GA population
The genetic algorithm begins with locally optimized feasible layouts and evolves them through selection and crossover. Local search restores coverage and removes redundancy after crossover-generated layouts may become infeasible.
- Generating initial GA population: The GA initial population is built by distributing stations until all cells are covered, then removing redundant cells that contribute most to the objective.
- Generating initial GA population: A stochastic Chvatal variant can generate different layouts by randomly choosing among k elite locations at each step.
- Generating initial GA population: The GA replaces less-fit layouts with offspring using binary tournament selection and fusion crossover.
- Generating initial GA population: Because crossover can create uncovered or redundant cells, local search restores feasibility and ensures coverage with no redundancy.
VIII. RESULTS
The results show that optimized layouts reduce average distance while remaining robust across time and demand parameters. Adding station-building costs reduces station counts while retaining substantial distance improvements.
- Increasing coverage range h reduces the number of charging stations required, while producing location sets that are not nested subsets.
- For every tested coverage range h, GA’s final population has significantly lower average distance than the initial population.
- A single-day July configuration preserves its distance improvement across demand measured on selected days in July, September, and October 2009.
- The GA layout remains robust when τmin and lmin vary, retaining a significant distance gap over a randomly obtained layout.
- The solution structure is independent of EV penetration ratio δ because δ uniformly multiplies all problem weights.
- Adding a positive weight offset incorporates station-building or spatial costs; this significantly reduces station counts while preserving substantial average-distance improvement.
IX. CONCLUSION
The paper proposes a charging-station layout framework that minimizes EV drivers’ travel distance to stations and supports extensions for additional objectives. The resulting layout is near-optimal and robust to variations in inputs, EV penetration, and technology.
- The framework minimizes overall EV drivers’ discomfort, measured by the distance from refuelling demand spots to the closest charging station.
- The model can incorporate spatial construction costs and station capacities as optimization variables without changing the problem structure or required optimization method.
- The genetic algorithm uses binary tournament selection, fusion crossover, mutation, and feasibility repair within an evolving population.
- The computed layout is robust to variation in input data, EV penetration rate, and EV and charging-station technology.This robustness supports data-driven planning for EV charging-station location despite the high costs of infrastructure deployment.
APPENDIX A CAPACITATED CASE
The capacitated extension handles cells whose charging demand can exceed a station’s capacity by requiring multiple stations to cover those cells. It preserves the set-covering problem structure while adjusting coverage weights and discomfort contributions.
- When a cell frequently has q > l EVs over a significant period, one charging station is insufficient and the cell requires multiple stations.
- A cell requiring at least k_i stations is represented by duplicating its element in the universe set, increasing the number of required coverage subsets.
- The cell’s weight is changed from IN_i,t to IN_i,t/k_i, while its discomfort contribution decreases because demand is divided among the available stations.
- Despite these modifications, the capacitated formulation remains a set-covering problem.