A set partitioning approach to shunting

The Vehicle Positioning Problem (VPP), also known as the shunting problem, is a classical combinatorial optimization problem in public transport planning. It has been investigated using several models and approaches, which work well for small instances, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation approach for the VPP and for a multi-period generalization. The main improvement of this model over previous ones is that it provides a tight linear description of the problem that can, in particular, produce non-trivial lower bounds. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial, respectively, pseudo-polynomial time for some versions of the problem. Computational results for large-scale instances are reported.

► We propose a Set Partitioning Model for the Vehicle Positioning Problem (VPP). ► The model produces non-trivial lower bounds for some scenarios of the problem. ► We solve the associated formulation using a column generation approach. ► The LP relaxation can be solved in polynomial time if first crossings are minimized. ► We present computational results for large-scale scenarios of the Multi-Periodic VPP.