Detailansicht

Trucks in movement
hybridization of exact approaches and variable neighborhood search for the delivery of ready-mixed concrete
Verena Schmid
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.165
URN
urn:nbn:at:at-ubw:1-30019.84859.719969-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
Beton erzeugende Unternehmen sehen sich täglich vor die Aufgabe gestellt, für die Belieferung der Baustellen eine möglichst effiziente Tourenplanung - unter Berücksichtigung ihrer heterogenen Fahrzeugflotte - zu erstellen. Da der Betonbedarf einer Baustelle die Kapazität eines einzelnen Fahrzeuges übersteigt, muss in der Regel jede Baustelle mehrmals hintereinander mit Beton beliefert werden. Das Planungsproblem ergibt sich nun insbesondere daraus, dass sich aufeinander folgenden Lieferungen nicht überschneiden dürfen, da nicht mehrere Fahrzeuge gleichzeitig entladen werden können. Eventuell entstehenden Lücken zwischen aufeinanderfolgenden Lieferungen jedoch sollten möglichst kurz gehalten werden. Im Rahmen dieser Dissertation werden mehrere Methoden besprochen, mit Hilfe derer eingangs erwähntes Tourenplanungsproblem gelöst werden kann. Die angewendeten Konzepte basieren auf exakten Verfahren, Heuristiken, Metaheuristiken, sowie hybriden Ansätzen. Ein exaktes Modell, beruhend auf einer Erweiterung des klassischen Vehicle Routing Problems (VRP, Tourenplanungsproblem) wurde entwickelt. Allerdings lässt sich die daraus resultierende Formulierung nur für äußerst kleine Instanzen exakt lösen. In der Praxis hingegen, ist dieser Ansatz aufgrund der zu langen Rechenzeiten und des enormen Rechenaufwandes nicht sinnvoll anwendbar. Daher wurde ein von Local Branching (LB) inspiriertes Verfahren konzipiert. Dieser integrativ hybride Ansatz wendet zusätzlich Nachbarschaftstrukturen, wie sie auch bei Variable Neighborhood Search (VNS) angewendet werden, kombiniert an. Darüber hinaus wurden valid inequalities für eine Verbesserung der unteren Schranken herangezogen. Ein weiterer Ansatz beruht auf einer Formulierung für multi-commodity network flow Problemen (MCNF). Anstatt einer globalen Sicht auf das Problem an sich, werden in diesem Zusammenhang nur ausgewählte Subbereiche näher betrachtet. So genannte Muster werden für alle Bestellungen
Abstract
(Englisch)
Companies in the concrete industry are facing the following scheduling problem on a daily basis: concrete produced at several plants has to be delivered at customers' construction sites using a heterogeneous fleet of vehicles in a timely, but cost-effective manner. As the ordered quantity of concrete typically exceeds the capacity of a single vehicle several deliveries need to be scheduled to fulfill an order. The deliveries cannot overlap and the time between consecutive deliveries has to be small. This thesis presents a broad range of different ways on how to solve the problem stated above. Various solution methods based on exact, heuristic, meta-heuristic and hybrid approaches have been developed. Exact methods based on a formulation the so called VRP° (a Split Delivery Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows) have been implemented. The resulting problem formulation can be solved to optimality for very small instances. For real-world-sized instances however, even with a steady increase in computational power, just to ``to MIP'' is not the way to success. Hence an algorithm, which controls the solution process of the embedded MIP-formulation, has been developed in order to tackler larger problem instances. This \emph{integrative hybrid} approach is based on Local Branching (LB) which itself is guided by means of Variable Neighborhood Search (VNS). Attention has also been paid to the development of valid inequalities and cuts in order to improve the quality of lower bounds. Another approach has been developed, which is based on a multi-commodity network flow model (MCNF) formulation. Rather than having a comprehensive view on the problem only subparts are considered and solved to optimality. So called \emph{patterns} (options on how orders could be satisfied) are generated heuristically and serve as an input for the MCNF. Given on a set of input pattern it is possible to solve the problem to optimality. Moreover the entire

Schlagwörter

Schlagwörter
(Englisch)
logistic routing hyridization multi-commodity network flow variable neighborhood search local branching ready-mixed concrete
Schlagwörter
(Deutsch)
Logistik Routenplanung Hybridisierung Netzwerkflussmodell variable Nachbarschaftssuche local branching Fertigbeton
Autor*innen
Verena Schmid
Haupttitel (Englisch)
Trucks in movement
Hauptuntertitel (Englisch)
hybridization of exact approaches and variable neighborhood search for the delivery of ready-mixed concrete
Paralleltitel (Deutsch)
Routenplanung für Betonfahrzeuge ; Hybridisierung exakter Verfahren mit variabler Nachbarschaftssuche für die Auslieferung von Fertigbeton
Publikationsjahr
2007
Umfangsangabe
144 S.
Sprache
Englisch
Beurteiler*innen
Karl Doerner ,
Walter Gutjahr
Klassifikation
85 Betriebswirtschaft > 85.32 Beschaffung, Materialwirtschaft
AC Nummer
AC05035909
Utheses ID
92
Studienkennzahl
UA | 084 | 157 | |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1