论文标题
基于马尔可夫链的多阶段随机整数线性编程的政策，并应用救灾后勤
Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics
论文作者
论文摘要
我们介绍了一个聚合框架，以解决具有混合构成状态变量和连续局部变量（MSILPS）的多阶段随机程序。我们的聚合框架通过利用基础随机过程的信息来施加其他结构，该结构被建模为马尔可夫链（MC）。我们证明，可以通过与随机双动力学变体集成的分支和切割算法准确求解聚合的MSILP。为了提高障碍性，我们建议使用这种方法获得双重界限。此外，我们采用两阶段线性决策规则（2SLDR）近似，特别是我们建议的新的基于MC的变体，以大大减少计算工作，以获得高质量的决策策略。我们在MSILP模型中测试了飓风救灾物流规划的方法。我们的经验评估比较了各种提出的方法的有效性，并分析了政策灵活性，解决方案质量和计算工作之间的权衡。具体而言，2SLDR近似为我们的测试实例提供了可证明的高质量解决方案，并由拟议的边界程序支持。我们还从基础决策政策所表现出的解决方案行为中提取了有价值的管理见解。
We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be solved exactly via a branch-and-cut algorithm integrated with a variant of stochastic dual dynamic programming. To improve tractability, we propose to use this approach to obtain dual bounds. Moreover, we apply two-stage linear decision rule (2SLDR) approximations, in particular a new MC-based variant that we propose, to obtain high-quality decision policies with significantly reduced computational effort. We test the proposed methodologies in an MSILP model for hurricane disaster relief logistics planning. Our empirical evaluation compares the effectiveness of the various proposed approaches and analyzes the trade-offs between policy flexibility, solution quality, and computational effort. Specifically, the 2SLDR approximation yields provable high-quality solutions for our test instances supported by the proposed bounding procedure. We also extract valuable managerial insights from the solution behaviors exhibited by the underlying decision policies.
