A lower bound for minimizing the total energy consumption in a statically routed Personal Rapid Transit system

Personal Rapid Transit is a futuristic and innovative transportation system in which passengers travel using a set of automated driverless vehicles. This work presents lower bounds for the offline problem of routing PRT vehicles with limited battery capacity. In this paper, we demonstrate that this problem generalizes the NP-hard asymmetric distance constrained vehicle routing problem. More specifically, this paper introduces a partial integer lower bounding strategy. Tests using a structured PRT system demonstrate the quality of the method, as we find an average error relative to an upper bound of 0.709%.