@techreport{GnegelFuegenschuh2020, type = {Working Paper}, author = {Gnegel, Fabian and F{\"u}genschuh, Armin}, title = {Branch-and-refine for solving time-dependent problems}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5199}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-51995}, year = {2020}, abstract = {Einer der Standardans{\"a}tze zur L{\"o}sung zeitabh{\"a}ngiger diskreter Optimierungsprobleme, wie z.B. das Problem des Handlungsreisenden mit Zeitfenstern oder das K{\"u}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{\"a}nkungen bereits aufgrund seiner Topologie erf{\"u}llt sind und somit Algorithmen f{\"u}r die entsprechende zeitunabh{\"a}ngige Variante angewendet werden k{\"o}nnen. Der Nachteil dieses Ansatzes ist, dass die Mengen der Ecken und B{\"o}gen des zeitexpandierten Graphen viel gr{\"o}ßer sind als die des urspr{\"u}nglichen Graphen. In neueren Arbeiten hat sich jedoch gezeigt, dass f{\"u}r viele praktische Anwendungen eine partielle Expandierung des Graphen, die m{\"o}glicherweise zeitunm{\"o}gliche Pfade zul{\"a}sst, oft ausreicht, um eine beweisbar optimale L{\"o}sung zu finden. Diese Ans{\"a}tze verfeinern iterativ den urspr{\"u}nglichen Graphen und l{\"o}sen in jeder Iteration eine Relaxierung der zeitexpandierten Formulierung. Wenn die L{\"o}sung der aktuellen Relaxation alle Zeitbeschr{\"a}nkungen erf{\"u}llt, kann daraus eine optimale L{\"o}sung abgeleitet werden, und der Algorithmus terminiert. In dieser Arbeit stellen wir neue Ideen vor, die das {\"U}bertragen von Informationen {\"u}ber die optimale L{\"o}sung eines gr{\"o}beren Graphen zu einem verfeinerten Graphen erm{\"o}glichen und zeigen, wie diese in Algorithmen verwendet werden k{\"o}nnen. Genauer gesagt stellen wir einen neuen Algorithmus zur L{\"o}sung von MILP-Formulierungen (Mixed Integer Linear Program) von zeitabh{\"a}ngigen Problemen vor, der es erm{\"o}glicht, die Graphenverfeinerung w{\"a}hrend der Untersuchung des Branch-and-Bound Baums durchzuf{\"u}hren, anstatt jedes Mal neu zu starten, wenn die optimale L{\"o}sung sich als nicht zul{\"a}ssig herausgestellt hat. Um die praktische Relevanz dieses Algorithmus zu demonstrieren, pr{\"a}sentieren wir Ergebnisse von numerische Experimenten seiner Anwendung auf das K{\"u}rzeste Wege Problem mit Zeitfenstern und das Problem des Handlungsreisenden mit Zeitfenstern.}, subject = {Graphenverfeinerung; Branch-and-Bound; K{\"u}rzeste Wege Problem mit Zeitfenstern; Problem des Handlungsreisenden mit Zeitfenstern; Graph refinement; Branch-and-bound; Shortest path problem with time-windows; Travelling salesman problem with time-windows; Branch-and-Bound-Methode; K{\"u}rzester-Weg-Problem; Travelling-salesman-Problem}, language = {en} }