A hybrid heuristic approach to the problem of the location of vehicle charging stations

• We select O–D trips from a set of possible O–D trips under budget restrictions.
• We determine the location of recharging stations under budget restrictions.
• We provide refueling information for each combination of O–D trip and AFV type.
• We propose a hybrid heuristic approach to solve the problem efficiently.

In order to reduce the negative impact of fuel-powered vehicles on the environment, the use of alternative-fuel vehicles (AFVs), which produce far less pollution than traditional fuel-powered vehicles, is being introduced in many countries around the world. However, compared to the fuel-powered vehicles, AFVs such as electric vehicles require frequent recharging of their electrical energy storages (batteries), which results in a short vehicle driving range. Thus, AFV users who want to travel from home to a terminal location and back again must consider whether their AFVs can be recharged on the way. One of the approaches to solve this problem is to install alternative fuel charging stations on suitable locations to provide recharging services. However, when the budget is limited, the selection of locations and the types of alternative fuel charging stations becomes a decision problem, since it will directly affect the number of potential AFV users that can be served. This paper develops a mixed-integer programming model to address this problem and to maximize the number of people who can complete round-trip itineraries. A hybrid heuristic approach is proposed to solve this model. Numerical results show that the proposed heuristic approach only requires a small amount of CPU time to attain confident solutions.