考慮使用者路徑選擇行為之電動車公共充電設施設址最佳化模式與演算法

An Optimization Model for Locating Electric Vehicle Public Charging Facilities Considering Users’ Route Choice Behavior

決定電動車公共充電站位置時，通常需考慮電動車使用者的路徑選擇行為。本研究以雙層規劃模式求解公共充電設施設址問題，上層為決策者決定充電站位置，目標式為最小化系統總成本，下層為使用者均衡路徑流量指派問題；另模式中考慮里程焦慮程度異質性以區分不同類別使用者。本研究利用缺口函數將模式重新定式為單層規劃模式，提出以拉氏鬆弛法為基礎的演算法，並整合下降方向法及次梯度法提升求解效率。本研究分別以不同規模的範例評估演算法求解績效，小範例中以Gurobi 求解效率較佳，大範例中使用演算法方能在有限時間內求得品質較好的解。本研究之成果具理論貢獻及實務應用價值，可作為公共充電設施設址決策之參考。

Considering electric vehicle users’ route choice behavior is necessary for determining the locations of public charging stations from the government’s perspective. This study formulates the facility location problem of public charging stations as a bilevel programming model. The upper-level problem determines the locations of the public charging stations, and its objective is to minimize the total system cost. The lower-level problem is a user equilibrium traffic flow assignment problem with a path-based gap function as the objective function. Moreover, this study considers heterogeneous users with different degrees of range anxiety. To solve the problem efficiently, a single-level reformulation is proposed using the gap function as an equilibrium constraint and a Lagrangian-relaxation-based algorithm is developed. The algorithm integrates the descent direction method and subgradient method to improve solving efficiency. The numerical examples are conducted on different scales of networks. The results show that the small-scale instance can be efficiently solved by using Gurobi, while the proposed algorithm outperforms Gurobi on solving the large-scale instance. This study provides both methodological and practical contributions to the decision-making on the locations of public charging facilities.