Online Storage Systems And Transportation Problems With Applications: Optimization Models And Mathematical Solutions

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
You might also like

Heuristic And Optimization For Knowledge Discovery
Authors: Ruhul Sarker , Hussein A. Abbass , Charles Newton    271    0


Introduction To Mathematical Methods In Bioinformatics
Authors: Alexander Isaev    169    0




Effective Computational Geometry For Curves And Surfaces
Authors: Jean-Daniel Boissonnat , Monique Teillaud    165    0


Geometric Curve Evolution And Image Processing
Authors: Frédéric Cao (auth.)    197    0


The Unity Of Mathematics: In Honor Of The Ninetieth Birthday Of I.m. Gelfand
Authors: Michael Atiyah (auth.) , Pavel Etingof , Vladimir Retakh , I. M. Singer (eds.)    241    0


Euclid's Elements
Authors: Fitzpatrick R. (ed.)    264    0


Set Theory (web Draft, 1998-1999)
Authors: Dixon P.    254    0