含时间约束的配送中心选址和能力规划的鲁棒优化

韦忆立，高咏玲

（中央财经大学 商学院，北京 100081）

0 引言

配送中心是企业物流网络中的重要节点，其选址问题是物流系统中具有战略意义的投资决策问题。配送中心需要耗费较长的时间建设，期间决策环境的快速变化或是历史数据的缺乏等因素往往导致参数发生扰动。这种扰动将使传统的确定环境下的最优解变成次优解或不可行。针对这一情况，学者们如Kouvelis等（1992）和Mulvey等（1995）提出了战略决策层次的鲁棒优化模型，它因能保证最优解对于噪声数据或是不完全的数据具有一定的免疫能力而备受关注。

鲁棒优化模型主要包括绝对鲁棒优化、相对鲁棒优化和偏差鲁棒优化等，采用的决策准则有最小化最大值、设定偏差范围等。遗憾值模型是相对鲁棒优化的一种，它通过限定各情景下目标函数值与最优目标函数值的偏差范围来保证最优解的稳健性，在设施选址领域应用最广。在现实中，企业配送网络的优化不仅需要考虑新建配送中心的情况，还需权衡对现有配送中心的能力调整。在这一领域，Elson（1972）建立了确定性需求环境下的混合整数规划模型，用于分析新建、扩建和关闭设施的优化问题，Aghezzaf（2005）建立了随机期望规划模型，研究了需求不确定环境下仓库选址和能力规划的问题，然而随机规划难以保证在所有可能的参数扰动下尤其是最坏情况下优化结果带来的效益都是可接受的。

近年来，我国土地价格的变化、原材料与劳动力成本的增加使得配送中心投资成本的不确定性增强。与此同时，市场竞争的日趋激烈和消费者需求的日益个性化，不仅增加了精确预测配送中心客户需求的难度，而且对于配送商品的时效性提出了更高的要求。例如电子商务、冷链物流、食品和药品等企业在进行选址决策时，不仅需要考虑投资成本和需求不确定性的影响，还要考虑配送时间的要求。在此背景下，本文对不确定环境下配送中心的位置、数量和规模决策问题进行研究，旨在降低物流网络的运行成本、有效地响应客户需求。

1 问题描述和模型的构建

本文采用情景分析法来描述不确定因素，分别用已知概率的情景集合S和S′来描述顾客需求和投资成本的不确定性，情景发生的概率分别用 ps和Ps′表示。

模型采用的假设如下：

（1）配送中心的运营会带来固定的运营成本，其取值与配送中心的规模无关。配送中心的可变运营成本与其处理的产品数量呈正比。

（2）两点间的单位运输成本和运输时间在各个情景下保持不变。

（3）配送中心规模代表着其处理能力。无论是扩建现有配送中心，还是新建配送中心，都设定了最小的扩建规模，一旦决定扩建，至少要达到该规模，以保证规模经济效应。可以在最小扩建规模的基础上进行额外扩建，额外扩建成本与扩建规模成正比例关系，但总建设规模有上限。

（4）仅考虑产品的在途运输时间，不考虑产品在配送中心的滞留和处理时间。

（5）供求平衡或供大于求，所有的客户需求都能在一定成本下满足。

1.1 参数与变量定义

1.1.1 标号与集合

i工厂的标号，i∈M.

j配送中心的标号，j∈N ；N=N′∪N″.

N′是原有配送中心的集合，N″是待建配送中心的集合。

k需求地的标号，k∈Q.

s′投资情景的标号，s′∈S′.

s需求情景的标号，s∈S.

1.1.2 主要参数

CSij产品从工厂i到配送中心 j的单位运费，i∈M ，j∈N.

CDjk产品从配送中心 j到需求地k的单位运费，j∈N ，k∈Q.

TSij产品从工厂i到配送中心 j的运输时间，i∈M ，j∈N.

TDjk产品从配送中心 j到需求地k的运输时间，j∈N ，k∈Q.

Tk需求地k对配送时间的限制，k∈Q.

CFj配送中心 j的固定运营成本，j∈N.

CVj配送中心 j的单位可变运营成本，j∈N.

R0相对遗憾限定系数（以下简称：遗憾系数），是对实际总成本超过最低总成本的百分比的限制。

1.1.3 决策变量

（1）选址与能力规划决策变量

1.2 约束条件

1.2.1 能力约束和选址约束

流入或流出配送中心的产品总量必须小于或等于其扩建或关闭后的最终处理能力。

1.2.2 流量约束

1.2.3 配送时间约束

在构造时间约束时，可要求任一“生产地—配送中心—需求地”组合的总运输时间均满足配送时间约束。这种处理方法在构建新的配送网络时能够较好地满足时效性的要求，但在本文考虑对现有配送中心的调整的条件下会使求解的总成本急剧增加，而且在决策之前难以保证存在满足时间要求的可行解。文献[5]研究单源、p个中转点的配送系统，用一个0-1变量考虑了从中转点到需求地的时间约束，本文在此基础上引入两个0-1变量，分别表示是否选择某一“工厂—配送中心”或“配送中心—需求地”供应组合。这两个组合的总配送时间应满足需求地的配送时间要求，关系如下：

1.3 目标函数

1.4 鲁棒优化模型

1.5 算法设计

本文所建立的模型求解步骤如下：

（4）求解鲁棒优化模型Mr。与单个投资情景下的模型Ms相比，模型Mr增加了相对遗憾值约束，其中遗憾系数R0应大于R0LB，否则模型Mr无可行解。

本文所建立的鲁棒优化模型可运用优化软件Lingo求解。

2 算例分析

本文的数值计算实验将围绕以下三个方面展开：（1）分析遗憾系数对鲁棒优化模型解的影响；（2）分析时间约束对投资决策和成本的影响；（3）测试优化软件Lingo求解模型的效率。

已知某企业只生产一种产品，目前设有3个大型工厂，经过配送中心中转，向5个需求地供应产品。该企业已有3个配送中心，还将在7个备选地选择若干地建设新的配送中心。配送中心的投资成本分为下降、正常和上涨三种情况。顾客需求分为萧条、正常、繁荣三种情况。需求数据和投资成本数据如表1和表2所示。

表1 各需求情景下的需求 （单位：万元）

配送中心的处理能力和运营成本数据如表3所示，单位运费和运输时间数据如表4和表5所示。

2.1 遗憾系数对鲁棒解的影响

最优总成本R*和最大相对遗憾值ξ*随R0的变化情况如图1所示。R0较小时，ξ*较小而R*较大；随着R0的增大，R*迅速降低，但ξ*也迅速上升，这表明中长期决策后最坏情况发生带来的损失较大。R0增大到一定程度后，相对遗憾值约束成为冗余，最优总成本保持不变，其值等于一般随机优化中的最优目标函数值。由此可见，遗憾系数取较小值时，模型的鲁棒性较好，不确定情况下实际总成本对最优总成本的最大偏离程度不会太大，但是为了保持这一性能需要支付更高的成本。

表2 各投资情景下的投资成本

表3 配送中心的处理能力和运营成本 （单位：万件）

表4 单位运费 （单位：元/件）

表5 运输时间 （单位：小时）

综上所述，遗憾系数R0控制了鲁棒模型的鲁棒性，较小的R0可保持较高的鲁棒性，但需要付出较高的成本，决策时要根据需要进行权衡，选择合适的遗憾系数，使模型的鲁棒性能和总成本都在可接受的范围内。

图1 最优总成本和最大相对遗憾值随遗憾系数的变化情况

2.2 时间约束对投资决策和成本的影响

为检验时间约束对于求解结果的影响，分析在无时间约束、宽松的时间约束、严格的时间约束三种情况下投资决策和最优成本的变化。各个需求点对配送时间的要求如表6所示。

表6 配送时间要求 （单位：小时）

表7显示了三种类型的时间约束对应的选址和能力规划决策以及各部分成本的情况。在无时间约束和宽松的时间约束下选址和能力规划的决策结果相同，投资成本相同。但加入时间约束后，舍弃了不能满足配送时间要求的路线，取而代之的是成本更高的路线，导致运输成本有所提高，从而总成本提高。

当采用严格的时间约束时，与无时间约束和宽松的时间约束的求解结果相比，选址和能力规划的决策结果发生了改变，投资成本、配送中心运营成本以及运输成本都有所增加，导致总成本进一步提高。

表7 时间约束对投资决策和成本的影响 （单位：万元）

上述三种不同程度的时间约束及其优化结果反映了配送成本、投资成本、配送中心运营成本与配送时间之间的效益悖反。企业可利用此类情景分析来量化满足配送时间所需的投资，为解决配送时间和成本之间的权衡问题提供决策依据。

2.3 运算效率分析

运用优化软件Lingo 11求解本文所建立的模型并对运算效率进行分析。以3个投资情景和3个需求情景为基础，比较有时间约束和无时间约束情况下Lingo 11的程序的求解时间。求解时间由单个投资情景下最优值求解时间、遗憾系数下限的求解时间和鲁棒优化模型的求解时间组成。

求解时间随着配送中心数量的增加而递增，且耗时增速越来越快，如图2所示。无时间约束情况下总求解时间比有时间约束情况下的总求解时间少，且耗时增加的速度也比有时间约束情况下慢。这是因为时间约束采用大量0-1整数变量来选择特定的“工厂—配送中心”或“配送中心—需求地”线路组合，随着网络中节点数量增大，0-1变量数量呈指数级增长，从而增加运用Lingo求解的难度。

图2 Lingo优化程序的求解时间

经过测试，在无时间约束的情况下，Lingo能很好地满足运算需要，大规模算例也能在较短的时间内求得全局最优解。在有时间约束的情况下，在5个工厂、40个配送中心（其中待选配送中心30个）、10个需求地的情况下，总求解时间不超过3分钟。这已经能够较好地满足企业的决策需要。

3 结束语

经济环境的日趋复杂使得物流网络设计所面临的源自投资成本和市场需求的不确定性大幅增加。选址战略的实施能否取得预期的效果在很大程度上取决于能否有效地应对这些不确定性。在这一背景下，本文建立了配送中心的选址和能力规划的鲁棒优化模型，运用相对遗憾值约束来保证在这些不确定因素的扰动下优化结果仍在决策者接受的范围之内。该模型不仅考虑了新建配送中心和对现有配送中心的能力调整，还反映了各需求点对配送时间的要求，为实现降低成本兼顾客户服务水平提供了辅助决策支持。算例分析揭示了保证求解结果的鲁棒性的代价，探讨了配送时间约束的影响。虽然本文验证了运用Lingo求解所建立的鲁棒优化模型的可行性和适用性，但在如何求解更大规模的设施选址和能力规划的鲁棒优化问题以及将选址决策与库存决策相结合等方面仍有待于进一步研究。

[1]Kouvelis P,Kurawarwala A A,Gutiérrez G J.Algorithms for Robust Single and Multiple Period Layout Planning for Manufacturing Systems[J].European Journal of Operational Research,1992,63(2).

[2]Mulvey J M,Vanderbei R J,Zenios S A,Robust Optimization of Large-Scale Systems[J].Operations Research,1995,43(2).

[3]田俊峰，杨梅，岳劲峰.具有遗憾值约束的鲁棒供应链网络设计模型研究[J].管理工程学报，2012，26(1).

[4]李延晖，马士华，刘黎明.基于时间约束的配送系统模型及一种启发式算法[J].系统工程，2003，21（7）.

[5]李延晖，马士华.基于时间约束的单源/p个中转点配送系统的MINLP模型[J].中国管理科学，2004，12（6）.