Resource allocation problems under uncertainty

不确定性下的资源配置问题

• 批准号: RGPIN-2016-04031
• 负责人: Bhattacharya, Binay
• 金额: $ 1.6万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=614794
• 关键词: 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.

现代工业运营的效率要求以最佳方式部署资源。这导致在资源分配的业务研究方面开展了大量工作，重点是最佳或接近最佳的规划。 资源分配决定代价高昂，难以逆转。它们的影响是在很长一段时间内感受到的。在设计阶段使用的参数，如成本、需求和距离，可能会随着时间的推移而变化。几十年来，研究人员一直在开发不确定性下的资源分配模型。鲁棒优化的目标是寻找一个解决方案，将在最坏的情况下，在各种可能的实现参数。随机参数可以是连续的，也可以是离散的。 本课题的主要目的是研究不确定性条件下加权网络中的设施选址问题。我们的建议有两个部分：（a）树形网络中的最小-最大遗憾设施选址问题;（B）道路网络中的带时间窗的取送问题。 树状网络中的设施选址问题在过去已经被广泛研究。还有许多悬而未决的问题有待解决。这一建议为进一步的研究提出了一些方向。一般网络中的PDPTW问题是一个NP难问题。这个问题在真实的世界中仍然非常重要。我们已经为这类问题建立了一个原型软件。该提案还确定了需要加强现有办法的几个领域。 对于一般的网络，我们对如何近似最优解知之甚少。在一般网络中，当参数被假定为确定时，近似选址问题的许多有趣的、重要的结果是已知的。我们将探讨当参数具有区间不确定性时。 精确求解NP-难优化问题的研究十分活跃。整数规划求解器的出现加速了这一进程。我们目前正在研究一般指派问题的模型。我们的目标之一是为解决方法提供结构。