On some generalized routing problems [Elektronische Ressource] / vorgelegt von Michael Drexl

Sujets

• Handel

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2007
• Nombre de lectures: 21
• Langue: Deutsch

Extrait

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 . . . . . . . . . . . . .