Optimal Charging Station Location in a Linear Cycle Path with Deviations

Bicycle tourism is on the rise thanks to assisted-pedaling bikes, also known as e-bikes. While pedaling is still required on these bikes, they allow for longer rides through a battery-powered motor that has an autonomy of a few tens of kilometers. Batteries can then be recharged in one to two hours at recharging stations. Due to the waiting time, these stations should be installed at points of interest such as town centers or monuments for the cyclist to explore during recharge. We consider the problem of installing charging stations (CSs) on a road or trail network in order to minimize the maximum distance between two CSs, subject to a budget constraint. Optimal placing of CSs for bike trail networks constitutes a known class of location problems; we focus on a special case where the graph representing the trail/road network is a caterpillar graph whose spine is a cycle path while the leaves are points of interest, connected to the trail via side roads. For this case, we show that the optimization problem can be solved to optimality by a binary search algorithm where a shortest path problem is solved at each iteration. We apply our approach to find the CS locations on a 210 km-long section of the VENTO bike trail in northern Italy.