Port Automation and Vehicle Scheduling: Advanced Algorithms for Scheduling Problems of AGVs

✍ Scribed by Hassan Rashidi; Edward P. K. Tsang

• Publisher: CRC Press
• Year: 2022
• Tongue: English
• Leaves: 305
• Edition: 3
• Category: Library

✦ Synopsis

Container terminals are constantly being challenged to adjust their throughput capacity to match fluctuating demand. Examining the optimization problems encountered in today’s container terminals, Port Automation and Vehicle Scheduling: Advanced Algorithms for Scheduling Problems of AGVs, Third Edition provides advanced algorithms for handling the scheduling of Automated Guided Vehicles (AGVs) in ports. Building on the earlier editions, previously titled Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, this book has undergone extensive revisions and includes two new chapters. New material addresses the solutions to the modeling of decisions in Chapter 3, while in Chapter 11 the authors address an emerging challenge in automated container terminals with integrated management. Key Features: ◾Classifies the optimization problems of the ports into five scheduling decisions. For each decision, it supplies an overview, formulates each of the decisions as constraint satisfaction and optimization problems, and then covers possible solutions, implementation, and performance. ◾Explores in Part One of the book the various optimization problems in modern container terminals, while details in Part Two advanced algorithms for the minimum cost flow (MCF) problem and for the scheduling problem of AGVs in ports. ◾Offers complete package that can help readers address the scheduling problems of AGVs in ports. This is a valuable reference for port authorities and researchers, including specialists and graduate students in operation research. For specialists, it provides novel and efficient algorithms for network flow problems. For students, it supplies the most comprehensive survey of the field along with a rigorous formulation of the problems in port automation.

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Contents
List of Figures
List of Tables
List of Abbreviations
Preface
Acknowledgments
Authors
1. Introduction
1.1. Objectives
1.1.1. Optimization in Ports
1.1.2. Scheduling of AGVs and Development of Advanced Algorithms
1.2. Structure of Subsequent Chapters
PART 1: OPTIMIZATION PROBLEMS FACING MODERN CONTAINER TERMINALS
2. Problems in Container Terminals
2.1. Compartments
2.2. Operations
2.3. Decisions to Be Made
2.3.1. Allocation of Berths to Arriving Vessels and QCs to Docked Vessels
2.3.2. Storage Space Assignment
2.3.3. Rubber Tyred Gantry Crane Deployment
2.3.4. Scheduling and Routing of Vehicles
2.3.5. Appointment Times to XTs
3. Formulations of the Problems
3.1. Allocation of Berths to Arriving Vessels and Quay Cranes to Docked Vessels
3.1.1. Assumptions
3.1.2. Decision Variables and Domains
3.1.3. Constraints
3.1.4. Objective Function
3.2. Storage Space Assignment
3.2.1. Assumptions
3.2.2. Decision Variables and Domains
3.2.3. Constraints
3.2.4. Objective Function
3.3. Rubber Tyred Gantry Crane Deployment
3.3.1. Assumptions
3.3.2. Decision Variables and Domains
3.3.3. Constraints
3.3.4. Objective Function
3.4. Scheduling and Routing of Vehicles
3.4.1. Assumptions
3.4.2. Decision Variables and Domains
3.4.3. Constraints
3.4.4. Objective Function
3.5. Appointment Times to eXternal Trucks
3.5.1. Assumptions
3.5.2. Decision Variables and Domains
3.5.3. Constraints
3.5.4. Objective Function
3.6. Container Terminals over the World: A Survey
3.7. Summary and Conclusion
4. Solutions to the Decisions: Review and Suggestions
4.1. Simulation of Container Terminals
4.2. Selecting an Architecture
4.3. Classification of Scheduling Methods
4.4. Frameworks for Optimization and Scheduling Problems
4.5. Solution Methods for Vehicle Problems, Developed before 2000
4.6. Solution Methods for Vehicle Problems, Developed in the Twenty-First Century
4.7. Suggestions for How to Do the Simulation
4.7.1. Microscopic Simulation
4.7.1.1. Entities
4.7.1.2. Resources
4.7.1.3. Control Elements
4.7.1.4. Operations
4.7.2. Macroscopic Simulation
4.7.2.1. Agent-Based Simulation (ABS)
4.7.2.2. Object-Based Simulation (OBS)
4.8. Proposed Frameworks for Implementation
4.9. Evaluation and Monitoring
4.10. Summary and Conclusion
PART 2: ADVANCED ALGORITHMS FOR THE SCHEDULING PROBLEM OF AUTOMATED GUIDED VEHICLES
5. Vehicle Scheduling: A Minimum Cost Flow Problem
5.1. Reasons to Choose This Problem
5.2. Assumptions
5.3. Variables and Notations
5.4. The Minimum Cost Flow Model
5.4.1. Graph Terminology
5.4.2. The Standard Form of the Minimum Cost Flow Model
5.4.3. Applications of the Minimum Cost Flow Model
5.5. The Special Case of the MCF Model for Automated Guided Vehicles Scheduling
5.5.1. Nodes and Their Properties in the Special Graph
5.5.2. Arcs and Their Properties in the Special Graph
5.5.3. The MCF-AGV Model for the Automated Guided Vehicles Scheduling
5.6. Summary and Conclusion
6. Network Simplex: The Fastest Algorithm
6.1. Reasons to Choose NSA
6.2. The Network Simplex Algorithm
6.2.1. Spanning Tree Solutions and Optimality Conditions
6.2.2. The Algorithm NSA
6.2.3. The Difference between NSA and Original Simplex
6.2.4. A Literature over Pricing Rules
6.2.5. Strongly Feasible Spanning Tree
6.3. Simulation Software
6.3.1. The Features of Our Software
6.3.2. The Implementation of NSA in Our Software
6.3.3. How the Program Works
6.3.4. The Circulation Problem
6.4. Experimental Results
6.5. An Estimate of the Algorithm’s Complexity in Practice
6.6. Limitation of the NSA in Practice
6.7. Summary and Conclusion
7. Network Simplex Plus: Complete Advanced Algorithm
7.1. Motivations
7.2. The Network Simplex Plus Algorithm (NSA+)
7.2.1. Anti-Cycling in NSA+
7.2.2. Memory Technique and Heuristic Approach in NSA+
7.2.3. The Differences between NSA and NSA+
7.3. A Comparison between NSA and NSA+
7.4. Statistical Test for the Comparison
7.5. Complexity of Network Simplex Plus Algorithm (NSA+)
7.6. Software Architecture for Dynamic Aspect
7.7. Experimental Results from the Dynamic Aspect
7.8. Summary and Conclusion
8. Dynamic Network Simplex: Dynamic Complete Advanced Algorithm
8.1. Motivations
8.2. Classification of Graph Algorithms and Dynamic Flow Model
8.3. The Dynamic Network Simplex Algorithm
8.3.1. Data Structures
8.3.2. Memory Management
8.3.3. The Algorithms DNSA and DNSA+
8.4. Software Architecture for Dynamic Aspect
8.5. A Comparison between DNSA+ and NSA+
8.6. Statistical Test for the Comparison
8.7. Complexity of the Algorithm
8.8. Summary and Conclusion
9. Greedy Vehicle Search: An Incomplete Advanced Algorithm
9.1. Motivations
9.2. Problem Formalization
9.2.1. Nodes and Their Properties in the Incomplete Graph
9.2.2. Arcs and Their Properties in the Incomplete Graph
9.2.3. The Special Case of the MCF-AGV Model for Automated Guided Vehicles Scheduling
9.3. Algorithm Formalization
9.4. Software Architecture for Dynamic Aspect
9.5. A Comparison between GVS and NSA+ and Quality of the Solutions
9.6. Statistical Test for the Comparison
9.7. Complexity of Greedy Vehicle Search
9.7.1. Complexity of GVS for Static Problem
9.7.2. Complexity of GVS for Dynamic Problem
9.8. A Discussion over GVS and Meta-Heuristic
9.9. Summary and Conclusion
10. Multi-Load and Heterogeneous Vehicles Scheduling: Hybrid Solutions
10.1. Motivation
10.2. Assumptions and Formulation
10.2.1. Assumptions
10.2.2. Formulation
10.2.3. Decision Variable
10.2.4. Constraints and Objective Function
10.3. Solutions to the Problem
10.3.1. Simulated Annealing Method for the Multi-Load AGVs
10.3.2. The Hybrid of SAM and NSA for Heterogeneous AGVs
10.4. Experimental Results
10.5. Summary and Conclusion
11. Integrated Management of Equipment in Automated Container Terminals
11.1. Introduction
11.2. Motivations
11.3. Related Works over Automated Container Terminals
11.4. Problem Description and Modeling
11.4.1. Complexity of the Problem
11.4.2. Problem Formulation
11.5. The Proposed Method
11.5.1. Chromosome
11.5.2. Crossover Operator
11.5.3. Mutation Operator
11.6. Simulation and Evaluation of the Proposed Method
11.6.1. Parameters
11.6.2. Numerical Experiments
11.7. Summary and Conclusions
12. Conclusions and Future Research
12.1. Summary of This Research Done
12.2. Observations and Conclusions
12.3. Research Contributions
12.4. Future Research
12.4.1. Scheduling and Routing of the Vehicles
12.4.2. Economic and Optimization Model
12.4.3. Automated Container Terminal
12.4.4. The Next Generation of Container Terminal
Appendix: Information on Web
Overview of This Research
Assumptions
Development
Some Interfaces of Our Software
References
Index