{"id":5976,"date":"2017-11-17T21:49:16","date_gmt":"2017-11-17T19:49:16","guid":{"rendered":"https:\/\/www.ftf.or.at\/?p=5976"},"modified":"2017-11-17T21:49:16","modified_gmt":"2017-11-17T19:49:16","slug":"local-search-heuristics-for-the-capacitated-vehicle-routing-problem-with-structured-time-windows","status":"publish","type":"post","link":"https:\/\/www.ftf.or.at\/?p=5976","title":{"rendered":"Local Search Heuristics for the Capacitated Vehicle Routing Problem with Structured Time Windows"},"content":{"rendered":"

\"truden\"<\/a>\u2026 ist der Titel des\u00a02.\u00a0Platzes des Roland-Mittermeir-Preises 2015\/2016<\/strong>\u00a0und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit\u00a0EUR 1.000,\u2013<\/strong>ausgezeichnet. Dem Autor und Preistr\u00e4ger, Herrn\u00a0Dipl.-Ing. Christian Truden<\/strong>, wurde der Preis im Rahmen des Festakts\u00a010-j\u00e4hriges Jubil\u00e4um der Fakult\u00e4t f\u00fcr Technische Wissenschaften<\/a>\u00a0<\/strong>\u00fcbergeben und die Arbeit wird hier kurz vorgestellt:<\/p>\n

\n
\n
\n

Das Vehicle Routing Problem ist ein kombinatorisches Optimierungsproblem, welches ein breites Spektrum an Anwendungen im Bereich der Transportlogistik hat. Diverse Varianten kommen unter anderem bei der Planung von effizienten Liefertouren zum Einsatz. Eines der aktuell bekanntesten Anwendungsgebiete, das in der vorgelegten Arbeit im Detail betrachtet wird, findet sich im Online-Lebensmittelhandel. Hierbei wa\u0308hlt der Kunde auf der Website des Supermarktes ein Zeitfenster fu\u0308r die Zulieferung seines Einkaufes. Im Anschluss muss ein Lieferplan erstellt werden, der alle bisherigen Kundenbestellungen in ihren zugewiesenen Zeitfenstern entha\u0308lt.<\/p>\n

Das diesem Prozess zu Grunde liegende Optimierungsproblem ist das sogenannte capacitated Vehicle Routing Problem with Time Windows (cVRPTW). Es beschreibt die Herausforderung Routen ausgehend von einem Depot kosten-minimal zu planen. Die Ladekapazita\u0308t der genutzten Lieferfahrzeuge und die maximale Fahrzeit der Fahrer darf hierbei nicht u\u0308berschritten werden. Des weiteren muss jeder Kunde genau einmal innerhalb des ihm zugewie- senen Zeitfensters besucht werden.<\/p>\n

Das cVRPTW geho\u0308rt zur Klasse der NP-schweren Optimierungsprobleme. Fu\u0308r gro\u0308\u00dfere Probleminstanzen, wie sie in der Praxis auftreten, sind daher exakten Methoden, die stets die optimale Lo\u0308sung liefern, nicht anwendbar. Da es die Online-Anwendung erfordert Lo\u0308sungen in Echtzeit zu generieren, wurden im Rahmen dieser Arbeit nicht- exakte Methoden, sogenannte Heuristiken, entwickelt, mit deren Hilfe sehr gute Lo\u0308sungen innerhalb ku\u0308rzester Zeit gefunden werden ko\u0308nnen.<\/p>\n

Die Basis unserer Methoden bilden lokale Suchheuristiken, welche die aktuelle Lo\u0308sung mittels einfacher Ver- tauschoperationen iterativ verbessern. Bei der von uns betrachteten Anwendung besitzen die Zeitfenster, die als strukturierte Zeitfenster bezeichnet werden, spezielle Eigenschaften: Es wird angenommen, dass sich die Zeitfenster nicht u\u0308berlappen und gro\u00df genug sind, damit mehrere Kunden innerhalb eines Zeitfensters besucht werden ko\u0308nnen. Diese Eigenschaften ko\u0308nnen ausgenutzt werden um den Suchraum der lokalen Operationen einzuschra\u0308nken und somit unsere Heuristiken entscheidend zu beschleunigen.<\/p>\n

Neben Lo\u0308sungsqualita\u0308t und Geschwindigkeit und der damit verbundenen ausgezeichneten Skalierbarkeit unserer Algorithmen, wurde von uns besonderer Wert auf die Flexibilita\u0308t der entwickelten theoretischen Grundlagen gelegt. Dadurch ko\u0308nnen unsere Methoden jederzeit mit geringem Aufwand an eine Vielzahl von zusa\u0308tzlichen spezifischen Bedingungen (sogenannte Business-Constraints), die es in der Praxis ha\u0308ufig und oftmals auch erst zu einem spa\u0308teren Projektzeitpunkt zu beru\u0308cksichtigen gilt, adaptiert werden.<\/p>\n

Die vorgelegte Masterarbeit diente bisher als Ausgangspunkt mehrerer Konferenzvortra\u0308ge und Publikationen. Bis dato sind zwei Konferenzpapiere entstanden, wobei eines davon bereits zur Vero\u0308ffentlichung akzeptiert wurde [3] und das andere sich aktuell im Reviewprozess befindet [2]. Au\u00dferdem befindet sich derzeit ein Journalartikel [1] in Begutachtung, wa\u0308hrend ein weiterer Journalartikel in Ku\u0308rze fertiggestellt wird.<\/p>\n

Neben diesen akademischen Resultaten wurde die Praxisrelevanz der erarbeiten Ergebnisse bereits mehrfach unter Beweis gestellt. Die in dieser Arbeit entwickelten Methoden bilden die Grundlagen der Optimierungskom- ponente eines Systems fu\u0308r Online-Lebensmittelbestellungen, welches gemeinsam mit der britischen Firma Satalia fu\u0308r eine der weltweit gro\u0308\u00dften Supermarktketten entwickelt wurde. Mit heutigem Tage befindet sich dieses System bereits in Betrieb und wird derzeit stufenweise in ganz Gro\u00dfbritannien eingefu\u0308hrt. Fu\u0308r weitere Details verweisen wir auf den folgenden, vor Kurzem vero\u0308ffentlichten Artikel: http:\/\/tinyurl.com\/cVRPsTW-article.<\/p>\n

Literatur<\/p>\n

[1] P. Hungerla\u0308nder, K. Maier, J. Po\u0308cher, A. Rendl, and C. Truden. Solving an on-line capacitated vehicle rou- ting problem with structured time windows. Technical Report TR-AAUK-M-O-16-12-30, Alpen-Adria Universita\u0308t Klagenfurt, Mathematics, Optimization Group, 2016. A preprint is available from http:\/\/www.optimization-online.org\/DB_HTML\/2017\/02\/5859.html.<\/p>\n

[2] \u00a0P. Hungerla\u0308nder, A. Rendl, and C. Truden. On the slot optimization problem in on-line vehicle routing. Technical Report TR-AAUK-M-O-17-04-13, Alpen-Adria Universita\u0308t Klagenfurt, Mathematics, Optimization Group, 2016. A preprint is available from http:\/\/www.optimization-online.org\/DB_HTML\/2017\/04\/ 5962.html.<\/p>\n

[3] \u00a0P. Hungerla\u0308nder, K. Maier, J. Po\u0308cher, A. Rendl, and C. Truden. Solving an on-line capacitated vehicle routing problem with structured time windows. In Operations Research Proceedings 2016, 2017. Accepted, a preprint is available from http:\/\/www.optimization-online.org\/DB_HTML\/2016\/12\/5764.html.<\/p>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

\u2026 ist der Titel des\u00a02.\u00a0Platzes des Roland-Mittermeir-Preises 2015\/2016\u00a0und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit\u00a0EUR 1.000,\u2013ausgezeichnet. Dem Autor und Preistr\u00e4ger, Herrn\u00a0Dipl.-Ing. Christian Truden, wurde der Preis im Rahmen des Festakts\u00a010-j\u00e4hriges Jubil\u00e4um der Fakult\u00e4t f\u00fcr Technische Wissenschaften\u00a0\u00fcbergeben und die Arbeit wird hier … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"sfsi_plus_gutenberg_text_before_share":"","sfsi_plus_gutenberg_show_text_before_share":"","sfsi_plus_gutenberg_icon_type":"","sfsi_plus_gutenberg_icon_alignemt":"","sfsi_plus_gutenburg_max_per_row":"","footnotes":""},"categories":[9,12],"tags":[],"class_list":["post-5976","post","type-post","status-publish","format-standard","hentry","category-studienabganger","category-news"],"_links":{"self":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/5976","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5976"}],"version-history":[{"count":2,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/5976\/revisions"}],"predecessor-version":[{"id":5988,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/5976\/revisions\/5988"}],"wp:attachment":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5976"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5976"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5976"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}