Mar, 2024

随机效用和路由约束下的竞争性设施选址

PDF
TL;DR研究基于竞争市场背景下的设施选址问题，采用随机实用选择模型预测客户需求。引入了路由约束，确保所选择的位置存在一个符合指定上界的旅行访问所有选定位置的路径。通过外估计近似法、子模割平面法和子回路消除法解决非线性目标函数和复杂路由约束问题，并开发了两种精确解法。同时，基于局部搜索的元启发式方法用于解决大规模实例，并与精确方法进行比较，实验证明了我们方法在解决方案质量和计算时间方面的优越性。
facility location problemcompetitive market contextrandom utility choice modelrouting constraintsexact solution methods
发现论文，激发创造
  • 一个用于容量受限位置路径问题的多种群整合方法

    该研究提出了一个多种群综合框架，通过多个仓库配置生成有效的子代解决方案，包括一个有效的基于邻域的局部搜索、一个可行性恢复过程和一个多样化的突变方法，在 281 个基准实例的广泛实验中得到了明显的改进，并匹配了 84 个已知的最佳结果。

    Mar, 2024

  • 具有容量限制的设施选址问题：算法和机制设计角度

    在一维设置中考虑设施位置问题及算法和机制设计的视角。从算法设计的角度出发，证明了相应的优化问题是 NP 难问题，但是在限制设施数量或设施容量完全相同时可以在多项式时间内计算出最优解。从机制设计的角度出发，提出一些新方法提高了策略性，并且获得了接近下限的近似保证。

    Nov, 2019

  • 带逻辑约束的混合整数优化问题的统一方法

    本文研究了一种统一的框架方法用于解决一类混合整数优化问题，通过对其逻辑约束进行非线性方式的表达，结合规则化条件及基于混合精度算法，形成了凸二进制优化问题，并利用一种综合的数字策略方法解决问题。

    Jul, 2019

  • 使用 Rollouts 和 MAX-SAT 解决带时间窗口的有容量车辆路径问题

    本文提出一种混合方法，将强化学习、策略推进和可满足性求解器相结合，以实现计算时间和解决方案质量之间的可调节权衡，该方法可以解决任意规模的问题，且无需额外训练，在解决车辆路由问题中的效果优于现有的基于学习的方法和元启发式算法，更具有泛化性。

    Jun, 2022

  • 通过最优输运实现任意尺寸约束的图割

    通过提出一种基于正则化 Gromov-Wasserstein 问题的加速近端梯度下降算法，我们解决了图切割问题，并实现了稀疏解，相较于经典谱聚类算法，额外的复杂度仅为 O (log (n))，但效率更高。

    Feb, 2024

  • 基于局部搜索的移动设施定位问题的近似算法

    探讨 “移动设施位置” 问题，在公共度量空间中移动设施以减少总体成本，并使用一种基于局部搜索的近似算法，实现任意常数 ε>0 的（3+ε）- 近似度。

    Jan, 2013

  • 圆容量不等式的神经分离算法

    设计了一种基于图嵌入的知识学习方法，将其应用于割平面算法来解决带约束车辆路径问题，与传统求解器相比，一定规模上有更好的上界。

    Jun, 2023

  • 候选位置设施选址博弈机制设计

    机制设计，通过策略证明机制来解决设施选址游戏，最小化代理的总成本和最大成本，并针对单设施问题和两设施问题分别证明了逼近度的下界和逼近算法。

    Oct, 2020

  • 具有战略客户和设施的两阶段设施选址博弈

    本论文研究了非合作设施定位博弈，其中设施和客户都是策略性的，并且对彼此产生重大影响。在这种情况下，研究者提出了一种以自私的客户为中心的自然客户行为的博弈模型，证明了其次博弈纳什均衡存在，同时简要介绍了社会最佳设施放置的计算难度和其与客户行为的相关性。

    May, 2021

  • 投票和设施选址的多目标优化

    我们研究了在任意度量空间中，给定 $n$ 个客户和 $m$ 个可能的设施位置的传统设施位置设置，以及想要选择一个位置来建造设施的问题，提出了同时优化多个目标的 $l$-centrum 目标族，并给出了这些目标的紧密边界和近似因子。

    Dec, 2022