Transportation

Description

This book contains eleven chapters describing some of the most recent methodological operations research developments in transportation. It is structured around the main transportation modes, and each chapter is written by a group of well-recognized researchers. Because of the major impact of operations research methods in the field of air transportation over the past forty years, it is befitting to open the book with a chapter on airlineoperations management. While many past publications have focused on airline strategic and tactical planning, Ball, Barnhart, Nemhauser and Odoni have chosen to address the organization and control of recovery operations in the event of disturbances. This line of research is relatively new and of major importance to the airline industry. The second chapter, by Desaulniers and Hickman, surveys the planning of public transit operations. The problems addressed and the methods employed in transit planning, for example those arising in network design, passenger assignment, scheduling, and fleet and crew assignment, are often similar to those of the airlines. The railway optimization chapter, by Caprara, Kroon, Monaci, Peeters and Toth, covers the realm of planning problems encountered in railway planning, with an emphasis on European passenger railways. Again, several of these issues are similar to those observed in other modes, but some problems are specific to the railway industry, such as train platforming, rolling stock circulation, and train unit shunting. The fourth chapter, by Christiansen, Fagerholt, Nygreen and Ronen, contains an extensive survey of maritime transportation problems, methods and applications. Compared with other modes, maritime transportation has received relatively little attention from operations researchers. Yet this field is rapidly expanding with the consolidation of major shipping companies and the development of large container ports.The next three chapters cover a variety of planning problems arising in vehicle fleet management. The chapter by Powell, Bouzaiene-Ayari and Simao addresses truck transportation planning in contexts where information processes are dynamic. The focus is on the development of models that capture the flow of information and decisions. The vehicle routing chapter, by Cordeau, Laporte, Savelsbergh and Vigo, concerns what is arguably the most central problem in distribution management. It surveys several families of vehicle routing problems, including classical models, inventory routing, and stochastic routing. In the transportation on demand chapter, Cordeau, Laporte, Potvin and Savelsbergh consider the planning of pickup and delivery operations made at the request of users, such as those encountered in courier services, dial-a-ride operations, dial-a-flight systems, and ambulance fleet deployment. Preface......Page 1 Introduction......Page 4 Flow constraints in the infrastructure of commercial aviation......Page 8 The ``physics'' of airport capacity......Page 10 Separation requirements and high-speed exits.......Page 11 Mix of movements.......Page 12 Capacity envelope and its computation......Page 13 The sequencing problem......Page 14 Interactions between operations on different runways.......Page 15 Weather-related factors.......Page 16 State and performance of the ATM system.......Page 17 The variability and unpredictability of the capacity of runway systems......Page 18 The capacity of airspace sectors......Page 20 Options and current practice on airport scheduling......Page 22 Critical issues regarding restricting schedules......Page 23 Basic premises......Page 26 Ground holding (including ground stops).......Page 27 Arrival sequencing.......Page 28 Global models......Page 29 Deterministic ground holding models......Page 31 Uncertainty and stochastic models......Page 32 Ground holding models with stochastic airport capacity......Page 33 Collaborative decision making......Page 35 CDM resource allocation procedures for ground delay programs......Page 36 Properties of RBS.......Page 38 Compression as trading.......Page 39 Air carrier response options......Page 40 Simulation models......Page 41 Airline schedule recovery......Page 43 Aircraft recovery......Page 44 Expanded aircraft recovery......Page 47 Crew recovery......Page 48 Passenger recovery......Page 51 Robust airline scheduling......Page 53 Robust fleet assignment......Page 54 Degradable airline scheduling......Page 56 Robust aircraft routing: Allocating slack to minimize delays......Page 57 Robust crew scheduling......Page 59 Minimizing expected crew costs......Page 60 Move-up crews......Page 61 Conclusions......Page 63 References......Page 64 Introduction......Page 71 Strategic planning......Page 72 Network design......Page 73 Passenger assignment......Page 80 Uncongested assignment......Page 82 Congested assignment......Page 85 Frequency setting......Page 88 Timetabling......Page 93 Operational planning......Page 96 Vehicle scheduling......Page 97 Duty scheduling......Page 102 Integrated vehicle and duty scheduling......Page 106 Crew rostering......Page 110 Parking and dispatching......Page 111 Maintenance scheduling......Page 113 Real-time control......Page 114 Vehicle holding......Page 115 Other strategies......Page 119 Cited references......Page 122 Introduction......Page 130 Strategic planning......Page 132 Rolling stock management......Page 133 Line planning......Page 134 Literature review......Page 136 Assumptions......Page 137 The model......Page 138 Comments......Page 140 Noncyclic timetabling......Page 142 Literature review......Page 143 Model formulation......Page 144 The model......Page 145 Experimental results......Page 147 Cyclic timetabling......Page 150 Train platforming......Page 151 Literature review......Page 152 Model formulation......Page 153 Rolling stock circulation......Page 155 Literature review......Page 157 Model formulation......Page 159 Experimental results......Page 161 Literature review......Page 162 Model formulation......Page 163 Maintenance routing......Page 166 Train unit shunting......Page 168 Literature review......Page 169 Model formulation......Page 171 Crew planning......Page 173 Literature review......Page 175 Model formulation......Page 176 Crew Scheduling......Page 177 Crew Rostering......Page 179 An integrated approach......Page 180 Experimental results......Page 181 Perspective......Page 183 References......Page 184 Introduction......Page 189 Characteristics and terminology of maritime transportation......Page 196 Ship and port characteristics......Page 197 Types of shipping services......Page 198 Cargo characteristics......Page 199 Terms used in maritime transportation planning......Page 200 Strategic planning in maritime transportation......Page 201 Ship design......Page 202 Fleet size and mix......Page 205 Homogeneous fleet size......Page 206 Heterogeneous fleet size and mix......Page 209 Liner network design......Page 211 Traditional liner operations......Page 212 Hub and spoke networks......Page 216 Design of maritime transport systems......Page 220 Contract evaluation......Page 221 Scheduling problems for industrial and tramp shipping......Page 222 Full shiploads......Page 223 Multiple cargoes with fixed cargo size......Page 228 Multiple cargoes with flexible cargo size......Page 232 Multiple products......Page 234 Contracted and optional cargoes......Page 236 Use of spot charters......Page 237 Solution approaches for industrial and tramp scheduling models......Page 238 The master problem in the DW decomposition approach.......Page 239 Column generation and the subproblems within the DW decomposition approach.......Page 240 The set partitioning approach......Page 241 Maritime supply chains......Page 242 Inventory routing for a single product......Page 243 Inventory routing for multiple products......Page 251 Other maritime supply chain applications......Page 256 Fleet deployment in liner shipping......Page 257 Barge scheduling......Page 261 Scheduling naval combat vessels......Page 262 Ship management......Page 263 Operational scheduling......Page 264 Environmental routing......Page 265 Ocean currents......Page 266 Speed selection......Page 267 Ship loading......Page 268 Booking of single orders......Page 270 Strategic planning and uncertainty......Page 271 Robust tactical planning......Page 272 Persistence......Page 275 Mergers, acquisitions, and collaborations......Page 276 Shift from industrial to tramp shipping......Page 277 Strategic planning issues and market interaction......Page 278 Conclusion......Page 279 References......Page 280 Introduction......Page 285 Some illustrative applications......Page 286 A resource model......Page 289 What is a resource?......Page 290 Resource layering......Page 291 Major problem classes......Page 293 The states of our system......Page 294 Bibliographic notes......Page 295 Modeling exogenous information processes......Page 296 Modeling time......Page 297 The information process......Page 298 Lagged information processes......Page 300 Information and sigma-algebras......Page 302 Representing decisions......Page 306 The decision function......Page 307 System dynamics......Page 309 An optimization formulation......Page 311 Algorithmic strategies......Page 312 Rolling horizon procedures......Page 313 Stochastic programming......Page 314 Dynamic programming......Page 316 Incorporating low-dimensional patterns......Page 320 Summary: The four information classes......Page 324 Bibliographic notes......Page 328 Discrete value function approximations for a single resource......Page 330 Basis functions......Page 333 Auxiliary functions......Page 334 Linear functional approximations......Page 335 Separable piecewise-linear functional approximations......Page 336 The organization of information and decisions......Page 338 A dynamic model......Page 341 Optimization formulation......Page 346 Some numerical experiments......Page 348 A model of the dynamic load assignment problem......Page 350 Optimization formulation......Page 352 Some numerical experiments......Page 355 Batch processes for less-than-truckload trucking......Page 356 A single link model of the dynamic dispatch problem......Page 358 A solution algorithm for the single-link problem......Page 359 References......Page 362 Introduction......Page 366 Formulations......Page 367 Exact algorithms for the CVRP......Page 369 Branch-and-bound and set partitioning based algorithms......Page 370 Branch-and-cut algorithms......Page 373 Heuristics for the VRP......Page 374 Route construction heuristics.......Page 375 Two-phase heuristics.......Page 376 Metaheuristics......Page 378 Local search heuristics.......Page 380 Population search heuristics.......Page 382 Learning mechanisms.......Page 383 The vehicle routing problem with time windows......Page 384 Formulation of the VRPTW......Page 385 Lagrangian relaxation based algorithms......Page 386 Column generation algorithms......Page 388 A branch-and-cut algorithm......Page 390 Construction heuristics......Page 391 Improvement heuristics......Page 392 Tabu search heuristics.......Page 393 Genetic algorithms.......Page 394 Other metaheuristics.......Page 395 The inventory routing problem......Page 397 Definition of the IRP......Page 398 Motivating example......Page 399 Single customer analysis......Page 400 The two-customer IRP......Page 402 Literature review on the IRP......Page 403 Stochastic vehicle routing problems......Page 409 The vehicle routing problem with stochastic customers......Page 412 The vehicle routing problem with stochastic demands......Page 413 The vehicle routing problem with stochastic customers and demands......Page 414 The vehicle routing problem with stochastic travel times......Page 415 References......Page 416 Introduction......Page 428 The vehicle routing problem with pickup and delivery......Page 430 Exact algorithms......Page 432 Heuristics......Page 434 Exact algorithms......Page 435 Heuristics......Page 437 Scheduling......Page 438 The static single-vehicle DARP......Page 439 The static multiple-vehicle DARP......Page 440 The dynamic DARP......Page 443 Urban courier service problems......Page 444 A tabu search heuristic for the UCSP......Page 445 A double-horizon strategy for the UCSP......Page 446 The dial-a-flight problem......Page 447 The static dial-a-flight problem......Page 449 A model for the static dial-a-flight problem......Page 450 Algorithmic issues related to the dynamic dial-a-flight problem......Page 452 Two early ambulance location models......Page 453 Static models with extra coverage......Page 454 Probabilistic models with extra coverage......Page 457 A dynamic model......Page 460 References......Page 461 Introduction......Page 466 Freight transportation systems......Page 468 Container intermodal transportation......Page 469 Customized, consolidation, and intermodal transportation......Page 470 Consolidation and intermodal terminals......Page 473 Models for system design......Page 477 Location with balancing requirements......Page 478 Multicommodity production distribution......Page 480 Hub-location models......Page 482 Service network design......Page 484 Static service network design......Page 486 Design of postal services......Page 488 Time-dependent service network design......Page 491 Port dimensioning......Page 492 Container fleet management......Page 493 Berth scheduling......Page 500 Quay-crane scheduling......Page 506 Stowage planning and sequencing......Page 508 Storage activities in the yard......Page 513 Allocation and dispatching of yard cranes and transporters......Page 516 Strategic planning of multimodal systems......Page 519 Demand......Page 521 Supply representation and assignment......Page 522 Perspectives......Page 525 References......Page 528 Introduction......Page 537 Special issues of journals......Page 542 Books......Page 543 Reports......Page 544 Software......Page 545 Classification......Page 546 Risk assessment......Page 549 Frequency analysis......Page 550 Historical frequencies......Page 553 Logical diagram-based techniques......Page 554 Modeling the impact area......Page 556 Gaussian plume model......Page 557 Risk cost......Page 561 Cleanup costs.......Page 562 Traffic incident delay.......Page 563 Perceived risks......Page 564 Risk on a hazmat transportation route......Page 566 Edge risk......Page 567 Path risk......Page 570 Expected disutility model.......Page 574 Demand satisfaction model.......Page 575 Path risk axioms......Page 576 Routing and scheduling......Page 578 Local routing problems......Page 579 Rail transport......Page 580 Multiobjective approaches to local routing......Page 581 Local routing and scheduling problems......Page 585 A priori optimization......Page 586 Adaptive route selection with real-time updates......Page 588 Global routing problems......Page 591 Equity considerations in global route planning......Page 592 Hazmat transportation network design......Page 595 Facility location and transportation......Page 597 Synthesis and future research directions......Page 603 Risk calculation - consequences......Page 604 Risk equity......Page 605 Implementation......Page 606 Recent concern: security......Page 607 Acknowledgements......Page 608 References......Page 609 Background......Page 620 The basic theme......Page 621 The Wardrop conditions......Page 622 Link flow representations......Page 624 Variational inequality representations......Page 627 A fixed demand reformulation of the elastic demand model......Page 629 The equivalence between equilibria in different representations......Page 630 Properties of equilibria......Page 632 Existence of equilibria......Page 633 Uniqueness of equilibria......Page 634 Alternative definitions......Page 636 Relationships......Page 638 User versus system optimality......Page 640 Bibliographical notes......Page 641 Multi-mode and multi-attribute models......Page 643 Introduction and equilibrium characterizations......Page 649 Wardrop-like principles......Page 652 Strategic models......Page 654 Bibliographical notes......Page 661 General guidelines......Page 663 Model structures and the verification of equilibria......Page 664 Decomposition-coordination......Page 665 Decomposition by Lagrangian relaxation......Page 666 Decomposition by linearization......Page 667 Merit functions and convergence for asymmetric models......Page 668 Implementations and computational experience......Page 671 Bibliographical notes......Page 673 Multi-mode and multi-attribute models......Page 675 Side constraints......Page 678 Strategic model......Page 679 Bibliographical notes......Page 680 Introduction......Page 681 Sensitivity analysis of separable traffic equilibrium......Page 683 Limitations of the classical sensitivity framework......Page 685 Inducing system-optimal flows through link tolls......Page 688 Tolls for raising revenues......Page 691 A continuous network design problem......Page 693 Bibliographical notes......Page 697 Definition and formulations......Page 699 Monotonicity properties......Page 700 Algorithms......Page 701 Bibliographical notes......Page 702 References......Page 703 Introduction......Page 711 Traffic flow modeling approaches......Page 712 Properties of traffic flow......Page 713 Microscopic traffic flow models......Page 715 Stimulus-response models.......Page 716 Psycho-spacing models.......Page 718 Submicroscopic simulation models.......Page 719 Cellular Automaton (CA) or particle hopping models.......Page 720 Conservation of vehicles and the kinematic wave model.......Page 721 Payne-type models.......Page 723 Gas-kinetic flow models......Page 724 Model application......Page 726 Introduction......Page 728 Guidance objectives......Page 729 RGIS functional characteristics......Page 730 Predictive guidance and consistency......Page 732 Approaches for predictive guidance generation......Page 733 Driver response to RGIS......Page 735 Areas of current research......Page 737 UTC systems: general requirements......Page 739 Principles of traffic signal control......Page 741 Traffic-responsive systems......Page 742 TRANSYT (TRAffic Network StudY Tool).......Page 743 SCOOT (Split Cycle Offset Optimization Technique).......Page 744 SCATS (Sydney Coordinated Adaptive Traffic System).......Page 746 TUC (Traffic-Responsive Urban Control).......Page 747 PRODYN.......Page 748 Operational Research (OR) techniques......Page 749 The control loop......Page 750 Fixed-time ramp metering strategies.......Page 752 Local ramp metering.......Page 753 Multivariable regulator strategies.......Page 754 Nonlinear optimal ramp metering strategies.......Page 755 Route guidance control strategies......Page 756 The motorway network traffic model......Page 757 The constrained optimal control problem......Page 759 Application results......Page 760 The no-control case......Page 761 The control case......Page 762 References......Page 764 Subject Index......Page 771