E-Book Overview
This books covers the analysis and development of online algorithms involving exact optimization and heuristic techniques, and their application to solve two real life problems. The first problem is concerned with a complex technical system: a special carousel based high-speed storage system - Rotastore. The second problem originates in the health sector and leads to a vehicle routing problem.
E-Book Content
Online Storage Systems and Transportation Problems with Applications
Applied Optimization Volume 91 Series Editors: Panos M. Pardalos University of Florida, U.S.A. Donald W. Hearn University of Florida, U.S.A.
Online Storage Systems and Transportation Problems with Applications Optimization Models and Mathematical Solutions
by
Julia Kallrath ITWM, Germany
Springer
eBook ISBN: Print ISBN:
0-387-23485-3 1-4020-2971-3
©2005 Springer Science + Business Media, Inc. Print ©2005 Springer Science + Business Media, Inc. Boston All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://ebooks.springerlink.com http://www.springeronline.com
to my parents
This page intentionally left blank
Contents
Dedication Preface 1. INTRODUCTION 1.1 Optimization Everywhere 2. BATCH PRESORTING PROBLEMS. I 2.1 Problem Description and Classification
v xi 1 1 5
2.2
Formulation of the Batch Presorting Problem 2.2.1 Feasible Permutations 2.2.2 Mathematical Formulation of and 2.2.3 Mathematical Formulation of 2.2.3.1 An Optimization Version of 2.2.3.2 An Optimization Version of
5 6 7 8 10 11 13
2.3
Complexity Results
15
2.4
Polynomial Subcases 2.4.1 Reformulation of and 2.4.2 An Alternative Model Formulation of
21 21 22
2.5
The Case of Two Layers 2.5.1 Offline Situations 2.5.2 Online Situations 2.5.3 Algorithms for Online Situations with Lookahead 2.5.3.1 Definition of a Lookahead 2.5.3.2 An Algorithm with a Weak Lookahead, size 2.5.3.3 Algorithms with a Weak Lookahead, size 2.5.3.4 An Algorithm with a Strong Lookahead 2.5.4 Competitive Analysis
25 26 30 33 33 34 35 37 37
viii
Online Storage Systems and Transportation Problems Comparison of and Online Algorithms with Lookahead Extensions Summary und Future Research
2.5.5
2.6 2.7
3. BATCH PRESORTING PROBLEMS. II 3.1 The Storage System Rotastore 3.1.1 A Brief Description of the Rotastore 3.1.2 Stochastic Measures 3.2 Numerical Tests 3.2.1 Models 3.2.2 Algorithms 3.3 Summary 4.VEHICLE ROUTING PROBLEMS IN HOSPITALS. I 4.1 Problem Formulation and Solution Outline 4.1.1 Problem Description 4.1.2 Discussion of one Particular Model Formulation 4.1.3 Discussion of Existing Solution Approaches 4.1.4 Outline of Proposed Methods 4.2 General Framework 4.2.1 Notation 4.2.2 Characterizing the Quality of Tours 4.3 Exact Solution Approaches 4.3.1 A Mixed Integer Programming Approach 4.3.1.1 Data, Indices and Variables 4.3.1.2 The Objective Function 4.3.1.3 The Constraints 4.3.1.4 Equivalent Mixed Integer Linear Formulations 4.3.1.5 Online Version of the MILP Model 4.3.1.6 Comments on the Size and the Structure of the MILP Problem 4.3.1.7 Tightening the Model Formulation 4.3.1.8 Concluding Remarks on the Model 4.3.2 A Branch-and-Bound Approach for Solving the Intra-Tour Problem 4.3.3 Column Enumeration 4.3.3.1 Motivating a Column Enumeration Approach 4.3.3.2 Comments on Column Generation Techniques
41 41 43 45 45 45 46 48 48 53 54 57 57 57 60 63 64 67 67 69 70 70 71 72 73 79 80 82 8