TY - GEN A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Set Partitioning Approach to Shunting N2 - 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. T3 - ZIB-Report - 09-18 KW - integer programming KW - set partitioning KW - combinatorial packing KW - vehicle positioning Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11326 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering N2 - We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method. T3 - ZIB-Report - 13-79 KW - vehicle routing KW - crew rostering KW - integer programming KW - bicriteria optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-45107 SN - 1438-0064 ER -