Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, Second Edition

by Hassan Rashidi, Edward Tsang

Overview

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, Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, Second Edition provides advanced algorithms for handling the scheduling of automated guided vehicles (AGVs) in ports.

The research reported in this book represents a complete package that can help readers address the scheduling problems of AGVs in ports. The techniques presented are general and can easily be adapted to other areas.

This book is ideal 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.

This book is divided into two parts. Part one explores the various optimization problems in modern container terminals. The second part details advanced algorithms for the minimum cost flow (MCF) problem and for the scheduling problem of AGVs in ports.

The book classifies optimization problems 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.

The book extends the dynamic network simplex algorithm, the fastest algorithm for solving the minimum cost flow problem, and develops four new advanced algorithms. In order to verify and validate the algorithms presented, the authors discuss the implementation of the algorithm to the scheduling problem of AGVs in container terminals.

Product Details

ISBN-13:	9781498732536
Publisher:	Taylor & Francis
Publication date:	08/14/2015
Edition description:	Revised
Pages:	260
Product dimensions:	6.20(w) x 9.20(h) x 0.80(d)

About the Author

Hassan Rashidi earned a BSc in computer engineering in 1986 as well as an MSc in systems engineering and planning in 1989 with the highest honors at Isfahan University of Technology, Iran. He joined the Department of Computer Science at the University of Essex in the United Kingdom, as a PhD student in October 2002 and earned his PhD in 2006. He was a researcher in the British Telecom research centre in United Kingdom in 2005. He is currently an associate professor at Allameh Tabataba’i University, Tehran, Iran, and a visiting academic at the University of Essex. He is an international expert in the applications of the network simplex algorithm to automated vehicle scheduling and has published many conference and journal papers.

Edward Tsang has a first degree in business administration (major in finance) and an MSc and PhD in computer science. He has broad interests in applied artificial intelligence, particularly constraint satisfaction, computational finance, heuristic search, and scheduling. He is currently a professor at the School of Computer Science and Electronic Engineering at the University of Essex, where he leads the computational finance group and the constraint satisfaction and optimization group. He is also the director of the Centre for Computational Finance and Economic Agents, an interdisciplinary center. He founded the Technical Committee for Computational Finance and Economics under the IEEE Computational Intelligence Society.

Table of Contents

Introduction
Objectives
Optimization in Ports
Scheduling of AGVs and Development of Advanced Algorithms
Structure of Subsequent Chapters

Problems in Container Terminals
Compartments
Operations
Decisions to Be Made
Allocation of Berths to Arriving Vessels and QCs to Docked Vessels
Storage Space Assignment
RTGC Deployment
Scheduling and Routing of Vehicles
Appointment Times to External Trucks

Formulations of the Problems and Solutions
Allocation of Berths to Arriving Vessels and QCs to Docked Vessels
Assumptions
Decision Variables and Domains
Constraints
Objective Function
Storage Space Assignment
Assumptions
Decision Variables and Domains
Constraints
Objective Function
RTGC Deployment
Assumptions
Decision Variables and Domains
Constraints
Objective Function
Scheduling and Routing of Vehicles
Assumptions
Decision Variables and Domains
Constraints
Objective Function
Appointment Times to External Trucks
Assumptions
Decision Variables and Domains
Constraints
Objective Function
Container Terminals over the World, a Survey
Survey on Simulation, Implementation, Solution Methods, and Evaluation
Simulation and Setting the Parameters
Selecting an Architecture
Solution Methods, a Survey
Evaluation and Monitoring
Summary and Conclusion

Vehicle Scheduling: A Minimum Cost Flow Problem
Reasons to Choose This Problem
Assumptions
Variables and Notations
MCF Model
Graph Terminology
Standard Form of the MCF Model
Applications of the MCF Model
Special Case of the MCF Model for AGV Scheduling
Nodes and Their Properties in the Special Graph
Arcs and Their Properties in the Special Graph
MCF-AGV Model for the AGV Scheduling
Summary and Conclusion

Network Simplex: The Fastest Algorithm
Reasons to Choose NSA
Network Simplex Algorithm
Spanning Tree Solutions and Optimality Conditions
Steps of NSA
Difference between NSA and Original Simplex
Short Literature over Pricing Rules
Strongly Feasible Spanning Tree
Simulation Software
Features of Our Software
Implementation of NSA in Our Software
How the Program Works
Circulation Problem
Experimental Results
Estimate of the Algorithm’s Complexity in Practice
Limitation of the NSA in Practice
Summary and Conclusion

Network Simplex Plus: Complete Advanced Algorithm
Motivation
Network Simplex Plus Algorithm
Anti-Cycling in NSA+
Memory Technique and Heuristic Approach in NSA+
Differences between NSA and NSA+
Comparison between NSA and NSA+
Statistical Test for the Comparison
Complexity of NSA+
Software Architecture for Dynamic Aspect
Experimental Results from the Dynamic Aspect
Summary and Conclusion

Dynamic Network Simplex: Dynamic Complete Advanced Algorithm
Motivation
Classification of Graph Algorithms and Dynamic Flow Model
Dynamic Network Simplex Algorithm
Data Structures
Memory Management
DNSA and DNSA+
Software Architecture for Dynamic Aspect
Comparison between DNSA+ and NSA+
Statistical Test for the Comparison
Complexity of the Algorithm
Summary and Conclusion

Greedy Vehicle Search: An Incomplete Advanced Algorithm
Motivation
Problem Formalization
Nodes and Their Properties in the Incomplete Graph
Arcs and Their Properties in the Incomplete Graph
Special Case of the MCF-AGV Model for AGV Scheduling
Algorithm Formalization
Software Architecture for Dynamic Aspect
Comparison between GVS and NSA+ and Quality of the Solutions
Statistical Test for the Comparison
Complexity of GVS
Complexity of GVS for Static Problems
Complexity of GVS for Dynamic Problems
Discussion over GVS and Meta-Heuristic
Summary and Conclusion

Multi-Load and Heterogeneous Vehicle Scheduling: Hybrid Solutions
Motivation
Assumptions and Formulation
Assumptions
Formulation
Decision Variable
Constraints and Objective Function
Solutions to the Problem
SAM for the Multi-Load AGVs
Hybrid of SAM and NSA for Heterogeneous AGVs
Experimental Results
Summary and Conclusion

Conclusions and Future Research
Summary of This Research Done
Observations and Conclusions
Research Contributions
Future Research
Scheduling and Routing of the Vehicles
Economic and Optimization Model
Other Possible Extension

Appendix: Information on the Web

References
Index