Resource allocation problems under uncertainty

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

• 批准号: RGPIN-2016-04031
• 负责人: Bhattacharya, Binay
• 金额: $ 1.6万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708963
• 关键词: 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-Hard问题。尽管如此，这个问题在现实世界中仍然非常重要。我们已经为这类问题建立了一个原型软件。该提案还确定了需要加强现有办法的几个领域。 对于一般的网络，人们对如何近似最优解知之甚少。对于一般网络中的近似选址问题，在假设参数是确定的情况下，许多有趣而重要的结果是已知的。我们将探索参数何时具有区间不确定性。 精确求解NP-Hard优化问题的研究十分深入。整数规划求解器的出现加速了这一进程。我们目前正在研究一个通用分配问题的模型。我们的目标之一将是为解决方案方法提供结构。