论文解读 陈迎新，柯斯琪，曲晨辉，张景琪
编者按
本次解读的文章是 Transportation Science 2017年的 《在日益增长的市场中，动态设施选址问题的连续逼近方法》（Wang, X., Lim, M. K., & Ouyang, Y. (2017). A continuum approximation approach to the dynamic facility location problem in a growing market. Transportation Science, 51(1), 343-357.）
原文 摘要 总结如下：
本文所需要解决的问题是在大规模增长市场的情况下，如何确定最佳的设施位置和部署时间，以便在规划范围内尽量减少设施建设和客户服务的成本。
为了克服计算上的挑战，本文采用了连续逼近（continuum approximation, CA）模型来解决大规模增长市场的动态设施选址问题，通过CA模型确定了时空连续体中的最佳设施密度。其次，本文提出了管子模型（Tube model），将得到的连续设施密度函数离散为一组时变的设施位置轨迹。再者，为了保证设施位置的一致性，本文采用了一种基于惩罚方法的迭代调节程序（iterative regulation procedure）。同时，文章也证明了上述方法的收敛性，并进一步推导了CA方法和管子模型产生紧密的近似误差界的条件。最后，文章也进行了一系列的数值实验来说明所提出的建模框架的适用性和计算性能（例如，准确性和收敛性），具体而言是通过与使用假设数据的离散模型进行比较，然后应用于伊利诺伊州的经验案例。
1. 写在前面
静态设施选址 vs 动态设施选址
设施选址决策对商业实践中的许多问题至关重要，一般而言决策者（如政府或公司）需要找到一组设施（如消防站或当地分支机构）的空间分布，以尽量减少满足各种需求的总成本（如设施和运输成本）。设施选址决策通常意味着对大量资源的长期承诺，即一旦做出了决定（设施已经开放），决策很难轻易被逆转。
即使不考虑设施位置决策的长期性影响，大量的研究因计算上的挑战仍集中在静态设施位置问题上（其中参数随时间是恒定的）。然而，在现实中，系统的任何参数（例如，客户需求、运营成本）都可能会随着时间的推移而变化，而设施的增加可能会在不同的时间发生。也就是说，“在哪里”和“在何时”均为建设设施的关键决定。
在本文中，学者探讨了一类动态的设施布局规划问题，其中一个中央规划者试图确定设施布局的最佳位置和时间，以尽量减少在各规划阶段的累积物流成本。特别是，文章考虑了一个需求不断增长的市场环境（而单位运营成本可能会降低），故新的设施会随着时间的推移不断开放或增加。本文的研究目的是提供一种适合大规模实例的动态设施布局规划的有效解决方法。
CA模型不能直接应用于动态问题
尽管CA已被广泛用于解决静态设施位置问题，但为处理这些问题的动态版本所做的工作相对较少。机器人社区已经做了一些相关的尝试；例如，
- Ny和Pappas（2010）提出了一种自适应算法来解决动态车辆路径问题，给定随机即将到来的客户位置的概率分布。
- Cambell（1990）注意到CA背后的主要思想是定位空间决策，他将CA扩展到动态设置下设计运输终端，但假设终端位置是“移动的”，可以在每次瞬间独立移动。
然而，在现实中，开放设施的位置在规划范围的其余部分通常保持不变。我们将其称为位置一致性约束。由于这种限制，设施部署决策会对剩余的规划范围产生持续的影响，并且不能通过时间邻域中的局部参数来确定。此外，即使使用CA获得了DFLP的解决方案，仍然需要一种转换方法来有效地将CA解决方案在时间和空间上转换为离散的设施位置。上述的磁盘模型（Ouyang和Daganzo 2006）是为静态问题而设计的，因此不能直接应用于动态问题。
2. 模型构建
2.1 连续逼近
首先，我们对DFLP离散模型进行连续逼近。假设：
2.2 管子模型
为了便于记述，我们将
这个迭代过程重复进行，直到找到一个不重叠的磁盘的平衡分布，如下图1(b)所示。
当我们将时间维度结合到磁盘模型中的时候，我们就得到了管子模型，如下图2(a)所示。假设：
但是，因为我们对DFLP离散模型进行连续逼近的时候对位置一致约束（location consistency constraint）进行了松弛，于是我们可能得到一个有弧度的管子，如图3(b)所示。考虑现实情况，一个已经开放的设施位置一般是保持不变的，我们期望得到的是一个中心位置不移动的管子，如图3(a)所示。于是，我们提出了管子模型的迭代调节算法(Iterative Tube Regulation Algorithm)。
2.3 管子模型的迭代调节算法
本文采取的方法是：允许设施的位置随时间变化，并通过在目标中施加惩罚项来强制执行约束条件。 因而，我们可以将Tube Regulation Problem建模为：
提出的DFLP算法小结
步骤1：DFLP到CA
- 松弛位置一致约束，将DFLP按时间点分解为无穷个独立的静态问题；
- 通过CA重构并求解所有静态问题，获得基于时空间的最优设施密度；
- 利用最优设施密度函数确定:（i）最优设施数量；（ii）设施开放时间。
步骤2：CA到level-Based DFLP
- 离散化时间区间，利用管子模型求解每个时间间隔的设施选址问题；
- 利用圆柱体近似设施服务区域，获得一系列倾斜的管子，给出本问题的松弛解。
步骤3：level-Based DFLP到DFLP
- 加入位置一致约束对管子的倾斜进行惩罚，将步骤2.2中的松弛解作为初始解；
- 更新管子的位置直到倾斜度进入可接受范围。
3. 近似误差界
本段介绍了如何评估解决方案的近似误差，并探讨了最优动态设施选址问题的上限和近似的下限。
在使用本文提出的方法时，会得到两个解：
- 来自第2.1节通过连续近似模型得到的CA解，该解不一定是可行解；
- 来自第2.3节的通过管子模型转换后得到的可行离散解。其中，可行离散解的目标值提供了原始DFLP的上限，而CA解的目标值则给出了一类离散解的下限（在某些条件成立时）。
我们可以通过一个DFLP例子来分析其最终解的上限和下限 （类似的分析和证明可以应用在其他DFLP上），以下述DFLP问题为例：
4. 数值实验
论文使用数字算例进行了实验，希望说明CA框架的实用性，探索异质性的影响。此外，论文将提出的方法应用于伊利诺伊州的一个案例研究，以突出其对现实世界问题的适用性。
4.1 举例说明
最佳设备部署时间n(x,t)是通过连续体近似法得到的，如下图(a)所示。
下面说明管子模型是如何实现的。
图6(a)-6(d)展示了管子调节程序的一些快照。为了清楚地说明问题，管子的每个圆柱体都简单地表示在一个平面上，同一管子的圆柱体通过线条连接。
4.2 异质性的敏感性实验
为说明异质性的影响，我们解决了一系列的DFLPs，每个异质性参数从0增加到0.5，其他参数固定为0。下图显示了每一类异质性的总成本的相对差异。由于我们的CA方法对DFLP的求解不一定唯一，因此对每个实例求解五次，并画出平均值。结果显示，总成本随着空间异质性的增加而减少，需求密度的异质性影响最明显。相比之下，我们发现总成本随着时间异质性的增加而上升。由于需求密度变化较快，设施运营或开放的成本随着时间的推移下降较快，保持低成本变得更加有挑战性。
4.3 伊利诺伊州案例研究
在本小节中，我们对伊利诺伊州实施所提出的解决方法，并说明其对现实环境的适用性。
图9(a)-9(c)分别说明了需求变化的时间和空间异质性的影响。
最后，我们评估了成本参数和需求增长率是如何影响最优设计的。结果统计见表2。
5. 总结
本文提出了一个用于解决动态设施位置问题的连续近似框架。首先通过增加时间维度来扩展静态连续设施位置问题。虽然这种转换产生的解决方案没有保持设施位置在时间上的一致性，但它提供了一个可分析的解。随后，我们提出了管子模型，一个圆盘模型的扩展，将CA解决方案转换成离散的设施位置。设施位置的一致性是通过一个迭代的管子调节程序来实现的，即通过一个惩罚方法，其中收敛的解决方案产生了DFLP的近似解决方案。通过一系列的数值例子，我们展示了空间和时间异质性的影响，并比较了CA模型和离散对应模型的性能。我们还将该方法应用于伊利诺伊州的一个经验性案例研究，以探索其在更现实的环境中的适用性。
最后，我们指出，当一组设施在规划期开始时可能已经建成时，可以应用所提出的模型。对于这种情况，可以简单地固定这些位置变量的值。在管子调节程序中，不更新相应管子的中心。这一扩展在设施选址方面提供了很大的实用价值。例如，在系统不确定性程度高或规划范围长的情况下，我们的模型可以在滚动范围内实施。在每个预测周期重新定义（修改）DFLP，以应用所提出的算法，并在不久的将来实施解决方案。然后，到该点开放的设施集成为新问题的固定初始条件，这又可以用上面讨论的程序来处理。
这项研究可以在几个方面进行扩展：（1）研究已开放的设施可以关闭的可能性（市场不一定持续增长）。（2）考虑开放设施可能因为自然或人为的危害而被破坏的情况。