relized by Calvi Mirko Fondations of Operations Research, 2024, Politecnico of Milan
Consider a long linear cycle path as Vento, or the Danube cycle path. The cycle path usually runs along the banks of a river with scarce tourist interest. However, from the main course of the cycle path, it is possible to reach places of tourist interest by making small detours.
The rapid growth of e-bike ridership is proposing the problem of deploying a suitable charging infrastructure. The charging stations should be placed in strategic positions to guarantee coverage of the entire cycle path. However, since the charging operations require a non-negligible amount of time, the charging stations should be positioned in places where alternative activities could be carried out, such as restaurants, museums, swimming pools, or other amenities. Moreover, the presence of a charging station could also induce e-cyclists to discover new places and generate positive externalities.
Minimize the total lenght of the cycle path and, given a maximum budget to spend, minimize the maximum distance between charging stations. It is strongly suggested to continue the reading from the .ipynb file.
To compute the shortest path I used a modified TSP (The Salesman Problem) algorithm. In the code you can see a method to dedect and avoid loops in the graph. TSP algorithm reveals to be extremelly effective. When the graph is too dense TSP is not efficent, so I suggest to do some data cleaning, like only taking the 5 closest cities an don't compute the distance for each possible node.
other budgets are present in the .ipynb file As you can see there is a threshold at 16011.18979 [m] (0->43), so using a budget over 29892 euros wont improve the minimixed maximum distance between stations.