Dynamic Fleet Management (eBook)

TABLE OF CONTENTS 7
PREFACE 9
ACKNOWLEDGMENTS 14
Chapter 1 PLANNED ROUTE OPTIMIZATION FOR REAL- TIME VEHICLE ROUTING 15
1.1 INTRODUCTION 15
1.2 ADAPTATION OF STATIC ALGORITHMS 18
1.2.1 Many-to-one (One-to-many) Problems 19
1.2.1.1 Local update procedures 19
1.2.1.2 Reoptimization procedures 20
1.2.2 Many-to-many Problems 22
1.2.2.1 Local update procedures 22
1.2.2.2 Reoptimization procedures 22
1.2.3 Multiple Plan Approach (MPA) 24
1.3 DIVERSION 24
1.4 ANTICIPATION OF FUTURE REQUESTS 26
1.4.1 Double Horizon 26
1.4.2 Waiting Strategies 26
1.4.3 Fruitful Regions 28
1.4.4 Multiple Scenario Approach (MSA) 28
1.5 CONCLUSION 28
ACKNOWLEDGEMENTS 30
REFERENCES 30
Chapter 2 CLASSIFICATION OF DYNAMIC VEHICLE ROUTING SYSTEMS 33
2.1 INTRODUCTION 33
2.2 THE DYNAMIC VEHICLE ROUTING PROBLEM 35
2.3 STATIC VERSUS DYNAMIC VEHICLE ROUTING 37
2.4 THE DEGREE OF DYNAMISM 40
2.4.1 Dynamism Without Time Windows 41
2.4.1.1 The degree of dynamism 41
2.4.1.2 Effective Degree of Dynamism - EDOD 43
2.4.2 Dynamism and Time Windows 43
2.4.3 Effective Degree of Dynamism – EDOD-TW 44
2.5 MEASURING THE PERFORMANCE OF DVRP’S 45
2.5.1 Competitive Analysis 46
2.5.2 Determining the Objectives 47
2.6 THREE-ECHELON FRAMEWORK FOR DVRP’s 48
2.6.1 Echelon I – Weakly Dynamic Systems 48
2.6.2 Echelon II – Moderately Dynamic Systems 49
2.6.3 Echelon III – Strongly Dynamic Systems 50
2.6.4 System Classification 51
2.7 CONCLUDING REMARKS 53
REFERENCES 53
Chapter 3 DYNAMIC AND STOCHASTIC VEHICLE ROUTING IN PRACTICE 55
3.1 INTRODUCTION 55
3.2 THE DYNAMIC AND STOCHASTIC VEHICLE ROUTING PROBLEM 56
3.3 APPLICATION EXAMPLES 59
3.4 A FORMAL DESCRIPTION OF DYNAMIC AND STOCHASTIC VRPS 61
3.5 A DYNAMIC AND STOCHASTIC VRP SOLVER 63
3.5.1 Overall Architecture 63
3.5.2 Requirements 65
3.5.3 The SPIDER DSVRP Solver 67
3.6 A ROBUST APPROACH TO DYNAMIC AND STOCHASTIC VRPS 68
3.7 LEARNING EVENT MODELS 71
3.7.1 Bayesian Networks 72
3.7.2 Modeling of Stochastic VRP Events 73
3.8 CONCLUSIONS AND FURTHER RESEARCH 75
REFERENCES 75
Chapter 4 A PARALLELIZABLE AND APPROXIMATE DYNAMIC PROGRAMMING- BASED DYNAMIC FLEET MANAGEMENT MODEL WITH RANDOM TRAVEL TIMES AND MULTIPLE VEHICLE TYPES 78
4.1 INTRODUCTION AND RELEVANT LITERATURE 78
4.2 PROBLEM DESCRIPTION DESCRIPTION DESCRIPTION DESCRIPTION DESCRIPTION 82
4.3 MODEL FORMULATION 83
4.3.1 Deterministic Travel Times Times Times Times Times Times Times 83
4.3.2 Random Travel Times 85
4.4 STRUCTURE OF THE APPROXIMATE SUBPROBLEMS AND PARALLELIZATION PARALLELIZATION PARALLELIZATION 88
4.5 CHARACTERIZING THE ARRIVAL RANDOM VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES 93
4.6 UPDATING AND IMPROVING THE VALUE FUNCTION APPROXIMATIONS 94
4.7 COMPUTATIONAL EXPERIMENTS 98
4.7.1 Experimental Setup 98
4.7.2 Computational Results Results 101
4.8 CONCLUSIONS AND RESEARCH PROSPECTS 104
REFERENCES 105
Chapter 5 INTEGRATED MODEL FOR THE DYNAMIC ON- DEMAND AIR TRANSPORTATION OPERATIONS 107
5.1 INTRODUCTION 107
5.2 BACKGROUND AND LITERATURE SURVEY 108
5.2.1 Background of the Problem 109
5.2.2 Previous Work 110
5.3 THE INTEGRATED MODEL 111
5.3.1 Crew Network and Crew Reassignment 112
5.3.2 The Fleet-station Time Line 114
5.3.3 The Model Formulation 115
5.3.4 Solution Algorithm 116
5.3.5 Dynamic Plan Adjustment to Handle Uncertainty 118
5.3.5.1 Demand uncertainty 119
5.3.5.2 Uncertainty on aircraft availability 119
5.4 COMPUTATIONAL EXPERIMENTS 120
5.4.1 New Demand without Time Window 120
5.4.2 New Demand with Time Window 122
5.5 CONCLUSIONS 122
REFERENCES 123
Chapter 6 AN INTERMODAL TIME-DEPENDENT MINIMUM COST PATH ALGORITHM 124
With an Application to Hazmat Routing 124
6.1 INTRODUCTION 124
6.2 BACKGROUND 126
6.2.1 Shortest Path Algorithms 127
6.2.2 Hazmat Transportation Problem 128
6.3 PROBLEM FORMULATION FORMULATION 129
6.4 ALGORITHM AND PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES PROPERTIES 132
6.5 EXTENSION OF THE TDIMCP ALGORITHM TO MINIMUM RISK HAZMAT ROUTING ROUTING ROUTING ROUTING ROUTING ROUTING ROUTING 136
6.6 NUMERICAL TESTS OF HAZMAT ROUTING PROBLEM 138
6.7 CONCLUDING REMARKS 141
REFERENCES 142
Chapter 7 REAL- TIME EMERGENCY RESPONSE FLEET DEPLOYMENT: CONCEPTS, SYSTEMS, SIMULATION & CASE STUDIES
7.1 INTRODUCTION 144
7.2 AN INTEGRATED EMERGENCY VEHICLE FLEET MANAGEMENT SYSTEM 146
7.3 PROBLEM STATEMENT 148
7.4 LITERATURE REVIEW 151
7.5 SIMULATION 154
7.5.1 Emergency Module 155
7.5.2 Vehicle Module 156
7.5.3 Optimizer Module 156
7.5.4 Calibration of Simulation Model 156
7.5.5 Output Analysis 156
7.6 MATHEMATICAL MODEL 157
7.6.1 Notation 157
7.6.2 Mathematical Model 160
7.6.3 Cost of Travel Time 162
7.6.4 Coverage Rate Rate 162
7.6.5 Penalty Associated with the Coverage Deficiency 163
7.7 CASE STUDY 163
7.7.1 Comparison of Dispatching Strategies 164
7.7.2 Computation Time 165
7.7.3 Comparison of Shortest Path Algorithms on Average Response Time ( ART) 166
7.7.4 Impact of Penalty Coefficients 166
7.7.5 Impact of Location Plans of Station 167
7.8 CONCLUSIONS AND FUTURE RESEARCH 170
REFERENCES 170
Chapter 8 VEHICLE ROUTING AND SCHEDULING MODELS, SIMULATION AND CITY LOGISTICS 174
8.1 INTRODUCTION 175
8.2 CONCEPTUAL APPROACH TO A DECISION SUPPORT SYSTEM FOR THE DESIGN AND EVALUATION OF CITY LOGISTIC APPLICATIONS 178
8.3 AIMSUN MICROSCOPIC TRAFFIC SIMULATOR AND CITY LOGISTICS 184
8.4 VEHICLE ROUTING AND SCHEDULING MODELS AND CITY LOGISTICS 186
8.4.1 Automatic Vehicle Routing Formulation 190
8.4.2 Dealing with the Appropriate Time Dependent Travel Times 192
8.5 COMBINING VEHICLE ROUTING WITH AIMSUN SIMULATION 193
8.6 TWO CASE STUDIES 196
8.6.1 The Lucca Case 198
8.6.2 Piacenza Case 200
8.7 CONCLUSIONS 203
8.8 ACKNOWLEDGEMENTS 204
REFERENCES 204
Chapter 9 DYNAMIC MANAGEMENT OF A DELAYED DELIVERY VEHICLE IN A CITY LOGISTICS ENVIRONMENT 207
9.1 DISTRIBUTION IN A CITY LOGISTICS ENVIRONMENT 207
9.2 USER REQUIREMENTS AND SYSTEM DESCRIPTION 209
9.3 MANAGING A DELAYED DISTRIBUTION VEHICLE 212
9.3.1 Monitoring and Detection 213
9.3.2 Decision Making and Rerouting 214
9.4 SYSTEM EVALUATION 217
9.5 CONCLUSIONS 223
ACKNOWLEDGMENTS 224
REFERENCES 224
APPENDIX A 226
Chapter 10 REAL- TIME FLEET MANAGEMENT AT ECOURIER LTD 228
10.1 INTRODUCTION 228
10.2 THE AUTOMATED INFORMATION-BASED ALLOCATION SYSTEM 229
10.2.1 Zoning the Service Territory 230
10.2.2 Time Subdivision 231
10.2.3 Forecasting Logistics Requirements 232
10.2.3.1 Demand forecasting 233
10.2.3.2 Travel time forecasting 234
10.2.4 On Line and Off Line Procedures 238
10.2.4.1 Initialization 238
10.2.4.2 Allocating couriers 239
10.2.4.3 The ALLOCATE module 239
10.2.4.4 The allocation procedure 241
10.2.4.5 The fast insertion procedure 242
10.2.4.6 The background optimization procedure 243
10.2.5 Parallelization Strategy 243
10.3 LITERATURE REVIEW 243
10.4 CONCLUSIONS 245
REFERENCES 246
INDEX 248