| 基于鲁棒优化的新增设施选址策略研究 |
| Conditional location problem based on robust optimization |
| 摘要点击 209 全文点击 0 投稿时间：2020-07-11 修订日期：2021-06-08 |
| 查看/发表评论 下载PDF阅读器 |
| 中文关键词 新增设施选址；最大负荷量；最小最大后悔值；算法设计与分析 |
| 英文关键词 conditional location; maximum load; minmax regret; algorithm design and analysis |
| 基金项目 中国博士后科学基金 |
| 作者 | 单位 | 邮编 | | 罗太波 | 西安电子科技大学 | 710126 | | 赵阳 | 西安电子科技大学 | | | 于江霞* | 西安电子科技大学 | 710126 | | 李红梅 | 西北大学 | |
|
| 中文摘要 |
| 在需求无概率分布的条件下, 将区间数据作为需求上下界, 以所有设施中最大负荷量最小化为目标, 基于鲁棒优化方法, 采用最小最大后悔准则, 在就近服务假设下建立新增设施选址优化模型. 基于最坏情景分析, 证明了最坏情景具有特殊的结构特征, 设计了使最大负荷量的最大后悔值最小的求解算法. 研究结果克服了求解时间复杂度会随需求点数量的增加而呈指数增长的缺点, 把已有的时间复杂度为指数的求解算法改进到多项式时间求解. 算例分析结果进一步表明本文算法更适合大规模网络上的新增设施选址问题. |
| 英文摘要 |
| This paper establishes a robust optimization model for conditional location problem without demand probability distribution. The demand of each vertex is an interval value, which represents the lower bound and the upper bound of the demand. All demand is supposed to get service at the nearest facility. The goal is to minimize the maximum load of all facilities. The minmax regret principle is applied to deal with the demand uncertainty. Based on the worst case analysis, this paper proved the weight structure of the worst scenarios, and then proposed a minmax regret algorithm. The result extends the existing algorithm with exponential time complexity to polynomial algorithm, and thus overcomes the disadvantage that the time complexity grows exponentially with the number of demand vertex. Numerical results show that the new algorithm is more efficient for the conditional location problem in large-scale network. |
| 关闭 |
