| 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 | 142 |
|---|
| 144 | 142 |
|---|
| 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 Notat
|