Title (eng)
Trucks in movement
hybridization of exact approaches and variable neighborhood search for the delivery of ready-mixed concrete
Parallel title (deu)
Routenplanung für Betonfahrzeuge ; Hybridisierung exakter Verfahren mit variabler Nachbarschaftssuche für die Auslieferung von Fertigbeton
Author
Verena Schmid
Advisor
Richard Hartl
Assessor
Karl Doerner
Walter Gutjahr
Abstract (deu)
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 (eng)
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
Keywords (eng)
logisticroutinghyridizationmulti-commodity network flowvariable neighborhood searchlocal branchingready-mixed concrete
Keywords (deu)
LogistikRoutenplanungHybridisierungNetzwerkflussmodellvariable Nachbarschaftssuchelocal branchingFertigbeton
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1248547
rdau:P60550 (deu)
144 S.
Number of pages
144
Association (deu)
Title (eng)
Trucks in movement
hybridization of exact approaches and variable neighborhood search for the delivery of ready-mixed concrete
Parallel title (deu)
Routenplanung für Betonfahrzeuge ; Hybridisierung exakter Verfahren mit variabler Nachbarschaftssuche für die Auslieferung von Fertigbeton
Author
Verena Schmid
Abstract (deu)
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 (eng)
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
Keywords (eng)
logisticroutinghyridizationmulti-commodity network flowvariable neighborhood searchlocal branchingready-mixed concrete
Keywords (deu)
LogistikRoutenplanungHybridisierungNetzwerkflussmodellvariable Nachbarschaftssuchelocal branchingFertigbeton
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1248548
Number of pages
144
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0