Online Storage Systems and Transportation Problems with Applications: Optimization Models and Mathematical Solutions

Front Cover
Springer Science & Business Media, 2005 - Computers - 222 pages

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. It is shown that this logistic problem leads to an NP-hard Batch PreSorting problem which is not easy to solve optimally in offline situations. The author considered a polynomial case and developed an exact algorithm for offline situations. Competitive analysis showed that the proposed online algorithm is 3/2-competitive. Online algorithms with lookahead, improve the online solutions in particular cases. If the capacity constraint on additional storage is neglected the problem has a totally unimodular polyhedron.

The second problem originates in the health sector and leads to a vehicle routing problem. Reasonable solutions for the offline case covering a whole day with a few hundred orders are constructed with a heuristic approach, as well as by simulated annealing. Optimal solutions for typical online instances are computed by an efficient column enumeration approach leading to a set partitioning problem and a set of routing-scheduling subproblems. The latter are solved exactly with a branch-and-bound method which prunes nodes if they are value-dominated by previous found solutions or if they are infeasible with respect to the capacity or temporal constraints. The branch-and-bound method developed is suitable to solve any kind of sequencing-scheduling problem involving accumulative objective functions and constraints, which can be evaluated sequentially. The column enumeration approach the author has developed to solve this hospital problem is of general nature and thus can be embedded into any decision-support system involving assigning, sequencing and scheduling.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

III
xi
IV
1
V
2
VI
3
VII
6
VIII
7
IX
9
X
11
LIV
91
LV
95
LVI
96
LVII
99
LVIII
100
LXI
101
LXII
102
LXIII
105

XI
17
XIII
18
XIV
21
XV
22
XVI
26
XVII
29
XIX
30
XX
31
XXI
33
XXIII
37
XXV
39
XXVI
41
XXIX
42
XXX
44
XXXII
49
XXXIII
50
XXXIV
53
XXXVIII
59
XXXIX
60
XL
63
XLI
65
XLII
66
XLIII
67
XLIV
68
XLV
69
XLVI
75
XLVII
76
XLVIII
78
XLIX
80
L
81
LII
88
LIII
90
LXIV
106
LXV
107
LXVII
108
LXVIII
110
LXIX
111
LXX
112
LXXI
113
LXXII
116
LXXIII
117
LXXVI
121
LXXVIII
122
LXXIX
125
LXXX
130
LXXXI
135
LXXXIII
137
LXXXIV
139
LXXXV
140
LXXXVI
142
LXXXVII
145
LXXXVIII
151
XC
176
XCI
183
XCII
184
XCIII
185
XCIV
186
XCV
187
XCVII
191
XCVIII
196
XCIX
209
C
217
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page viii - Students and graduates in mathematics, physics, operations research, and businesses with interest in modeling and solving real optimization problems
Page ix - Conventions and Abbreviations The following table contains in alphabetic order the abbreviations used in this book. Abbreviation Meaning
Page ix - IP Integer Programming LP Linear Programming MCP Mixed Complementarity Problem MILP Mixed Integer Linear Programming

Bibliographic information