Detailansicht
A general variable neighbourhood search algorithm for the multi-vehicle profitable pickup and delivery problem
Murat Kücüktepe
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard F. Hartl
DOI
10.25365/thesis.34387
URN
urn:nbn:at:at-ubw:1-30417.82166.914065-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Da der Vertriebsmarkt unter starkem Konkurrenzdruck arbeitet und sehr schnell expandiert, sind kleinere Logistikunternehmen, die ein beschränktes Transportvolumen haben, gezwungen, nur diejenigen Kunden auszuwählen, die höhere Einnahmen bringen. Um die Transportkosten zu vermeiden, wird die Zusammenarbeit der Transportunternehmen zu einer Verpflichtung. Das oben beschriebene Problem wird in der Literatur als Multi-Vehicle Profitable Pickup and Delivery Problem (MVPPDP) bezeichnet. Dieses ist durch ein Hauptdepot bzw. Hauptlager charakterisiert in welchem ich mehrere Fahrzeuge befinden. Diese Fahrzeuge holen die Waren bei ausgewählten „Abholkunden“ bzw. Abholpunkten ab und befördern diese innerhalb der eingeplanten Fahrzeit an die entsprechenden Auslieferungskunden. Um dieses Problem zu lösen, wurde die Methode General Variable Neighbourhood Search (GVNS) angewendet. Während das Shaking aus drei verschiedenen Ansätzen besteht, werden Ausgangslösungen mit einer Greedy- und Two-Stage Cheapest Insertion Heuristic berechnet. Beim dem lokalen Suchprozess wird eine sequenzielle und eine selbstanpassungsfähige Variable Neighbourhood Descent (VND) mit elf Nachbarschaften vorgeschlagen. Der Algorithmus wird auf neu erstellte Daten, die sich von 20 - 1000 Kunden erstrecken, geprüft bzw. angewendet. Die Daten wurden erzeugt, um die Leistung des Algorithmus bei verschiedenen Einnahmearten, wie zum Beispiel bei konstanten, nachfrageproportionalen und zufälligen Einnahmen zu testen und zu analysieren. Da die Eingangsdaten vielseitig sind, ist ein gut diversifizierender Algorithmus erforderlich. Deshalb wird nach mehreren Tests das stärkste Shaking gewählt. Das empirische Experiment zeigt zufriedenstellende Ergebnisse. Daraus kann geschlossen werden, dass der Algorithmus fähig ist, auf praxisbezogene Probleme angewendet zu werden.
Abstract
(Englisch)
As the distribution market expands rapidly in a severely competitive environment, small-scale logistic companies with insufficient volume of carriers are forced to choose the customers with higher revenues to serve. Hence, the collaboration of the carriers becomes an obligation in order to avoid the travel costs. The real-life problem described above can be formulated as a Multi-Vehicle Profitable Pickup and Delivery Problem (MVPPDP) that consists of a central depot hosting the multiple vehicles which transport the goods from chosen pickup customers to the corresponding delivery customers within the pre-determined travel time limit. To tackle with this problem, a sophisticated metaheuristic approach, the General Variable Neighbourhood Search (GVNS) is developed. Initial solutions are constructed with a greedy heuristic and a two-stage cheapest insertion heuristic while the shaking step is formed by three different components. For the local search part, a sequential and a self-adaptive Variable Neighbourhood Descent (VND) with eleven neighbourhoods are proposed. The algorithm is tested on newly created data instances including 20-1000 customers. The data is generated to analyse the performance of the algorithm with different types of revenues such as fixed, demand-proportional and random. Since the input data is versatile enough to handle, a well-diversifying algorithm is needed. For this reason, the strongest shaking procedure is opted after several trials. The computational experiments show promising results. This implies that the algorithm is competent for being applied for the real-life problems.
Schlagwörter
Schlagwörter
(Englisch)
General Variable Neighbourhood Search Profitable Pickup and Delivery Problem Self-Adaptive Variable Neighbourhood Descent Vehicle Routing Problem Two-Stage Cheapest Insertion Heuristic
Schlagwörter
(Deutsch)
General Variable Neighbourhood Search Profitable Pickup and Delivery Problem Self-Adaptive Variable Neighbourhood Descent Vehicle Routing Problem Two-Stage Cheapest Insertion Heuristic
Autor*innen
Murat Kücüktepe
Haupttitel (Englisch)
A general variable neighbourhood search algorithm for the multi-vehicle profitable pickup and delivery problem
Paralleltitel (Deutsch)
Das General Variable Neighbourhood Search Verfahren für das Mutli-Vehicle Profitable Pickup and Delivery Problem
Publikationsjahr
2014
Umfangsangabe
VII, 70, S. VIII - XV : Ill, graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard F. Hartl
AC Nummer
AC12144366
Utheses ID
30523
Studienkennzahl
UA | 066 | 920 | |