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

این کتاب تجزیه و تحلیل و توسعه الگوریتم‌های آنلاین شامل بهینه‌سازی دقیق و تکنیک‌های اکتشافی و کاربرد آنها برای حل دو مشکل واقعی را پوشش می‌دهد.

اولین مشکل مربوط به یک سیستم فنی پیچیده است: یک سیستم ذخیره سازی پرسرعت مبتنی بر چرخ فلک مخصوص - Rotastore. نشان داده شده است که این مشکل لجستیک منجر به یک مشکل از پیش مرتب سازی دسته ای NP-hard می شود که حل بهینه آن در موقعیت های آفلاین آسان نیست. نویسنده یک مورد چند جمله ای را در نظر گرفت و یک الگوریتم دقیق برای موقعیت های آفلاین ایجاد کرد. تجزیه و تحلیل رقابتی نشان داد که الگوریتم آنلاین پیشنهادی 3/2-رقابتی است. الگوریتم‌های آنلاین با پیش‌بینی، راه‌حل‌های آنلاین را در موارد خاص بهبود می‌بخشند. اگر محدودیت ظرفیت در ذخیره سازی اضافی نادیده گرفته شود، مشکل دارای یک چند وجهی کاملاً تک مدولار است.

مشکل دوم در بخش بهداشت منشأ می گیرد و منجر به مشکل مسیریابی خودرو می شود. راه‌حل‌های معقول برای پرونده آفلاین که یک روز کامل را با چند صد سفارش پوشش می‌دهد با رویکرد اکتشافی و همچنین با بازپخت شبیه‌سازی شده ساخته شده‌اند. راه‌حل‌های بهینه برای نمونه‌های آنلاین معمولی با یک رویکرد شمارش ستونی کارآمد محاسبه می‌شوند که منجر به یک مشکل پارتیشن‌بندی مجموعه‌ای و مجموعه‌ای از مشکلات فرعی مسیریابی-زمان‌بندی می‌شود. دومی دقیقاً با روش شاخه و کران حل می‌شود که گره‌ها را در صورتی که توسط راه‌حل‌های یافت‌شده قبلی تسلط دارند یا اگر با توجه به ظرفیت یا محدودیت‌های زمانی غیرممکن باشند، هرس می‌کند. روش شاخه و کران توسعه‌یافته برای حل هر نوع مسئله توالی-زمان‌بندی که شامل توابع و محدودیت‌های هدف انباشته است، که می‌توانند به‌طور متوالی ارزیابی شوند، مناسب است. رویکرد شمارش ستونی که نویسنده برای حل این مشکل بیمارستان ایجاد کرده است، ماهیت کلی دارد و بنابراین می‌تواند در هر سیستم پشتیبانی تصمیم‌گیری شامل تخصیص، ترتیب‌دهی و زمان‌بندی تعبیه شود.

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.