本文提出多目标企业绿色供应链网络设计问题,以0-1整数规划同时最小化设施建设与运输成本、碳排放和客户不满意度,并通过加权和ILP、三类FPTAS及基准启发式进行比较。在8个客户区域和5个候选配送中心的实例中,精确求解仅发现两组非支配网络方案;FPTAS在满足1+ε近似保证的同时显著降低计算时间,而开放全部配送中心和最近配送中心等启发式方法在排放、成本及客户不满意度方面明显劣于优化方法。
| 非支配方案 | 开启配送中心 | 总成本 (f_1) | 排放 (f_2) | 客户不满意度 (f_3) | 主要优势 |
|---|---|---|---|---|---|
| 方案A | DC 0、2、3 | 1282.9 | 851.1 | 21,057 | 成本与客户不满意度 |
| 方案B | DC 1、2、3 | 1291.7 | 830.7 | 21,535 | 排放 |
| FPTAS方法 | 主要优化目标 | 关键结果 | 相对参考解表现 |
|---|---|---|---|
| B1 Cost-FPTAS | 总成本 (f_1) | 接近方案A | 成本差距+0.8%,排放差距+7.2% |
| B2 Emission-FPTAS | 碳排放 (f_2) | 选择DC 2、3、4 | 排放差距+7.0%,成本差距+8.1%,不满意度差距+8.7% |
| B3 Pareto-FPTAS | 成本—排放二维Pareto前沿 | 保留1个网格代表解 | 与B1方案一致 |
报告的核心论点是:企业供应链网络设计不能只追求成本最小化,还必须同时考虑碳排放和客户不满意度;这三个目标之间存在明显冲突,因此应通过Pareto前沿刻画不同的折中方案。, 在一个包含8个客户区域和5个候选配送中心的小型实例中,作者声称精确ILP能够识别出完整Pareto前沿,而三种FPTAS在允许误差ε=0.15的情况下,也能以毫秒级运行时间取得接近精确解的结果。,
不过,这篇论文更接近一个“算法框架演示”和小规模数值实验,而不是对现实供应链管理具有充分外推能力的实证研究。其主要局限包括:只使用单一确定性实例;部分表格原始数值在文本中没有完整展示;FPTAS的理论复杂度和保证条件还需要更严谨地论证;此外,图示中的“Balanced”解与正文对星号解的描述存在潜在矛盾。
论文考虑三个都需要最小化的目标:
这一建模逻辑是合理的:新增配送中心通常可以缩短客户运输距离,改善服务质量;但是新增设施会带来固定建设成本和一次性建设排放。同时,如果过多客户集中在某一个容量有限的配送中心,则会出现容量约束,网络设计不能单纯按照地理距离进行决策。
报告指出,问题属于多目标组合优化。由于成本、排放和服务水平通常不能同时达到各自最优,研究目标不再是寻找单一最优解,而是寻找由非支配解组成的Pareto前沿。, 所谓非支配解,是指不存在另一个可行方案能够在所有目标上都不差、并且至少一个目标更好。
模型使用两类0-1决策变量:
模型包含以下主要约束:
容量约束中使用了右端项 (\kappa_j x_j),因此当配送中心关闭时,右端项为零,理论上已经能防止其承接客户。作者仍然保留显式的联结约束,理由是可以收紧线性规划松弛,减少分支定界搜索规模。 这一解释符合整数规划中的常见建模实践。
论文通过将容量设施选址问题(CFL)归约到该问题,证明即使只最小化成本目标,MOE-DGSCND仍然是NP-hard。 归约的基本思路是:令运输成本参数与CFL中的客户服务成本相对应,将排放和不满意度参数设为零,从而使新问题的成本目标完全等价于原CFL目标。
因此,计算完整Pareto前沿至少不会比求解单目标容量设施选址更容易。 报告还通过估计搜索空间说明穷举法不可行:在实验实例中,论文给出的候选解数量上界约为 (3.518437\times10^{13}),即使变量规模看似很小,直接枚举所有选址和分配组合也会迅速失去可操作性。
但是,复杂度部分存在若干需要谨慎看待之处。论文关于不可近似性的表述将集合覆盖、非容量设施选址和当前带容量及预算约束的问题联系在一起,但这些问题的近似界并不能简单等同,相关结论需要更加明确地区分问题版本、目标函数和假设条件。 因此,复杂度章节能够支持“问题具有较高计算难度”这一总体判断,但其具体近似界表述仍应通过更严格的定理条件加以限定。
作者将三个目标通过加权标量化转化为单一目标问题。其思想是对每个目标进行归一化,再使用权重 (w_1,w_2,w_3) 加总,其中权重满足非负且总和为1。
这种方法的优点是容易使用成熟的ILP求解器,并且改变权重即可获得不同偏好的候选方案。论文使用CBC求解器,并通过PuLP建模接口调用;所有求解均要求达到零最优性间隙,即声称获得了精确最优解。,
不过,加权和方法并不一定能够发现非凸Pareto前沿上的全部非支配点。论文自身也较谨慎地使用了“Pareto-optimal或weakly Pareto-optimal”等表述,但在后文又将八组权重得到的结果称为完整Pareto前沿,这两种说法之间需要加以区分。
作者设置了8组权重,并将等权重解称为“Balanced”或星号解,用作后续差距比较的基准。 实验结果声称,八组权重最终只识别出两个不同的非支配方案:
这两个方案构成一个非常短的Pareto前沿:方案A比方案B便宜、不满意度更低,但排放更高;方案B排放更低,但成本和不满意度略差。 从决策角度看,这意味着管理者似乎主要面临“低成本/高排放”和“低排放/略高成本”的二元选择,而不是一条包含大量中间方案的连续折中曲线。
论文还指出,当排放权重超过33%时,模型倾向于选择方案B;在其他权重组合下则选择方案A。 这表明排放目标的权重存在一个相对明显的决策阈值。
三类FPTAS都采用“评分—缩放—舍入—枚举—筛选”的流程。算法首先为每个配送中心计算目标相关的评分,然后使用粒度参数 (K) 将连续评分舍入为离散等级,最后枚举不同大小的配送中心子集并进行贪心分配。
理论上,FPTAS应当在输入规模和 (1/\varepsilon) 上均为多项式时间,并返回不超过最优值 (1+\varepsilon) 倍的解。 本文设置(\varepsilon=0.15),意味着目标保证通常是15%的相对误差上界。
但这里存在一个重要的理论疑点:论文描述的算法仍然枚举所有大小不超过 (B) 的配送中心子集。实验中 (n=5,B=3),一共枚举25个子集,因此运行很快;然而一般情况下,子集数量为 (\sum_{r=1}^{B}\binom{n}{r}),当 (B) 随输入规模增长时,这并不一定是关于 (n) 的多项式时间。论文在复杂度描述中也写有“对于固定B为多项式”,这实际上弱化了其作为标准FPTAS的普适性。, , 因此,实验上的快速表现不能自动证明算法满足严格意义上的FPTAS定义。
B1针对成本目标设计配送中心评分,并返回成本接近成本最优的方案。, 实验中,B1选择了DC 0、2、4,其成本比星号解高0.8%,但排放高7.2%。这说明B1确实能够较好控制成本,却没有同步优化排放。
这也是多目标问题中单目标近似算法的典型特征:即使成本接近最优,设施组合仍可能因为建设排放参数不同而造成明显的碳排放差异。
B2以排放为目标,对每一个已选配送中心组合采用排放最小化的贪心分配。 该算法选择了DC 2、3、4,这一组合没有被精确ILP的八组权重发现。
B2的排放值为888.3,相对于星号解高7.0%;同时成本高8.1%,不满意度高8.7%。 这表明B2虽然名称上针对排放优化,但其实际结果并未达到整个实例的排放最优方案B(排放830.7)。这可能意味着算法的评分函数、贪心分配方式或“针对单目标的保证”并没有被充分解释,至少需要进一步说明其比较基准究竟是哪个单目标最优解。
B3仅针对成本和排放两个目标建立几何网格,将目标空间划分为多个网格单元,并在每个单元中保留一个代表解,随后删除被支配的代表点。,
在本实例中,B3最终只保留了一个Pareto网格代表,并且该解与B1相同。 这说明由于实例规模小、目标数值接近,网格化后不同方案被压缩到同一网格单元。
需要特别指出的是,B3的理论保证只覆盖 (f_1) 和 (f_2),第三个目标 (f_3)虽然被报告,但不受近似保证控制。 因而B3不能被解释为完整的三目标Pareto-FPTAS,而是一个成本—排放双目标近似方法。
Open-All直接开启所有候选配送中心,再按照运输成本进行贪心分配。, 其主要价值不是作为可行运营方案,而是作为一个对照基准,用于观察放宽预算约束后的效果。
该方法在客户不满意度上表现较好,较星号解低5.1%,原因是5个配送中心覆盖范围更广,平均运输距离下降。 但它的排放高出32.3%,因为多建设两个配送中心带来了显著的固定建设排放。 这一结果很好地支撑了作者关于预算约束具有实质性战略意义的观点:增加设施虽然能够改善服务,但可能严重恶化环境表现。
Greedy-Nearest按照客户到各配送中心的总几何距离选择最接近的 (B) 个配送中心,但没有充分考虑需求权重、容量和固定开设成本。 该方法的成本高出17.6%,客户不满意度高出21.2%,是整体表现最差的基准方法之一。
这一结果揭示,仅依据地理距离进行选址是不充分的。实验中客户需求从70到200不等,配送中心固定成本从55到95不等;如果忽略这些差异,距离上的局部最优很可能导致容量利用率和总成本上的整体低效。,
实验包含8个客户区域、5个候选配送中心,最多开启3个配送中心,总需求为960单位。, 运输成本率设为每单位每公里0.05美元,排放率设为每单位每公里0.02千克二氧化碳。
论文指出,容量最大的三个配送中心为DC 2、4、0,总容量1350,超过总需求;固定开设成本最低的三个配送中心为DC 3、1、4,总容量1100,同样能够满足需求。 这说明预算为3时问题是可行的,但不是所有三中心组合都一定可行,容量约束确实参与了选址筛选。
论文还提供了客户数据表、候选配送中心数据表和欧氏距离矩阵表。距离矩阵是由二维坐标计算得到,并四舍五入到一位小数。, 这种空间建模清晰直观,但也较为理想化:真实供应链运输距离往往受到道路网络、交通状况、车辆限制和区域边界影响,欧氏距离可能低估实际运输距离。
表4用于展示8组权重对应的精确解。 其核心信息不是每一组权重都产生全新的网络,而是多数组合集中到方案A或方案B。由此可见,该实例的Pareto结构非常简单:排放目标达到一定重要程度时,网络从DC 0切换到DC 1;否则保留成本和不满意度更有优势的组合。
但是,正文对“星号解”的描述需要核对。第11页将方案A描述为成本/不满意度最优,将方案B描述为排放最优;而第15页的网络图明确标记Balanced星号解开启DC1、DC2、DC3,更接近方案B。, 因此,报告应明确星号解到底是方案A还是方案B,否则所有“相对星号解的百分比差距”都会存在解释歧义。
表5比较B1、B2、B3相对于星号解的差距,表6则对各FPTAS相对于相应单目标最优值的比率进行验证。, 报告称全部比率均不超过1.15,因此满足ε=0.15的近似保证。
需要区分两类结论:第一,算法相对于“对应单目标最优值”的比率不超过1.15;第二,算法相对于星号解的差距不超过15%。这两者并不完全等价,尤其当星号解不是各个目标的单目标最优解时,不能直接用星号解差距证明FPTAS的理论保证。
表7展示两个基准启发式方法的结果,表8整合所有方法在三个目标上的表现。, 综合结果呈现出明显层次:
因此,图表所传递的主要信息是:简单启发式方法无法稳定处理成本、环境和服务之间的联动,而带有明确目标导向和组合优化机制的FPTAS表现更可靠。
图1上排展示三个两两目标投影:成本—排放、成本—不满意度、排放—不满意度;下排展示各方法在三个目标上的柱状比较,虚线表示星号基准值。
从图形可以观察到:
图1很好地支持了“该实例的Pareto前沿结构简单”的结论,但由于只有一个小规模实例,不能据此推断所有实际供应链网络都只会出现两种方案。
图2展示Balanced方案的空间网络:开放的配送中心为DC1、DC2、DC3,关闭的为DC0、DC4;客户区域以绿色圆点显示,蓝色线段表示客户分配关系。
图中可以看出,客户C1、C2、C5分配给DC1;C4、C6、C3分配给DC2;C0和C7分配给DC3。该网络体现出明显的地理就近原则:左下区域客户C0、C7由DC3服务,中上区域由DC1服务,右侧客户由DC2服务。 这说明模型在满足容量约束的同时,也形成了较为自然的区域化服务结构。
不过,图2进一步暴露了星号解定义问题:它显示星号方案为DC1、2、3,而第11页将成本/不满意度更优的方案A列为DC0、2、3。因此,报告应在表4、表8和图2之间统一星号方案的编号和目标值。
报告识别的主要风险包括:
报告的最大优势是模型结构完整、算法比较清晰,并且同时呈现了精确方法、近似方法和基准方法。但其主要不足也比较明显:
总体而言,论文构建了一个同时考虑成本、碳排放和客户不满意度的绿色供应链网络设计模型,并通过精确ILP、三种FPTAS和两种启发式方法进行了比较。, 实验结果显示,精确解的Pareto前沿由两个主要网络组成:DC0、2、3方案在成本和服务方面更优,DC1、2、3方案在排放方面更优。
FPTAS方法在这个小实例上表现良好,B1的成本差距仅0.8%,B2的排放差距约7.0%,B3能够生成成本—排放双目标的近似代表解。, 相比之下,Open-All虽然降低了不满意度,却带来32.3%的排放惩罚;Greedy-Nearest则在成本和不满意度上分别恶化17.6%和21.2%。
论文最有价值的管理启示是:预算约束并非单纯的财务限制,而是驱动成本—排放—服务权衡的关键制度变量;在本实例中,多开配送中心所带来的服务改善不足以抵消新增建设排放。, 但要将这些结论推广到更大规模、更复杂、更具不确定性的现实供应链,还需要扩展数据规模、引入随机需求和鲁棒优化,并进一步严谨证明所提出FPTAS的复杂度和近似性质。
2609.11971.pdf