Heuristics for the vehicle routing problem with multiple deliverymen

Masterarbeit aus dem Jahr 2011 im Fachbereich BWL - Beschaffung, Produktion, Logistik, Note: Sehr gut, Karl-Franzens-Universität Graz (Produktion und Logistik), Sprache: Deutsch, Abstract: Der Hauptbestandteil dieser Arbeit ist das Testen verschiedener lokaler Suchoperatoren

für eine Erweiterung des gutbekannten Vehicle Routing Problems.

Diese erst vor kurzem eingeführte Erweiterung wurde notwendig um ein

Routenplanungsproblem zu lösen, das daraus bestand, Getränke und Tabakwaren

in dichtbesiedelten Groÿstädten in Brasilien auszuliefern. Es wurde

nun versucht herauszunden, welche der VRPTW Operatoren geeignet sind,

um das Vehicle Routing Problem with Time Windows and Multiple Deliverymen

(VRPTWMD) möglichst gut zu lösen. Insgesamt wurden vier Operatoren

implementiert, wobei Relocate und Ejection Chains auf die Routenminimierung

abzielen und Cross bzw. 2-opt entsprechend die gefahrene Distanz

verringern sollten. Um die Operatoren zu testen, wurden die benötigten

Startlösungen mit der von Solomon entwickelten I1 Einfügeheuristik generiert.

Die Erkenntnisse aus den Tests wurden schieÿlich dazu verwendet, eine

best performance Variante zu entwickeln, welche anhand der Solomon Instanzen

R101 bis R112 getestet wurde. Die Ergebnisse der Tests benden

sich am Ende der Arbeit.

The Vehicle Routing Problem with time windows is a well studied problem

in literature. The extension to Vehicle Routing Problem with Time Windows

and Multiple Deliverymen (VRPTWMD) has been proposed to solve a

delivery problem of commodities, like beverages and tobacco in highly populated

areas in Brazil. This rather new problem structure in the VRPTW

context, is the main subject of the work. In this thesis, the aim is to nd

out, which operators used for VRP are most suitable for the VRPTWMS.

Relocate and Ejection Chain operators were tested for truck and deliverymen

reduction, Cross and 2-opt were implemented to reduce distance. The

Solomon I1 insertion heuristic was used to obtain starting solutions, for the

tests and the nal version of the algorithm proposed. To complete this work,

several tests have been performed and the results of the algorithm running

Solomon R101- R112 instances can be found at the end.