Operations Research
0030-364X
1526-5463
Mỹ
Cơ quản chủ quản: INFORMS , INFORMS Institute for Operations Research and the Management Sciences
Lĩnh vực:
Management Science and Operations ResearchComputer Science Applications
Các bài báo tiêu biểu
The Price of Robustness A robust approach to solving linear optimization problems with uncertain data was proposed in the early 1970s and has recently been extensively studied and extended. Under this approach, we are willing to accept a suboptimal solution for the nominal values of the data in order to ensure that the solution remains feasible and near optimal when the data changes. A concern with such an approach is that it might be too conservative. In this paper, we propose an approach that attempts to make this trade-off more attractive; that is, we investigate ways to decrease what we call the price of robustness. In particular, we flexibly adjust the level of conservatism of the robust solutions in terms of probabilistic bounds of constraint violations. An attractive aspect of our method is that the new robust formulation is also a linear optimization problem. Thus we naturally extend our methods to discrete optimization problems in a tractable way. We report numerical results for a portfolio optimization problem, a knapsack problem, and a problem from the Net Lib library.
Tập 52 Số 1 - Trang 35-53 - 2004
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Tập 35 Số 2 - Trang 254-265 - 1987
An Effective Heuristic Algorithm for the Traveling-Salesman Problem This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, “classical” problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n2 ; in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE635), and about three minutes to obtain the optimum with above 95 per cent confidence.
Tập 21 Số 2 - Trang 498-516 - 1973
Shock Waves on the Highway A simple theory of traffic flow is developed by replacing individual vehicles with a continuous “fluid” density and applying an empirical relation between speed and density. Characteristic features of the resulting theory are a simple “graph-shearing” process for following the development of traffic waves in time and the frequent appearance of shock waves. The effect of a traffic signal on traffic streams is studied and found to exhibit a threshold effect wherein the disturbances are minor for light traffic but suddenly build to large values when a critical density is exceeded.
Tập 4 Số 1 - Trang 42-51 - 1956
Regret in Decision Making under Uncertainty Evidence exists that people do not always make decisions involving uncertain monetary rewards as if they were maximizing expected utility of final assets. Explanations for this behavior postulate that the cognitive demands of consistency to such a theory are too great. However, situations exist in which more than mental shortcuts are involved and these anomalies raise questions about expected utility theory as a guide to behavior. This paper explores the possibility that expected utility theory appears to fail because the single outcome descriptor—money—is not sufficient. After making a decision under uncertainty, a person may discover, on learning the relevant outcomes, that another alternative would have been preferable. This knowledge may impart a sense of loss, or regret. The decision maker who is prepared to tradeoff financial return in order to avoid regret will exhibit some of the behavioral paradoxes of decision theory. By explicitly incorporating regret, expected utility theory not only becomes a better descriptive predictor but also may become a more convincing guide for prescribing behavior to decision makers.
Tập 30 Số 5 - Trang 961-981 - 1982
A Proof for the Queuing Formula: <i>L</i> = λ<i>W</i> In a queuing process, let 1/λ be the mean time between the arrivals of two consecutive units, L be the mean number of units in the system, and W be the mean time spent by a unit in the system. It is shown that, if the three means are finite and the corresponding stochastic processes strictly stationary, and, if the arrival process is metrically transitive with nonzero mean, then L = λW.
Tập 9 Số 3 - Trang 383-387 - 1961
The Location of Emergency Service Facilities This paper views the location of emergency facilities as a set covering problem with equal costs in the objective. The sets are composed of the potential facility points within a specified time or distance of each demand point. One constraint is written for each demand point requiring “cover,” and linear programming is applied to solve the covering problem, a single-cut constraint being added as necessary to resolve fractional solutions.
Tập 19 Số 6 - Trang 1363-1373 - 1971
Pricing and the Newsvendor Problem: A Review with Extensions In the newsvendor problem, a decision maker facing random demand for a perishable product decides how much of it to stock for a single selling period. This simple problem with its intuitively appealing solution is a crucial building block of stochastic inventory theory, which comprises a vast literature focusing on operational efficiency. Typically in this literature, market parameters such as demand and selling price are exogenous. However, incorporating these factors into the model can provide an excellent vehicle for examining how operational problems interact with marketing issues to influence decision making at the firm level. In this paper we examine an extension of the newsvendor problem in which stocking quantity and selling price are set simultaneously. We provide a comprehensive review that synthesizes existing results for the single period problem and develop additional results to enrich the existing knowledge base. We also review and develop insight into a dynamic inventory extension of this problem, and motivate the applicability of such models.
Tập 47 Số 2 - Trang 183-194 - 1999
Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems Stochastic programming can effectively describe many decision-making problems in uncertain environments. Unfortunately, such programs are often computationally demanding to solve. In addition, their solution can be misleading when there is ambiguity in the choice of a distribution for the random parameters. In this paper, we propose a model that describes uncertainty in both the distribution form (discrete, Gaussian, exponential, etc.) and moments (mean and covariance matrix). We demonstrate that for a wide range of cost functions the associated distributionally robust (or min-max) stochastic program can be solved efficiently. Furthermore, by deriving a new confidence region for the mean and the covariance matrix of a random vector, we provide probabilistic arguments for using our model in problems that rely heavily on historical data. These arguments are confirmed in a practical example of portfolio selection, where our framework leads to better-performing policies on the “true” distribution underlying the daily returns of financial assets.
Tập 58 Số 3 - Trang 595-612 - 2010
The Optimal Control of Partially Observable Markov Processes over a Finite Horizon This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem.
Tập 21 Số 5 - Trang 1071-1088 - 1973