<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5493</id>
    <completedYear>2021</completedYear>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>workingpaper</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-04-20</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A 2D layered graph approach for scheduling delivery robots</title>
    <title language="deu">Ein geschichteter 2D Graphen Ansatz für die Ablaufplanung von Lieferrobotern</title>
    <abstract language="eng">In recent years parcel volumes reached record highs. The logistics industry is seeking new innovative concepts to keep pace. For densely populated areas delivery robots are a promising alternative to conventional trucking. These electric robots drive autonomously on sidewalks and deliver urgent goods, such as express parcels, medicine, or meals. The limited cargo space and battery capacity of these vehicles necessitates a depot visit after each customer served. The problem can be formulated as an electric vehicle routing problem with soft time windows and a single unit capacity. The goal is to serve all customers such that the quadratic sum of delays is minimized and each vehicle operates within its battery bounds. To solve this problem, we formulate an MIQP and present an expanded formulation based on a layered graph. For this layered graph we derive two solution approaches based on relaxations, which use less nodes and arcs. The first, Iterative Refinement, always solves the current relaxation to optimality and refines the graph if the solution is not feasible for the expanded formulation. This is repeated until a proven optimal solution is found. The second, Branch and Refine, integrates the graph refinement into a branch and bound framework avoiding restarts. Computational experiments performed on modified Solomon instances demonstrate the advantage of using our solution approaches and show that Branch and Refine outperforms Iterative Refinement in all studied parameter configurations.</abstract>
    <abstract language="deu">In den letzten Jahren erreichte das Paketvolumen Rekordhöhen. Die Logistikbranche sucht nach neuen innovativen Konzepten, um Schritt zu halten. Für dicht besiedelte Gebiete sind Lieferroboter eine vielversprechende Alternative zum konventionellen LKW-Transport. Diese elektrischen Roboter fahren autonom auf Bürgersteigen und liefern Waren wie Expresspakete, Medikamente oder Mahlzeiten aus. Der begrenzte Laderaum und die begrenzte Batteriekapazität dieser Fahrzeuge erfordern nach jedem Kunden einen Depotbesuch. Das Problem kann als Routingproblem für Elektrofahrzeuge mit weichen Zeitfenstern und einer Kapazität von einer einzelnen Einheit formuliert werden. Ziel ist es, alle Kunden so zu bedienen, dass die quadratische Summe der Verspätungen minimiert wird und jede Fahrzeugroute innerhalb der Batterieladungsgrenzen liegt. Um dieses Problem zu lösen, formulieren wir einen MIQP und präsentieren eine erweiterte Formulierung basierend auf einem geschichteten Graphen. Für diesen geschichtete Graphen leiten wir zwei  Lösungsansätze ab, die auf Relaxationen basieren und weniger Knoten und Bögen verwenden. Der erste, iterative Verfeinerung, löst die aktuelle Relaxation immer optimal und verfeinert den Graphen, wenn die erweiterte Formulierung keine zulässige Lösung enthält. Dies wird wiederholt, bis eine optimale Lösung gefunden ist. Die zweite Option, Verzweigen und Verfeinern, integriert die Graphenverfeinerung in einen Verzweige und Beschränke Rahmen, um Neustarts zu vermeiden. Computerexperimente, die an modifizierten Solomon-Instanzen durchgeführt wurden, zeigen den Vorteil der Verwendung unserer Lösungsansätze und zeigen, dass Verzweigen und Verfeinern die iterative Verfeinerung in allen untersuchten Parameterkonfigurationen übertrifft.</abstract>
    <identifier type="doi">10.26127/BTUOpen-5493</identifier>
    <identifier type="issn">2627-6100</identifier>
    <identifier type="urn">urn:nbn:de:kobv:co1-opus4-54931</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <author>Fabian Gnegel</author>
    <author>Stefan Schaudt</author>
    <author>Uwe Clausen</author>
    <author>Armin Fügenschuh</author>
    <series>
      <title>Cottbus Mathematical Preprints</title>
      <number>17, 2021</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Delivery robots</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Electric vehicle routing problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Graph refinement</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Layered graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Partial recharging</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Lieferroboter</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Streckenplanung für elektrische Fahrzeuge</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Graphenverfeinerung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Geschichtete Graphen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Partielles Aufladen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Mobiler Roboter</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Tourenplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Optimierung</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="collections" number="">Wiss. Publikationen</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
    <thesisPublisher>BTU  Cottbus - Senftenberg</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-btu/files/5493/COMP-17-2021_Gnegel_et_al.pdf</file>
    <file>https://opus4.kobv.de/opus4-btu/files/5493/TB-VRP-Instances.zip</file>
  </doc>
  <doc>
    <id>5199</id>
    <completedYear>2020</completedYear>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>workingpaper</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-06-11</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Branch-and-refine for solving time-dependent problems</title>
    <title language="deu">Branch-and-Refine zur Lösung zeitabhängiger Probleme</title>
    <abstract language="deu">Einer der Standardansätze zur Lösung zeitabhängiger diskreter Optimierungsprobleme, wie z.B. das Problem des Handlungsreisenden mit Zeitfenstern oder das Kürzeste Wege Problem mit Zeitfenstern, ist die Herleitung einer sogenannten zeitindizierten Formulierung. Wenn dem Problem eine Struktur  zu Grunde liegt, die durch einen Graphen beschrieben werden kann, basiert die zeitindizierte Formulierung normalerweise auf einem anderen, erweiterten Graphen, der in der Literatur als zeitexpandierter Graph bezeichnet wird. Der zeitexpandierte Graph kann oft so generiert werden, dass alle Zeitbeschränkungen  bereits aufgrund seiner Topologie erfüllt sind und somit Algorithmen für die entsprechende zeitunabhängige Variante angewendet werden können. Der Nachteil dieses Ansatzes ist, dass die Mengen der Ecken und Bögen des zeitexpandierten Graphen viel größer sind als die des ursprünglichen Graphen. In neueren Arbeiten hat sich jedoch gezeigt, dass für viele praktische Anwendungen eine partielle Expandierung des Graphen, die möglicherweise zeitunmögliche Pfade zulässt, oft ausreicht, um eine beweisbar optimale Lösung zu finden. Diese Ansätze verfeinern iterativ den ursprünglichen Graphen und lösen in jeder Iteration eine Relaxierung der zeitexpandierten Formulierung. Wenn die Lösung der aktuellen Relaxation alle Zeitbeschränkungen erfüllt, kann daraus eine optimale Lösung abgeleitet werden, und der Algorithmus terminiert.&#13;
In dieser Arbeit stellen wir neue Ideen vor, die das Übertragen von Informationen über die optimale Lösung eines gröberen Graphen zu einem verfeinerten Graphen ermöglichen und zeigen, wie diese in Algorithmen verwendet werden können. Genauer gesagt stellen wir einen neuen Algorithmus zur Lösung von MILP-Formulierungen (Mixed Integer Linear Program) von zeitabhängigen Problemen vor, der es ermöglicht, die Graphenverfeinerung während der Untersuchung des Branch-and-Bound Baums durchzuführen, anstatt jedes Mal neu zu starten, wenn die optimale Lösung sich als nicht zulässig herausgestellt hat. Um die praktische Relevanz dieses Algorithmus zu demonstrieren, präsentieren wir Ergebnisse von numerische Experimenten seiner Anwendung auf das Kürzeste Wege Problem mit Zeitfenstern und das Problem des Handlungsreisenden mit Zeitfenstern.</abstract>
    <abstract language="eng">One of the standard approaches for solving time-dependent discrete optimization problems, such as the travelling salesman problem with time-windows or the shortest path problem with time-windows is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is, that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion, that might contain time infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation is time feasible an optimal solution can be derived from it and the algorithm terminates. In this work we present new ideas, that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms, which are based on graph refinement. More precisely we present a new algorithm for solving Mixed Integer Linear Program (MILP) formulations of time-dependent problems that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree instead of restarting whenever the optimal solution was found to be infeasible. For demonstrating the practical relevance of this algorithm we present numerical results on its application to the shortest path problem with time-windows and the traveling salesman problem with time-windows.</abstract>
    <identifier type="doi">10.26127/BTUOpen-5199</identifier>
    <identifier type="issn">2627-6100</identifier>
    <identifier type="urn">urn:nbn:de:kobv:co1-opus4-51995</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <author>Fabian Gnegel</author>
    <author>Armin Fügenschuh</author>
    <series>
      <title>Cottbus Mathematical Preprints</title>
      <number>13, 2020</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Graphenverfeinerung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Branch-and-Bound</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kürzeste Wege Problem mit Zeitfenstern</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Problem des Handlungsreisenden mit Zeitfenstern</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Graph refinement</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Branch-and-bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Shortest path problem with time-windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Travelling salesman problem with time-windows</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Branch-and-Bound-Methode</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Kürzester-Weg-Problem</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Travelling-salesman-Problem</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="collections" number="">Wiss. Publikationen</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
    <thesisPublisher>BTU  Cottbus - Senftenberg</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-btu/files/5199/COMP-13-2020_Gnegel_Fuegenschuh.pdf</file>
    <file>https://opus4.kobv.de/opus4-btu/files/5199/COMP_13_Supplement.zip</file>
  </doc>
</export-example>
