Open Access

Carlos Cardonha

• This dissertation is dedicated to the Vehicle Positioning Problem (VPP), a classical combinatorial optimization problem in public transport in which vehicles should be assigned to parking positions in a depot in such a way that shunting moves are minimized. We investigate several models and solution methods to solve the VPP and the VPPp, a multi-periodic extension of the problem which was not previously studied. In the first part of the thesis, the basic version of the problem is introduced and several formulations, theoretical properties, and concepts are investigated. In particular, we propose a mixed integer quadratic constrained formulation of the VPP whose QP relaxation produces the first known nontrivial lower bound on the number of shunting moves. The second part of our work describes two advanced solution methods. In the first approach, a set partitioning formulation is solved by a branch-and-price framework. We present efficient algorithms for the pricing problem and in order to improve the performance of the framework, we introduce heuristics and discuss strategies to reduce symmetry. The second approach consists of an iterative technique in which we try to optimize an ILP by solving some of its projections, which are smaller and therefore easier to compute. Both techniques are able to produce satisfactory solutions for large-scale instances of the VPPp. In the third part, advanced aspects of the problem are investigated. We propose and analyze several solution methods for the VPP+ and for the VPPp+, which are extended and more challenging versions of the VPP and of the VPPp, respectively. Finally, the role of uncertainty in the problem is discussed. In particular, we introduce a new criteria to evaluate the robustness of assignment plans, a formulation based on this concept, and a new online algorithm for the VPP.