Performance evaluation of heuristic and ILP-based algorithms for multi-period planning of SBVT-enabled transport networks


Optimization algorithms are a valuable tool for decision makers looking at different technological options and future traffic estimates. In order to quickly and accurately analyse multiple what-if scenarios, these algorithms need to balance solution quality and scalability. In this paper, we look at the specific case of multi-period planning in a transport network featuring SBVTs. We analyse the performance of an algorithm based on two ILPs running in sequence, and its suitability to a multi-period scenario, discussing the challenges of offloading complexity away from the ILPs onto pre or post-processing stages.

We also show experimental results on how the use of symmetry breaking constraints can significantly improve the algorithm’s running time in the most complex cases. Finally, the applicability of the ILP-based approach is measured against a simpler sequential heuristic algorithm, showing that specific problem instances can do with simpler methods, while others require a global optimization.