nach oben

2011 | Buch

Kapitel lesen Erstes Kapitel lesen

Anticipatory Optimization for Dynamic Decision Making

verfasst von: Stephan Meisel

Verlag: Springer New York

Buchreihe : Operations Research/Computer Science Interfaces Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

Economic operations are constantly subject to a large number of influences. Globalization, the progress of information technology as well as increasing resource prices are among the major influences of the past years. They raise both new challenges and opportunities for operations within a company. In addition, they open whole new contexts of economic activity. In particular these influences lead to operations under increasingly dynamic and uncertain conditions. The need for concepts and planning methods enabling the efficient conduction of such operations is a direct consequence. A company must respond to dynamic and uncertain circumstances by anticipation of future events in order to maintain efficiency.

Stephan Meisel

Chapter 2. Basic Concepts and Definitions

Abstract

This chapter defines the concepts representing the fundamental point of reference of anticipatory optimization for dynamic decision making. Section 2.1 summarizes the elements of dynamic decision making. In Sect. 2.2 optimization is defined as the procedure of finding a solution of a single decision problem. Section 2.3 introduces the concept of anticipation and exposes the scope and range of anticipatory optimization.

Stephan Meisel

Chapter 3. Perfect Anticipation

Abstract

A perfect anticipatory decision in the context of dynamic decision making may be achieved by solution of an optimization problem as stated in Eq. 2.8. However, formulation of such an optmization problem requires the availability of the values $V_{t^\prime}(s_{t^\prime})$ of successor states $s_{t^\prime}$. In particular, a value function $V_{t(s_t)}$ must be known for each of the decision times t. Determination of these value functions corresponds to the solution of Bellman’s equations as formulated as Eqs. 2.6.

Stephan Meisel

Chapter 4. Synergies of Optimization and Data Mining

Abstract

Data mining provides the concepts for reducing the negative effects of a vast state space. Both these concepts and optimization are required for the realization of approximate anticipation. In particular approximate anticipation emerges as a synergy of optimization and data mining. However, these two procedures are basically independent of each other. Thus, the present chapter provides the general foundations of the synergies of optimization and data mining, based on which the next Chap. 5 introduces approximate anticipation. A unified view of the optimization and data mining is established in Sect. 4.1. Subsequently the synergies of the two are both identified and illustrated with respect to their contribution to data mining in Sect. 4.2 and with respect to optimization in Sect. 4.3.

Stephan Meisel

Chapter 5. Approximate Anticipation

Abstract

For the vast majority of real-world dynamic decision problems, the value function V required for solution of optimization problems of type

$$P_t=(D_t(s_t),\;c_t(s_t,d_t)+\mathop{E}[V_{t\prime} (s_{t\prime})|s_t])$$

cannot be derived because of the limitations exposed in Sect. 3.4. As a consequence, effective decisions cannot be made deliberately and lowering the degree of anticipation turns out to be the only remedy. However, a lower degree of anticipation trends to result in an increased focus on specific features of the dynamic decision problem at hand. Roughly speaking, the lower the degree of anticipation the less general an optimization approach will be. Only a very small number of methodical paradigms exist that generally represent a subset of lower degree anticipatory optimization. Moreover most of these paradigms so far remain without a significant impact on dynamic decision making.

Stephan Meisel

Chapter 6. Dynamic Vehicle Routing

Abstract

Vehicle routing is one of the major tasks in the context of transportation. The predominant influences currently inducing a change in transportation operations are outlined in Chap. 1. In particular these influences lead to an increased economic relevance of dynamic vehicle routing. A company whose business requires transportation operations may realize substantial cost reductions by considering vehicle routing problems (VRPs) as dynamic decision problems. The resulting problem class is important and elements of this class can be found in a large variety of economic sectors. Consider the routing of vehicles for the delivery of industrial products or for provision of field service for instance. Alternative examples comprise express courier services, the routing of vehicles within container terminals or taxicab services just to name a few.

Stephan Meisel

Chapter 7. Anticipatory Routing of a Service Vehicle

Abstract

The following sections introduce a selection of approaches to anticipatory optimization for dynamic routing of a service vehicle. As proposed in Sects. 2.3.2 and 6.2 the approaches are categorized according to their degree of anticipation. Section 7.1 covers perfect anticipation, which – from a practical point of view – is limited to small problem instances. Nevertheless, the realization of perfect anticipation for such small instances provides valuable insights with respect to approaches featuring lower degrees of anticipation.

Stephan Meisel

Chapter 8. Computational Study

Abstract

This chapter provides insights into the behavior of the different approaches to anticipatory optimization introduced in Sects. 7.2 and 7.3. The insights are derived from computational experiments with a set of diverse instances of the problem of dynamic routing of a service vehicle. Each of these instances is exposed to each of the approaches such that the quality of an approach can be understood with respect to both varying problem characteristics and the qualities of its competitors.

Stephan Meisel

Chapter 9. Managerial Impact of Anticipatory Optimization

Abstract

The previous chapters illustrate the broad scope of anticipatory optimization. As indicated in Chaps. 1 and 2, anticipatory optimization is relevantwith respect to a large variety of operational contexts. Moreover, Chaps. 3 to 5 give an impression of the tremendous methodological spectrum included in the concept. Eventually, Chaps. 6 to 8 exemplify the realization of anticipatory optimization in the context of dynamic vehicle routing. However, this example does not provide a general cookbook for successful application in arbitrary operational contexts.

Stephan Meisel

Chapter 10. Conclusions

Abstract

The preceding chapters cover anticipatory optimization for dynamic decision making. Chapter 1 illustrates the characteristics of the emerging decision problems that raise the need for anticipatory optimization. It exemplifies the influences of globalization, of the progress of information technology and of the increasing resource prices on the operations of many companys. Due to these influences a large number of operations must nowadays be conducted under increasingly dynamic and uncertain conditions. Chapter 1 shows by means of examples from different contexts that such operations may be considered as dynamic decision processes.

Stephan Meisel

Backmatter

Titel: Anticipatory Optimization for Dynamic Decision Making
verfasst von: Stephan Meisel
Verlag: Springer New York
Electronic ISBN: 978-1-4614-0505-4
Print ISBN: 978-1-4614-0504-7
DOI: https://doi.org/10.1007/978-1-4614-0505-4

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Chapter 2. Basic Concepts and Definitions

Chapter 3. Perfect Anticipation

Chapter 4. Synergies of Optimization and Data Mining

Chapter 5. Approximate Anticipation

Chapter 6. Dynamic Vehicle Routing

Chapter 7. Anticipatory Routing of a Service Vehicle

Chapter 8. Computational Study

Chapter 9. Managerial Impact of Anticipatory Optimization

Chapter 10. Conclusions

Backmatter

Premium Partner