<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>894</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-12-22</completedDate>
    <publishedDate>2005-12-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Target Date Assignment Problem</title>
    <abstract language="eng">Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.</abstract>
    <identifier type="serial">05-61</identifier>
    <identifier type="opus3-id">894</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8945</identifier>
    <enrichment key="SourceTitle">Appeared in : T. Erlebach; G. Persiano (eds.), Approximation and Online Algorithms (WAOA 2005), LNCS 3879 (2006) 230-243</enrichment>
    <author>Stefan Heinz</author>
    <author>Sven Krumke</author>
    <author>Nicole Megow</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <author>Tjark Vredeveld</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-61</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Target Date Assignment Problem</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68W40">Analysis of algorithms [See also 68Q25]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/894/ZR-05-61.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/894/ZR-05-61.ps</file>
  </doc>
  <doc>
    <id>913</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-04-18</completedDate>
    <publishedDate>2006-04-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">LP-Based Local Approximation for Markov Decision Problems</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">06-20</identifier>
    <identifier type="opus3-id">914</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9131</identifier>
    <author>Stefan Heinz</author>
    <author>Volker Kaibel</author>
    <author>Matthias Peinhardt</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>06-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Markov decision problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>linear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="F.2.2">Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)</collection>
    <collection role="ccs" number="G.2.1">Combinatorics (F.2.2)</collection>
    <collection role="msc" number="68W25">Approximation algorithms</collection>
    <collection role="msc" number="90C40">Markov and semi-Markov decision processes</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/913/ZR-06-20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/913/ZR-06-20.ps</file>
  </doc>
  <doc>
    <id>386</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-01-27</completedDate>
    <publishedDate>1999-01-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Generalized Baues Problem for Cyclic Polytopes II</title>
    <abstract language="eng">Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d &lt; d' &lt; n$.</abstract>
    <identifier type="serial">SC-98-43</identifier>
    <identifier type="opus3-id">387</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3862</identifier>
    <enrichment key="SourceTitle">Appeared in: Publications de l'Institut Mathematique, Belgrade 66 (1999) 3-15</enrichment>
    <author>Christos A. Athanasiadis</author>
    <author>Jörg Rambau</author>
    <author>Francisco Santos</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Generalized Baues Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Induced Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Poset</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Spherical</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cyclic Polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bistellar Operations</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52B99">None of the above, but in this section</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/386/SC-98-43.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/386/SC-98-43.pdf</file>
  </doc>
  <doc>
    <id>387</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-01-28</completedDate>
    <publishedDate>1999-01-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings</title>
    <abstract language="eng">In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos.</abstract>
    <identifier type="serial">SC-98-44</identifier>
    <identifier type="opus3-id">388</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3874</identifier>
    <enrichment key="SourceTitle">Appeared in: "The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings", Journal of the European Mathematical Society, 2 (2000) 179-198</enrichment>
    <author>Birkett Huber</author>
    <author>Jörg Rambau</author>
    <author>Francisco Santos</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-44</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>fiber polytope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lifting subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Minkowski sum</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cayley Trick</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bohne-Dress Theorem</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="14M25">Toric varieties, Newton polyhedra [See also 52B20]</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52B20">Lattice polytopes (including relations with commutative algebra and algebraic geometry) [See also 06A11, 13F20, 13Hxx]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/387/SC-98-44.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/387/SC-98-44.pdf</file>
  </doc>
  <doc>
    <id>367</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-09-22</completedDate>
    <publishedDate>1998-09-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Combinatorial Online Optimization</title>
    <abstract language="eng">In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.</abstract>
    <identifier type="serial">SC-98-24</identifier>
    <identifier type="opus3-id">368</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3674</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the International Conference of Operations Research Zürich (OR'98), Springer, 1999, pp. 21-37</enrichment>
    <author>Norbert Ascheuer</author>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-24</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitiveness</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-world problems</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/367/SC-98-24.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/367/SC-98-24.pdf</file>
  </doc>
  <doc>
    <id>357</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-05-06</completedDate>
    <publishedDate>1998-05-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Generalized Baues Problem for Cyclic Polytopes I.</title>
    <abstract language="eng">The Generalized Baues Problem asks whether for a given point configuration the order complex of all its proper polyhedral subdivisions, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cyclic polytopes in all dimensions. This yields the first non-trivial class of point configurations with neither a bound on the dimension, the codimension, nor the number of vertice for which this is known to be true. Moreover, it is shown that all triangulations of cyclic polytopes are lifting triangulations. This contrasts the fact that in general there are many non-regular triangulations of cyclic polytopes. Beyond this, we find triangulations of $C(11,5)$ with flip deficiency. This proves---among other things---that there are triangulations of cyclic polytopes that are non-regular for every choice of points on the moment curve.</abstract>
    <identifier type="serial">SC-98-14</identifier>
    <identifier type="opus3-id">358</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3579</identifier>
    <enrichment key="SourceTitle">Appeared in: European Journal of Combinatorics, 21(1), 2000, 65-83</enrichment>
    <author>Jörg Rambau</author>
    <author>Francisco Santos</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-14</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Generalized Baues Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Induced Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Poset</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Spherical</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cyclic Polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bistellar Operations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Flip Defici</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52B99">None of the above, but in this section</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/357/SC-98-14.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/357/SC-98-14.pdf</file>
  </doc>
  <doc>
    <id>377</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-12-08</completedDate>
    <publishedDate>1998-12-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Transportation Problem: Competitive Scheduling of Elevators</title>
    <abstract language="eng">In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service.</abstract>
    <identifier type="serial">SC-98-34</identifier>
    <identifier type="opus3-id">378</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3779</identifier>
    <enrichment key="SourceTitle">Appeared as: Online Dial-a-Ride Problems: in: Minimizing the Completion Time. Proceeding of the 17th International Symposium on Theoretical Aspects of Computer Science, Vol 1770 of Lecture Notes in Computer Science, Springer 2000, 639-650</enrichment>
    <author>Norbert Ascheuer</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-34</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitive analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="F.1.2">Modes of Computation</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/377/SC-98-34.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/377/SC-98-34.pdf</file>
  </doc>
  <doc>
    <id>711</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-11-25</completedDate>
    <publishedDate>2002-11-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online-Dispatching of Automobile Service Units</title>
    <abstract language="eng">We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association.</abstract>
    <identifier type="serial">02-44</identifier>
    <identifier type="opus3-id">712</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7117</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2002. Selected Papers of the International Conference on Operations Research (SOR 2002), Klagenfurt, September 2-5, 2002. U. Leopold-Wildburger et al. (eds.) Berlin: Springer 2003. Pp. 168-173</enrichment>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Luis Miguel Torres</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-44</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>soft time windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ADAC</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/711/ZR-02-44.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/711/ZR-02-44.pdf</file>
  </doc>
  <doc>
    <id>702</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-10-18</completedDate>
    <publishedDate>2002-10-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Dynamic Routing Algorithms in Transparent Optical Networks An Experimental Study Based on Real Data</title>
    <abstract language="eng">Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure.</abstract>
    <identifier type="serial">02-35</identifier>
    <identifier type="opus3-id">703</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7025</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 7th IFIP Working Conference on Optical Network Design and Modelling (ONDM 2003) (Cinklar, Tibor and Jacab, Tivadar and Tapolcai, Janos and Gaspar, Csaba, eds.) Kluwer Acadamic Press(2003) 293-312</enrichment>
    <author>Ralf Hülsermann</author>
    <author>Monika Jäger</author>
    <author>Sven Krumke</author>
    <author>Diana Poensgen</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-35</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Dynamic Network Configuration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Routing and Wavelength Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Transparent Optical Networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Blocking Probability</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Simulation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/702/ZR-02-35.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/702/ZR-02-35.pdf</file>
  </doc>
  <doc>
    <id>684</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-04-08</completedDate>
    <publishedDate>2002-04-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">TOPCOM: Triangulations of Point Configurations and Oriented Matroids</title>
    <abstract language="eng">TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed.</abstract>
    <identifier type="serial">02-17</identifier>
    <identifier type="opus3-id">685</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6849</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Software - ICMS 2002 (Cohen, Arjeh M. and Gao, Xiao-Shan and Takayama, Nobuki, eds.) World Scientific (2002) 330-340</enrichment>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>point configuration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>oriented matroid</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chirotope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>circuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cocircuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>symmetry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>TOPCOM</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="msc" number="52C35">Arrangements of points, flats, hyperplanes [See also 32S22]</collection>
    <collection role="msc" number="52C40">Oriented matroids</collection>
    <collection role="msc" number="52C45">Combinatorial complexity of geometric structures [See also 68U05]</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/684/ZR-02-17.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/684/ZR-02-17.pdf</file>
  </doc>
  <doc>
    <id>685</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-04-08</completedDate>
    <publishedDate>2002-04-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">02-18</identifier>
    <identifier type="opus3-id">686</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6858</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM News, Vol. 35, No. 4, (2002) pp. 10-11</enrichment>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Luis Miguel Torres</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>soft time windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pricing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch and bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real world data</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ADAC</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/685/ZR-02-18.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/685/ZR-02-18.pdf</file>
  </doc>
  <doc>
    <id>690</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-05-07</completedDate>
    <publishedDate>2002-05-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">How to Cut a Cake Almost Fairly</title>
    <abstract language="eng">In the cake cutting problem, $n\ge2$ players want to cut a cake into $n$ pieces so that every player gets a ``fair'' share of the cake by his own measure. We describe a protocol with $n-1$~cuts in which each player can enforce to get a share of at least~$1/(2n-2)$. Moreover we show that no protocol with $n-1$~cuts can guarantee a better fraction.</abstract>
    <identifier type="serial">02-23</identifier>
    <identifier type="opus3-id">691</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6905</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 263-264</enrichment>
    <author>Sven Krumke</author>
    <author>Maarten Lipmann</author>
    <author>Willem de Paepe</author>
    <author>Diana Poensgen</author>
    <author>Jörg Rambau</author>
    <author>Leen Stougie</author>
    <author>Gerhard Woeginger</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-23</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Fair division</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cake cutting</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="91A06">n-person games, n &gt; 2</collection>
    <collection role="msc" number="91A10">Noncooperative games</collection>
    <collection role="msc" number="91A80">Applications of game theory</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/690/ZR-02-23.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/690/ZR-02-23.pdf</file>
  </doc>
  <doc>
    <id>417</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-08-18</completedDate>
    <publishedDate>1999-08-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Wo bleibt der Aufzug?</title>
    <abstract language="deu">Dieser Artikel gibt eine allgemeinverständliche Einführung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung.</abstract>
    <identifier type="serial">SC-99-29</identifier>
    <identifier type="opus3-id">418</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-4175</identifier>
    <enrichment key="SourceTitle">Erschienen in: OR News Nr. 5, März 1999, ISSN 1437-2045, S. 11-13</enrichment>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-29</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Aufzugsteuerung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online-Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Echtzeit-Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>kompetitive Analyse</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/417/SC-99-29.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/417/SC-99-29.pdf</file>
  </doc>
  <doc>
    <id>394</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-03-03</completedDate>
    <publishedDate>1999-03-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Euler is Standing in Line</title>
    <abstract language="eng">In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.</abstract>
    <identifier type="serial">SC-99-06</identifier>
    <identifier type="opus3-id">395</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3947</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Appl. Math. 113 (2001) 87-107. A prel. vers. appeared in: Proc. of the 25nd Intern. Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science, vol. 1665, Springer (1999) 42-54</enrichment>
    <author>Dietrich Hauptmeier</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Hans-Christoph Wirth.</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-06</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NP-completeness</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polynomial-time approximation algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stacker-crane problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator system</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Eulerian Cycle</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q10">Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ONLINE-PLANNING">ONLINE-PLANNING</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/394/SC-99-06.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/394/SC-99-06.pdf</file>
  </doc>
  <doc>
    <id>396</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-03-12</completedDate>
    <publishedDate>1999-03-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Dial-a-Ride Problem under Reasonable Load</title>
    <abstract language="eng">In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.</abstract>
    <identifier type="serial">SC-99-08</identifier>
    <identifier type="opus3-id">397</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3961</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 4th Italian Conference on Algorithms amd Complexity, Vol. 1767 of Lecture Notes in Computer Science, Springer 2000, 125-136</enrichment>
    <author>Dietrich Hauptmeier</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-08</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitive analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="F.1.2">Modes of Computation</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="MATHEON-C3:Online-Modular">MATHEON-C3:Online-Modular</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/396/SC-99-08.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/396/SC-99-08.pdf</file>
  </doc>
  <doc>
    <id>397</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-03-12</completedDate>
    <publishedDate>1999-03-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Simulation Studies for the Online-Dial-a-Ride Problem</title>
    <abstract language="eng">In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.</abstract>
    <identifier type="serial">SC-99-09</identifier>
    <identifier type="opus3-id">398</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3976</identifier>
    <author>Martin Grötschel</author>
    <author>Dietrich Hauptmeier</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-09</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitive analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>simulation studies</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="F.1.2">Modes of Computation</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/397/SC-99-09.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/397/SC-99-09.pdf</file>
  </doc>
  <doc>
    <id>350</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-02-25</completedDate>
    <publishedDate>1998-02-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Combinatorial Online Optimization in Practice</title>
    <abstract language="eng">This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems.</abstract>
    <identifier type="serial">SC-98-07</identifier>
    <identifier type="opus3-id">351</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3508</identifier>
    <enrichment key="SourceTitle">Appeared in: OPTIMA - Mathematical Programming Society Newsletter, Nr. 57, March 1998, pp. 1-6</enrichment>
    <author>Norbert Ascheuer</author>
    <author>Martin Grötschel</author>
    <author>Nicola Kamin</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-world problems</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90B90">Case-oriented studies</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/350/SC-98-07.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/350/SC-98-07.pdf</file>
  </doc>
  <doc>
    <id>837</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-01-05</completedDate>
    <publishedDate>2005-01-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online-Optimization of Multi-Elevator Transport Systems with Reoptimization Algorithms based on Set-Partitioning Models</title>
    <abstract language="eng">We develop and experimentally compare policies for the control of a system of $k$ elevators with capacity one in a transport environment with $\ell$ floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each req uest and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average sq uared waiting times can be implemented to run in real-time ($1\,s$) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used polic ies like multi-server variants of greedy and nearest neighbor.</abstract>
    <identifier type="serial">05-03</identifier>
    <identifier type="opus3-id">837</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8373</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Applied Mathematics 154 (2006) 1908-1931</enrichment>
    <author>Philipp Friese</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-03</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator group control</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>policy</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>reoptimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>simulation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/837/ZR-05-03.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/837/ZR-05-03.pdf</file>
  </doc>
  <doc>
    <id>792</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2004-05-25</completedDate>
    <publishedDate>2004-05-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC</title>
    <abstract language="eng">Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.</abstract>
    <identifier type="serial">04-17</identifier>
    <identifier type="opus3-id">793</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7928</identifier>
    <enrichment key="SourceTitle">The rev. vers. appeared in: Electronic Notes in Discrete Mathematics Vol. 18, 1 December 2004, 157-163. The final vers. appeared in: Discrete Applied Mathematics 154 (2006) 1897-1907</enrichment>
    <author>Benjamin Hiller</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>04-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>soft time windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ADAC</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimality gap</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>high load</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/792/ZR_04_17.fin.vers.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/792/ZR_04_17.orig.Vers.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/792/ZR_04_17.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/792/ZR_04_17.orig.Vers.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/792/ZR_04_17.pdf</file>
  </doc>
  <doc>
    <id>621</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-12-19</completedDate>
    <publishedDate>2000-12-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem</title>
    <abstract language="eng">In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.</abstract>
    <identifier type="serial">00-53</identifier>
    <identifier type="opus3-id">622</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6217</identifier>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NP-completeness</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polynomial-time approximation algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stacker-crane problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q10">Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/621/ZR-00-53.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/621/ZR-00-53.pdf</file>
  </doc>
  <doc>
    <id>623</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-12-20</completedDate>
    <publishedDate>2000-12-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Online Optimierung</title>
    <abstract language="eng">Wie soll man einen Aufzug steuern, wenn man keine Informationen über zukünftige Fahraufträge besitzt? Soll man eine Bahncard kaufen, wenn die nächsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollständig gegeben sind. In vielen Fällen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungenügend. Zahlreiche Problemstellungen in der Praxis sind in natürlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zukünftiger Ereignisse getroffen werden müssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten Lösung mit dem Wert einer optimalen Offline-Lösung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schwächen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine Fülle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So müssen Entscheidungen unter strikten Zeitbeschränkungen gefällt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgewählte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universität Berlin entstanden.</abstract>
    <identifier type="serial">00-55</identifier>
    <identifier type="opus3-id">624</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6238</identifier>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-55</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kompetitive Analyse</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online Algorithmen</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/623/ZR-00-55.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/623/ZR-00-55.pdf</file>
  </doc>
  <doc>
    <id>642</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2001-07-24</completedDate>
    <publishedDate>2001-07-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Combinatorial Online Optimization in Real Time</title>
    <abstract language="eng">Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.</abstract>
    <identifier type="serial">01-16</identifier>
    <identifier type="opus3-id">643</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6424</identifier>
    <enrichment key="SourceTitle">Appeared in: Online Optimization of Large Scale Systems, Springer, 2001</enrichment>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Thomas Winter</author>
    <author>Uwe Zimmermann</author>
    <series>
      <title>ZIB-Report</title>
      <number>01-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Realtime Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Competitive Analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Survey</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="MATHEON-C3:Online-Modular">MATHEON-C3:Online-Modular</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/642/ZR-01-16.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/642/ZR-01-16.pdf</file>
  </doc>
  <doc>
    <id>643</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2001-07-24</completedDate>
    <publishedDate>2001-07-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online Optimization of Complex Transportation Systems</title>
    <abstract language="eng">This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.</abstract>
    <identifier type="serial">01-17</identifier>
    <identifier type="opus3-id">644</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6438</identifier>
    <enrichment key="SourceTitle">Appeared in: Online Optimization of Large Scale Systems, Springer (2001)</enrichment>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>01-17</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/643/ZR-01-17.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/643/ZR-01-17.pdf</file>
  </doc>
  <doc>
    <id>648</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2001-09-25</completedDate>
    <publishedDate>2001-09-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">01-22</identifier>
    <identifier type="opus3-id">649</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6484</identifier>
    <enrichment key="SourceTitle">Appeared in: Algorithms - ESA 2002. Proceedings of the 10th European Symposium on Algorithms, Rome, Italy, September 17-21, 2002. R. Möhring et al. (eds.) Berlin: Springer 2002. LNCS 2461, pp. 637-648</enrichment>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Luis Miguel Torres</author>
    <series>
      <title>ZIB-Report</title>
      <number>01-22</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>soft time windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pricing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch and bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real world data</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ADAC</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/648/ZR-01-22.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/648/ZR-01-22.pdf</file>
  </doc>
</export-example>
