Competitive EV charging station location with queues

summary

The gist

Electric vehicle (EV) public charging infrastructure planning faces significant challenges in competitive markets…

In short

The study models EV user behavior and competition using a multinomial logit model integrated into a bilevel program to find optimal charging station locations. By analyzing finite queueing systems, the research develops a linearization method to solve this complex problem. Results show that relocation strategies outperform existing networks under competition and congestion, providing managerial insights for infrastructure planning.

Key concepts

Multinomial Logit (MNL) Model
This model is used to predict how users choose between different charging stations based on their perceived utility. It goes beyond simply choosing the closest station by incorporating factors like expected waiting time and the probability of a user 'balking' (choosing not to use a station). This provides a more realistic view of user behavior.
Bilevel Program
This is an optimization technique where one level makes decisions while another level reacts to them. In this paper, the upper level decides where to place new stations to maximize accessibility (throughput), and the lower level models how users choose their stations based on those placements (user equilibrium).
Queueing Systems (M/M/s/K)
These are mathematical models used to analyze waiting lines at charging stations. The paper examines three types: M/M/1/K, M/M/s/K, and M./Er./s./K. These systems help quantify user behavior metrics like average waiting time and balking probability under different service conditions.
Linearization Method
Since the full bilevel problem is difficult to solve directly, the authors use piecewise-linear approximations to simplify the lower-level problem. This transforms it into a single-level mixed-integer linear program, making the complex optimization tractable and allowing for scalable solutions.

Terminology used across episodes

This episode discusses

The paper

Competitive EV charging station location with queues · Read on arXiv

Université de Montréal · Institut de Recherche d’Hydro-Québec

Electric vehicle (EV) public charging infrastructure planning faces significant challenges in competitive markets, where multiple service providers affect congestion and user behavior. This work extends existing modeling frameworks by incorporating the presence of competitors' stations and more realistic queueing systems. First, we analyze three finite queueing systems, M/M/1/K, M/M/s/K, and M/Er/s/K, with varying numbers of servers (charging outlets) and service time distributions, deriving analytic expressions for user behavior metrics. Second, we embed the queueing-based user behavior model into a bilevel program, where the upper level locates new charging stations to maximize accessibility (throughput), and the lower level captures users' station choices via a user equilibrium. Third, we apply a reformulation from competitive congested user-choice facility location models to approximately solve the bilevel problem and introduce a surrogate-based heuristic to enhance scalability. Fourth, we showcase our methodology on a real-world case study of an urban area in Montreal (Canada), offering managerial insights into how user-choice behavior assumptions and competition affect throughput and location decisions. The results demonstrate that our model yields (re)location strategies that outperform the existing network. More broadly, this approach provides a tool for incorporating charging service quality-through queueing metrics-and existing competition into station planning.

DOI: 10.1080/01605682.2026.2746464

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "Competitive EV charging station location with queues".

Dev: Here's the gist of the paper. Electric vehicle (EV) public charging infrastructure planning faces significant challenges in competitive markets, where multiple service providers affect congestion and user behavior The results demonstrate that our model yields (re)location strategies that outperform the existing network This work extends existing modeling frameworks by incorporating the presence of competitors’ stations and more realistic queueing systems Modeling User Behavior and Competition The paper models EV user selection using a user choice model based on the multinomial logit (MNL) model This model allows for a more realistic representation of user behavior compared to the commonly used simplified model in which users are assumed to choose the closest stations The disutility of a facility for a user is defined as Uij = vij − εij, where εij is a random variable that follows the Gumbel distribution The user assignment is modeled by equations (4.2) and (4.2), which incorporate expected waiting time and balking probability at facilities Queueing System Analysis The authors analyze three finite queueing systems, M/M/1/K, M/M/s/K, and M/Er/s/K, deriving analytic expressions for user behavior metrics They show that the M / Er / s / K model closely approximates the more general simulated M / Er / s / K model in their setting The performance metrics like balking probability and average waiting time are derived using queueing models of practical interest Optimization Methodology The core methodology involves embedding the queueing-based user behavior model into a bilevel program where the upper level locates new charging stations to maximize accessibility (throughput) The lower level captures users’ station choices via a user equilibrium To solve this nonlinear mixed-integer bilevel optimization problem, they apply piecewise-linear approximations to the lower level and then reformulate it as a single-level mixed-integer linear program by leveraging the optimality conditions of the approximated lower-level problem They also describe a surrogate-based heuristic to enhance scalability Case Study and Managerial Insights The methodology is showcased on a real-world case study of an urban area in Montreal (Canada), offering managerial insights into how user-choice behavior assumptions and competition affect throughput and location decisions The results demonstrate that our approach can improve public charging station accessibility with respect to the existing infrastructure, particularly under high congestion scenarios where increased buffer capacity amplifies its advantages The study investigates different scenarios of interest, including varying buffer sizes, user choice parameters, budget constraint for new stations and competition The study concludes that the solving of our linearization model leads to (re)locations that outperform the existing network under competition and congestion Simplifying assumptions can significantly distort both user behavior and optimal infrastructure decisions Future work should address limitations by obtaining real-world data on arrivals and waiting times, exploring the scalability of our linear approximation—especially when extending the model to include capacity decisions such as the number of outlets per station—and considering dynamic competition over time Detailed Results Summary The study compares the performance metrics across four types of queues, including M/M/1/1 + B, M/M/2/2 + B, M / Er / 2 / 2 + B, and M / M / 2 / 2 + B' The simulation results show that the performance metrics of the M / Er / s / K queues are small differences between them The linearization approach is shown to be sufficiently accurate for optimal parameter combinations with θ − 1 = 0, e.g., (0, 10, 0) and (10, 10, 0) The synergy between buffer capacity and relocation is observed when using the linearization model under competition The network analysis shows that the solution under the triplet (0, 10, 0) places new sites directly on 3 of these 7 additional competitor locations The heuristic model shows identical new site locations that are spread out across the region for both parameter triplets The results indicate that the linearization model consistently achieves higher TTR than the surrogate-based heuristic solution when relocation is enabled under competition The performance gap between models widens with increased buffer size, as larger buffers amplify the divergence in their objectives Robustness Testing A robustness test on the linearization model shows that nonzero performance gaps emerge across nearly all settings, indicating noticeable differences in TTR when each solution is applied outside its original disutility setting The solution from the parameter combination (0, 0, 0) consistently achieves low optimality gaps The study emphasizes the importance of modeling the lower-level problem—namely, user equilibrium—as accurately as possible Nonzero performance gaps emerge across nearly all settings The discrepancies observed between queueing assumptions suggest that simplified models should be avoided The solution from the parameter combination (0, 0, 0) consistently achieves low optimality gaps Key Findings on Strategy The study demonstrates that relocating sites results in a clear improvement in TTR compared to the original network configuration with no relocation Increasing the number of relocated sites from X = 3 to X = 6 generally leads to further gains in TTR The synergistic interaction between buffer capacity and relocation is observed when using the location decisions of the linearization model under competition, where buffer size amplifies the effectiveness of relocation The linearization approach solution is driven by the objective of maximizing throughput The heuristic approach prioritizes user preferences The results show that increasing the buffer size to ten shifts the throughput distribution toward higher values—reflecting the ability to handle more users due to additional waiting space The study shows that in the absence of competition and with a relatively high demand factor of 0.3%, users have no choice but to use the available sites, regardless of relocation The solution from the parameter combination (0, 10, 0) outperforms the one of (10, 10, 0) by approximately 2 and 6 users/day under competition when buffer size is ten and relocation is allowed at X = 3 and X = 6 The solution from the parameter combination (10, 10, 0) generally leads to slightly better TTR than the ones associated with (0, 10, 0), with a typical difference of no more than 2 users/day in TTR Final Summary Our study presents an advanced facility location framework tailored to the operational realities of EV charging in congested and competitive urban environments We show that the user equilibrium problem can be formulated as a convex optimization problem under the assumption that the facilities are modeled as M/M/s/K queues Our results in a real-world scenario demonstrate that the solving of our linearization model leads to (re)locations that outperform the existing network under competition and congestion This work makes simplifying assumptions that enable analytical tractability but may limit generalizability The use of the multinomial logit model imposes a strong assumption on user choice behavior that may not fully capture real-world complexities Acknowledgments The authors sincerely appreciate the support provided by Ribal Atallah of the Hydro-Québec Research Institute for sharing his expertise on electric vehicle charging infrastructure and the associated network This research was supported by Mitacs and Hydro-Québec through the Mitacs Accelerate Program, and partially by the FRQ-IVADO Research Chair in Data Science for Combinatorial Game Theory The authors thank Steven Lamontagne and İsmail Sevim for their helpful discussions and insightful perspectives related to the project References Aboolian, R.

Rosa: and Karimi, M.

Dev: (2025).

Rosa: Benefit maximizing network design in the public sector Al-Dahabreh, N., Sayed, M.

Paper summary: Rosa: So this paper on "Competitive EV charging station location with queues," it looks at how planning for these places gets really tough in crowded markets where you have multiple providers messing with user choices and congestion. It claims they extend existing models by bringing in competitors and more realistic queueing systems to see how that affects things.

Dev: Right, so the core idea is looking at three finite queueing systems, M/M/one/K, M/M/s/K, and M/Er/s/K with different numbers of servers, which is the charging outlets <ref:2510.12961#pg1,three finite queueing systems, M/M/1/K, M/M/s/K>. They derive analytic expressions for user behavior metrics from those.

Taro: I'm curious about those specific queueing systems—what are they comparing? Are we talking about simple wait times or something more complex when you have limited spots?

Rosa: They look at how different service time distributions change things, and they find that the M/Er/s/K model is a good approximation for their simulated M/Er/s/K setting in this context.

Dev: And then they take that user behavior model and put it into a bilevel program. The upper level decides where to place new charging stations to maximize accessibility, which is the throughput, and the lower level models the users' choices through a user equilibrium.

Taro: A bilevel program sounds complex; how do you actually solve that when you have those queueing metrics plugged into the user choice model? What's the safety case there?

Rosa: They take a reformulation from competitive congested user-choice facility location models to approximately solve that bilevel problem, and they introduce a surrogate-based heuristic to make it more scalable.

Dev: That heuristic is important because it lets them handle the complexity of solving that nonlinear mixed-integer bilevel optimization problem by using piecewise-linear approximations for the lower level and then treating it as a single-level mixed-integer linear program.

Taro: So, when you run this on a real area, like Montreal, what does that mean for the actual physical deployment of chargers? Does it just tell you where to put them closest to people?

Rosa: The case study in Montreal shows they get relocation strategies that outperform the existing network configurations. It gives managers insights into how those user-choice assumptions and competition actually affect throughput and location decisions.

Dev: What's the big implication for planning if this model suggests relocating sites? Does it mean you should always move stations if you have competitors around?

Taro: The results show that the synergy between buffer capacity and relocation is observed when using the linearization model under competition, where larger buffers amplify the effectiveness of relocation. That seems like a key finding.

Rosa: Exactly, so increasing that buffer size to ten shifts the throughput distribution toward higher values, reflecting an ability to handle more users due to additional waiting space. The study shows that in the absence of competition and with a relatively high demand factor of zero point three percent, users have no choice but to use the available sites regardless of relocation.

Paper summary: Dev: That’s interesting because it suggests that without competition and low demand, just having more spots doesn't force a relocation decision on users anymore; their choice is simpler than we thought. But when competition is there, like in the Montreal case, the relocation strategy becomes quite different.

Taro: When they look at specific parameter combinations, they see that under the triplet (zero ten zero), the new sites are placed directly on three of seven additional competitor locations. That’s a very specific spatial outcome.

Rosa: And their heuristic model shows identical new site locations that are spread out across the region for both parameter triplets. But remember they found that the linearization model consistently achieves higher throughput than the surrogate-based heuristic solution when relocation is enabled under competition.

Dev: So, the model driven by maximizing throughput seems to be better at finding those better relocation options than just following user preferences, which is what the heuristic does.

Taro: The performance gap between these two models widens as you increase buffer size because larger buffers amplify the divergence in their objectives. That suggests that buffer capacity is a critical lever in deciding whether relocation is beneficial under competition.

Rosa: It really does point to how much service quality, modeled by those queueing metrics, matters when you're trying to plan infrastructure for EVs in congested areas like Montreal. So the main thing here is incorporating competition and realistic queues into the planning process itself.

Dev: And looking at the authors, they’re tackling a complex problem by embedding user choice models with queueing dynamics into a bilevel program and then using approximation techniques to make it solvable for practical use.

Taro: They did acknowledge that simplifying assumptions can distort both user behavior and optimal infrastructure decisions, which is a fair limitation to point out when you're dealing with real-world stuff.

Rosa: And they do state that the multinomial logit model imposes a strong assumption on user choice behavior that might not fully capture everything users actually do in those high-stress situations.

Dev: So for anyone planning EV infrastructure, this paper suggests using these queueing metrics to make the decisions about location and capacity, even if you have to use some approximations like piecewise-linear ones to get a solution.

Taro: It seems like the real world test outside the lab is important here—seeing how these models hold up when you introduce those failure modes where the world misbehaves or demand spikes unexpectedly.

Rosa: That’s what I'm interested in, so if we take this framework and see how robust it is when those real-world conditions aren't perfectly modeled, that’s the next step to consider.

Conclusion: Rosa: So, we're wrapping up on "Competitive EV charging station location with queues." This paper looks at how planning for EV chargers gets really complicated when there are other companies competing for customers and causing traffic jams.

Dev: Yeah, the authors take this problem and they build a model that puts real queueing systems right into it to see what happens to user behavior. It’s about taking those three different queueing types—M/M/one/K, M/M/s/K, and M/Er/s/K—and using them to figure out how users actually choose where to charge.

Taro: So the main thing is they embed this user choice model into a bilevel program. The top level tries to place stations for maximum access, and the bottom level models what users actually do based on waiting times and how crowded it gets.

Rosa: And then they solve that tough problem by using some approximations—piecewise-linear ones—to turn it into something they can actually run, plus a heuristic to make it scalable. The result is that their proposed relocation strategies actually perform better than the existing network setup in their case study in Montreal.

Dev: That's the big implication: we’re seeing how incorporating competition and realistic queueing metrics directly into station planning can lead to actual improvements in how many people can use the infrastructure.

Taro: It shows that just placing stations where they are closest isn't always the best move when you have other players around because of those waiting times.

Rosa: And the paper highlights that this approach gives us a tool we could use to plan better charging networks, not just for one city but generally for any congested area.

Dev: It does, and next we’re going to look at exactly how robust these findings are when the world doesn't behave exactly as their model predicts.

More episodes

← Home