Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, Second Edition, 2nd Edition (Hardback) book cover

Vehicle Scheduling in Port Automation

Advanced Algorithms for Minimum Cost Flow Problems, Second Edition, 2nd Edition

By Hassan Rashidi, Edward Tsang

CRC Press

259 pages | 62 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781498732536
pub: 2015-08-14
SAVE ~$29.00
$145.00
$116.00
x
eBook (VitalSource) : 9780429183898
pub: 2015-08-14
from $72.50


FREE Standard Shipping!

Description

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.

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

About the Authors

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.

Subject Categories

BISAC Subject Codes/Headings:
BUS076000
BUSINESS & ECONOMICS / Purchasing & Buying
BUS087000
BUSINESS & ECONOMICS / Production & Operations Management
COM051240
COMPUTERS / Software Development & Engineering / Systems Analysis & Design