TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Torres, Luis Miguel T1 - Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows N2 - Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers. T3 - ZIB-Report - 01-22 KW - vehicle dispatching KW - soft time windows KW - real-time KW - column generation KW - pricing KW - branch and bound KW - real world data KW - ADAC Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6484 ER - TY - GEN A1 - Heinz, Stefan A1 - Kaibel, Volker A1 - Peinhardt, Matthias A1 - Rambau, Jörg A1 - Tuchscherer, Andreas T1 - LP-Based Local Approximation for Markov Decision Problems N2 - The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an $\varepsilon$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies. T3 - ZIB-Report - 06-20 KW - Markov decision problem KW - linear programming KW - column generation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9131 ER - TY - GEN A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Torres, Luis Miguel T1 - Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time N2 - Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield. T3 - ZIB-Report - 02-18 KW - vehicle dispatching KW - soft time windows KW - real-time KW - column generation KW - pricing KW - branch and bound KW - real world data KW - ADAC Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6858 ER -