Resource allocation problems under uncertainty

点击翻译按钮获取中文摘要

Efficiency in modern industrial operations requires that resources be deployed in an optimal manner. This has resulted in extensive work in operations research on resource allocation with a focus on optimal or near-optimal planning. Resource allocation decisions are very costly and difficult to reverse. Their impact is felt over a long period of time. The parameters, such as cost, demand, and distance, used during the design phase may change over the time period. Researchers have been developing models for resource allocation under uncertainty for decades. The goal of robust optimization is to look for a solution that will work well in the worst case under various possible realizations of the parameters. The random parameters can be either continuous or described by discrete scenarios. The main objective of our project is to study the problem locating facilities in weighted networks under uncertainty. Our proposal has two parts: (a) min-max regret facility location problems in a tree-like networks, (b) pickup and delivery problem with time window (PDPTW) in road networks. Facility location problems in tree-like networks have been studied extensively in the past. There are many open problems still to be solved. This proposal suggests a few directions for further studies. PDPTW in general networks is an NP-hard problem. Still this problem is very important in real world. We have built a prototype software for this class of problems. This proposal also identifies a few areas where the enhancing of the existing approaches are needed. For general networks, very little is known about how to approximate the optimal solution. Many interesting, important results on approximating location problems in general networks are known when the parameters are assumed to be certain. We will explore when the parameters have interval uncertainty. The research on exactly solving NP-hard optimization problems is intense. The advent of integer programming solver has hastened this progress. We are currently working on a model for general assignment problems. One of our objectives would be to provide structure to the solution approach.