VNS as an upper bound for an exact method to solve a class of on-demand transit transportation systems

This paper considers the offline routing of a Personal Rapid Transit system. In particular, a branch and bound approach is combined with a variable neighborhood search, and this is adapted to the context of the problem as we introduce some linear programming techniques and different neighborhood operators to enhance its performance. Computational results show a good average gap between the lower and our method and this can be found in a relatively good computational time.