Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-3704
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBode, Claudia
dc.date.accessioned2014-02-27T11:07:48Z
dc.date.available2014-02-27T12:07:48Z
dc.date.issued2014
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/3706-
dc.description.abstractDas Basisproblem von Arc-Routing Problemen mit mehreren Fahrzeugen ist das Capacitated Arc-Routing Problem (CARP). Praktische Anwendungen des CARP sind z.B. in den Bereichen Müllabfuhr und Briefzustellung zu finden. Das Ziel ist es, einen kostenminimalen Tourenplan zu berechnen, bei dem alle erforderlichen Kanten bedient werden und gleichzeitig die Fahrzeugkapazität eingehalten wird. In der vorliegenden Arbeit wird ein Cut-First Branch-and-Price Second Verfahren entwickelt. In der ersten Phase werden Schnittebenen generiert, die dem Master Problem in der zweiten Phase hinzugefügt werden. Das Subproblem ist ein kürzeste Wege Problem mit Ressourcen und wird gelöst um neue Spalten für das Master Problem zu liefern. Ganzzahlige CARP Lösungen werden durch ein neues hierarchisches Branching-Schema garantiert. Umfassende Rechenstudien zeigen die Effektivität dieses Algorithmus. Kombinierte Standort- und Arc-Routing Probleme ermöglichen eine realistischere Modellierung von Zustellvarianten bei der Briefzustellung. In dieser Arbeit werden jeweils zwei mathematische Modelle für Park and Loop und Park and Loop with Curbline vorgestellt. Die Modelle für das jeweilige Problem unterscheiden sich darin, wie zulässige Transfer Routen modelliert werden. Während der erste Modelltyp Subtour-Eliminationsbedingungen verwendet, werden bei dem zweiten Modelltyp Flussvariablen und Flusserhaltungsbedingungen eingesetzt. Die Rechenstudie zeigt, dass ein MIP-Solver den zweiten Modelltyp oft in kürzerer Rechenzeit lösen kann oder bei Erreichen des Zeitlimits bessere Zielfunktionswerte liefert.de_DE
dc.description.abstractThe basic multiple-vehicle arc-routing problem is called Capacitated Arc-Routing Problem (CARP). Applications of the CARP are in waste collection and mail delivery, for example. The goal is to find a cost-minimal set of tours that service all required edges and meet the capacity restriction. In this work, a cut-first branch-and-price second approach is developed. In phase one, cutting planes are generated that are introduced to the master problem in the second phase. The subproblem is a shortest path problem with resource constraints. It is solved in order to generate new columns for the master problem. Integer CARP solutions are guaranteed by a new hierarchical branching scheme. Comprehensive computational results show the effectiveness of the algorithm. Combining location problems with arc-routing problems enables one to model more realistic mail delivery applications. In this work, two mathematical formulations for each park and loop, and park and loop with curbline are introduced. The two models for each problem differ in how they model feasible transfer routes. While the first type of model uses subtour-elimination constraints, the second type uses flow variables and flow conservation constraints. The computational study shows that a MIP-Solver often needs less computation time to solve the latter type of model or results in better lower bounds when reaching the time limit.en_GB
dc.language.isoeng
dc.rightsInCopyrightde_DE
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc510 Mathematikde_DE
dc.subject.ddc510 Mathematicsen_GB
dc.titleOn arc-routing problemsen_GB
dc.typeDissertationde_DE
dc.identifier.urnurn:nbn:de:hebis:77-36748
dc.identifier.doihttp://doi.org/10.25358/openscience-3704-
jgu.type.dinitypedoctoralThesis
jgu.type.versionOriginal worken_GB
jgu.type.resourceText
jgu.description.extent155 S.
jgu.organisation.departmentFB 03 Rechts- und Wirtschaftswissenschaften-
jgu.organisation.year2013
jgu.organisation.number2300-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.organisation.placeMainz-
jgu.subject.ddccode510
opus.date.accessioned2014-02-27T11:07:48Z
opus.date.modified2014-11-25T09:17:31Z
opus.date.available2014-02-27T12:07:48
opus.subject.dfgcode00-000
opus.subject.otherarc routing , exact method , modellingde_DE
opus.subject.otherArc Routing , exaktes Verfahren , Modellierungen_GB
opus.organisation.stringFB 03: Rechts- und Wirtschaftswissenschaften: Abteilung Wirtschaftswissenschaftende_DE
opus.identifier.opusid3674
opus.institute.number0302
opus.metadataonlyfalse
opus.type.contenttypeDissertationde_DE
opus.type.contenttypeDissertationen_GB
jgu.organisation.rorhttps://ror.org/023b0x485
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
3674.pdf1.42 MBAdobe PDFView/Open