Online storage systems and transportation problems with applications. Optimization models and mathematical solutions. (Q1886094)

The book contains two well-performed case studies, which include thorough analysis of complexity, modelling of problems, design and implementation of solving algorithms and their verification, testing and comparison. The first of the studied problems denoted as ``Batch Pre-sorting Problem'' concerns task of input sequence reordering so that the efficiency of a following processor is maximal. In this case study, the processor is represented by a special carousel based high-speed storage system Rotastore, which completes sets of objects accordingly to given orders. An order is completed from objects of different types, which are located at several layers of the storage system. If the objects of one type are uniformly distributed over the layers, then the system needs minimal number of cycles to complete the order. The system is equipped with a facility, which enables limited sorting performed on a flow of the objects entering the storage system. On the background of this real-live problem, the combinatorial Batch Pre-sorting Problem was established, the objective of which is to find a finite sequence of objects of different types that guarantees an optimal assignment of objects to given physical storage layers taking into consideration limited capacity of the associated pre-sorting facility. For this problem, three mathematical models with different objective functions were derived. The author proves that the problem is NP-complete in general, but some special cases are solvable to optimality in polynomial time. An optimal algorithm has been developed for this special problem formulated for offline control, when the whole input sequence of objects is known in advance. The algorithm has been enhanced for cases of online control and its performance was tested for situations, in which only a part of the input sequence is known. There were compared cases with and without restricted look ahead. At the end of this part of the book a competitive analysis is performed to estimate online algorithm behaviour. The second case study concerns a vehicle routing problem, which emerges mostly in online form in health sector. This problem distinguishes from the other vehicle routing problems by two types of operations made to satisfy customer's demand for transport. These operations are picking up and dropping off. The further differences consist in time windows, in which a particular operation must be performed and in objective function, which has rather a min-max form than an additional one. To solve this complex problem, several exact approaches were suggested and tested. It was found that mixed integer linear programming and column generation approaches can solve only small instances of the offline problem to optimality, but when used together with heuristics, the computational time of the optimization process can be considerably reduced. This reduction of solving time enabled utilizing of these methods for solving of online problems, in which some orders are pre-assigned and where the set of new known orders is much smaller than a set of orders in an offline problem. To construct a proper decision support tool, the set of exact methods for sub-problem solving was enlarged by construction and improvement heuristics and, in addition, the principle of simulated annealing was embedded into the process. Real-world instances of the problems in offline and online form were used to verify and compare the individual algorithms and their combinations. The associated results are reported in the appendices to complete these studies.