Anticipatory Optimization for Dynamic Decision Making

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

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

این کتاب دو هدف عمده دارد:

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

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

The availability of today’s online information systems rapidly increases the relevance of dynamic decision making within a large number of operational contexts. Whenever a sequence of interdependent decisions occurs, making a single decision raises the need for anticipation of its future impact on the entire decision process. Anticipatory support is needed for a broad variety of dynamic and stochastic decision problems from different operational contexts such as finance, energy management, manufacturing and transportation. Example problems include asset allocation, feed-in of electricity produced by wind power as well as scheduling and routing. All these problems entail a sequence of decisions contributing to an overall goal and taking place in the course of a certain period of time. Each of the decisions is derived by solution of an optimization problem. As a consequence a stochastic and dynamic decision problem resolves into a series of optimization problems to be formulated and solved by anticipation of the remaining decision process.

However, actually solving a dynamic decision problem by means of approximate dynamic programming still is a major scientific challenge. Most of the work done so far is devoted to problems allowing for formulation of the underlying optimization problems as linear programs. Problem domains like scheduling and routing, where linear programming typically does not produce a significant benefit for problem solving, have not been considered so far. Therefore, the industry demand for dynamic scheduling and routing is still predominantly satisfied by purely heuristic approaches to anticipatory decision making. Although this may work well for certain dynamic decision problems, these approaches lack transferability of findings to other, related problems.

This book has serves two major purposes:

‐ It provides a comprehensive and unique view of anticipatory optimization for dynamic decision making. It fully integrates Markov decision processes, dynamic programming, data mining and optimization and introduces a new perspective on approximate dynamic programming. Moreover, the book identifies different degrees of anticipation, enabling an assessment of specific approaches to dynamic decision making.

‐ It shows for the first time how to successfully solve a dynamic vehicle routing problem by approximate dynamic programming. It elaborates on every building block required for this kind of approach to dynamic vehicle routing. Thereby the book has a pioneering character and is intended to provide a footing for the dynamic vehicle routing community.