A Novel Location-Allocation-Routing Model for Siting Multiple Recharging Points on the Continuous Network Space

Due to environmental and geopolitical reasons, many countries are embracing electric vehicles (EVs) as an alternative to gasoline powered automobiles. Other alternative-fuel vehicles (AFVs) powered by compressed gas, hydrogen or biodiesel have also been tested for replacing gasoline powered vehicles. However, since the associated refueling infrastructure of AFVs is sparse and is gradually being built, the distance between recharging points (RPs) becomes a crucial prohibitive attribute in attracting drivers to use such vehicles. Optimally locating RPs will both increase demand and help in developing the refueling infrastructure.

The major emphasis in this dissertation is the development of theories and associated algorithms for a new set of location problems defined on continuous network space related to siting multiple RPs for range limited vehicles.

This dissertation covers three optimization problems: locating multiple RPs on a line network, locating multiple RPs on a comb tree network, and locating multiple RPs on a general tree network. For each of the three problems, finding the minimum number of RPs needed to refuel all Origin-Destination (O-D) flows is considered as the first objective. For this minimum number, the location objective is to locate this number of RPs to minimize weighted sum of the travelling distance for all O-D flows. Different exact algorithms are proposed to solve each of the three algorithms.

In the first part of this dissertation, the simplest case of locating RPs on a line network is addressed. Scenarios include single one-way O-D pair, multiple one-way O-D pairs, round trips, etc. A mixed integer program with linear constraints and quartic objective function is formulated. A finite dominating set (FDS) is identified, and based on the existence of FDS, the problem is formulated as a shortest path problem. In the second part, the problem is extended to comb tree networks. Finally, the problem is extended to general tree networks. The extension to a probabilistic version of the location problem is also addressed.