On some generalized routing problems [Elektronische Ressource] / vorgelegt von Michael Drexl
178
pages
Deutsch
Documents
2007
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
178
pages
Deutsch
Ebook
2007
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié le
01 janvier 2007
Nombre de lectures
21
Langue
Deutsch
Publié le
01 janvier 2007
Nombre de lectures
21
Langue
Deutsch
OnSomeGeneralizedRoutingProblems
VonderFakultat¨ fur¨ Wirtschaftswissenschaften
derRheinisch Westf alischen¨ TechnischenHochschuleAachen
zurErlangungdesakademischenGradeseines
DoktorsderWirtschafts undSozialwissenschaften
genehmigteDissertation
vorgelegtvon
Dipl. Kfm. MichaelDrexl,M.O.R.
ausSchwabmunchen¨
Berichter:Univ. Prof. Dr.rer.nat.habil. Hans J ur¨ genSebastian
Univ. Prof. Dr.rer.pol.habil. MichaelBastian
Tagdermundlichen¨ Prufung:¨ 31. Oktober2007
DieseDissertationistaufdenInternetseiten
derHochschulbibliothekonlineverfugbar¨ .Contents
ListofSymbolsandAbbreviations iv
Zusammenfassung vii
Abstract ix
1 Introduction 1
1.1 SubjectMatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 MathematicalPrerequisites,Terminology,andNotation . . . . . . . . . . . . . . . . . . 3
2 Resource ConstrainedShortestPathsandLabellingAlgorithms 5
2.1 LabellingAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 AConcreteExample: theShortestPathProblemwithTimeWindows . . . . . . . . . . 7
2.3 NegativeCycles,ElementaryPaths,andComplexity . . . . . . . . . . . . . . . . . . . . 10
2.4 Ther c shortest pathsFramework . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4.1 FundamentalPrinciplesofGenericProgramming . . . . . . . . . . . . . . . . . 11
2.4.2 ImplementationDetails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 TheGeneralizedDirectedRuralPostmanProblem 14
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 IntegerProgrammingFormulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.1 AFormulationfortheDRPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.2 FormulationsfortheGDRPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.1 StandardArcRoutingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.2 TheGeneralizedTravellingSalesmanProblem . . . . . . . . . . . . . . . . . . 20
3.3.2.1 MakingtheClustersofaGTSPDisjoint . . . . . . . . . . . . . . . . 20
3.3.2.2 TransformingaGeneralizedATSPintoaGDRPP,andViceVersa . . . 21
3.3.3 TheGeneralizedDirectedGeneralRoutingProblem . . . . . . . . . . . . . . . 21
3.3.4 TheClusteredTravellingSalesmanProblem . . . . . . . . . . . . . . . . . . . . 22
3.3.5 TheDirectedRuralPostmanProblem . . . . . . . . . . . . . . . . . . 23
3.3.6 HierarchicalPostmanProblems . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.7 TheClusteredGeneralizedDirectedRuralPostmanProblem . . . . . . . . . . . 25
3.3.8 TheGeneralizedClusteredRural . . . . . . . . . . . 25
3.3.9 TurnPenalties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.10 ZigzagService . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.11 DifferentCostsforServicingandDeadheadinginDifferentDirections . . . . . . 30
3.3.12 ComplexityResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 SolutionApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.1 ALabellingAlgorithmfortheGDRPP . . . . . . . . . . . . . . . . . . . . . . 31
iContents ii
3.4.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.3 ABranch and CutAlgorithmfortheGDRPP . . . . . . . . . . . . . . . . . . . 36
3.4.3.1 ValidInequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3.2 BranchingandEnumerationStrategies . . . . . . . . . . . . . . . . . 36
3.4.3.3 UpperBounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 ComputationalExperiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.1 TestInstances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.2 SystemParameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.3 ComputationalResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.3.1 ResultsfortheExactLabellingAlgorithm . . . . . . . . . . . . . . . 38
3.5.3.2fortheHeuristics . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.3.3 ResultsfortheBranch and CutAlgorithm . . . . . . . . . . . . . . . 45
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 TheVehicleRoutingProblemwithTrailersandTransshipments 53
4.1 ProblemDescription . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.1 WhatisNew? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.2 TheCentralQuestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.3 PotentialSavingsThroughtheUseofTrailers . . . . . . . . . . . . . . . . . . . 57
4.2 LiteratureReview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 MixedIntegerProgrammingFormulations . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.1 RepresentationoftheData . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.2 AFormulationfortheCompleteProblemBasedonTurnVariables . . . . . . . . 67
4.3.2.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.2.3 ObjectiveFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.2.4 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3.2.5 ConnectionBetweenTurnVariablesandArcVariables. . . . . . . . . 78
4.3.2.6 CriticalAppraisalofthe‘Complete’Problem . . . . . . . . . . . . . . 79
4.3.3 AFormulationfora‘Core’ProblemBasedonArcVariables . . . . . . . . . . . 79
4.3.3.1 Simplifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.3.2 UnderlyingNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.3.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3.3.4 TheFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3.4 AFormulationfortheCoreProblemBasedonPathVariables . . . . . . . . . . 86
4.3.4.1 TheMasterProgram . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3.4.2 ThePricingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.4.3 IdenticalPricingProblems . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.5 ModifiedFormulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.4 ABranch and PriceAlgorithmfortheVRPTT? . . . . . . . . . . . . . . . . . . . . . . 99
4.5 ABranch and CutfortheCoreProblem . . . . . . . . . . . . . . . . . . . . 104
4.5.1 ValidInequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.5.2 BranchingandEnumerationStrategies . . . . . . . . . . . . . . . . . . . . . . . 108
4.6 ComputationalExperiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.6.1 TestInstances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.6.2 SystemParameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.6.3 ComputationalResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113Contents iii
5 TheTruck and TrailerRoutingProblem 115
5.1 NewMIPFormulationsfortheTTRP . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.2 UnderlyingNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.1.3 AFormulationBasedonArcVariables . . . . . . . . . . . . . . . . . . . . . . 119
5.1.4 AFBasedonPathV . . . . . . . . . . . . . . . . . . . . . . 123
5.1.4.1 TheMasterProgram . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.1.4.2 ThePricingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.1.4.3 IdenticalPricingProblems . . . . . . . . . . . . . . . . . . . . . . . 126
5.2 ABranch and CutAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.1 ValidInequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.2 BranchingandEnumerationStrategies . . . . . . . . . . . . . . . . . . . . . . . 128
5.3 ABranch and PriceAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.1 ThePricingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.1.1 LiteratureReview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.1.2 StrategiesfortheSolutionofthePricingProblems . . . . . . . . . . . 131
5.3.1.3 ResourcesandResourceExtensionFunctions . . . . . . . . . . . . . 132
5.3.1.4 TechnicalIssues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.3.2 AddingValidInequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3.3 BranchingandEnumerationStrategies . . . . . . . . . . . . . . . . . . . . . . . 137
5.4 ComputationalExperiments . . . . . . . . . . . . .
