@misc{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Set Partitioning Approach to Shunting}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11326}, number = {09-18}, abstract = {The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.}, language = {en} } @misc{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Binary Quadratic Programming Approach to the Vehicle Positioning Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11242}, number = {09-12}, abstract = {The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view.}, language = {en} } @inproceedings{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Binary Quadratic Programming Approach to the Vehicle Positioning Problem}, series = {Modeling, Simulation and Optimization of Complex Processes -- Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009}, booktitle = {Modeling, Simulation and Optimization of Complex Processes -- Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009}, doi = {10.1007/978-3-642-25707-0}, pages = {41 -- 52}, abstract = {The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view.}, language = {en} } @phdthesis{Cardonha, author = {Cardonha, Carlos}, title = {Applied Methods for the Vehicle Positioning Problem}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-34211}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferCardonha2009, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A set partitioning approach to shunting}, series = {LAGOS 09 V Latin-American Algorithms, Graphs and Optimization Symposium}, booktitle = {LAGOS 09 V Latin-American Algorithms, Graphs and Optimization Symposium}, publisher = {Elsevier}, pages = {359 -- 364}, year = {2009}, language = {en} } @article{BorndoerferCardonha2009, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Set Partitioning Approach to Shunting}, series = {Electronic Notes in Discrete Mathematics}, journal = {Electronic Notes in Discrete Mathematics}, doi = {10.1016/j.endm.2009.11.059}, pages = {359 -- 364}, year = {2009}, language = {en} }