对《Split Delivery Capacitated Profitable Tour Problem with Incomplete Service（SDCPTP-IS）》混合整数线性规划模型及其数学启发式算法的学术研究报告
本报告旨在向学术界同仁介绍由 Marvin Caspar（所属机构：德国凯泽斯劳滕-兰道大学商业信息系统与运筹学研究组，Business Information Systems & Operations Research (BISOR), University of Kaiserslautern-Landau）所进行的一项原创性运筹学研究。该研究以学术论文《A matheuristic for the split delivery capacitated profitable tour problem with incomplete service》的形式，发表于期刊 Central European Journal of Operations Research 的2026年第34卷第211-238页（在线发布于2025年10月18日）。论文系统性地探讨了带不完全服务的可拆分配送能力约束盈利巡回问题，并提出了相应的数学模型与高效的求解算法。
一、 研究的学术背景
本研究隶属于运筹学（Operations Research）领域中的组合优化与车辆路径规划（Vehicle Routing Problem, VRP）分支。研究的核心动机源于企业在实际物流与运输决策中面临的复杂权衡。在按订单生产、次日达等场景下，企业资源（如车辆、人力）有限，并非所有客户订单都值得或能够被完全满足。因此，决策者需要在接受订单带来的收益（奖励）与履行订单所产生的配送成本之间进行权衡，以最大化整体净收益。这一决策问题在学术上被抽象为带利润的车辆路径问题（Vehicle Routing Problems with Profits, VRPPs）或其特例——能力约束盈利巡回问题（Capacitated Profitable Tour Problem, CPTP）。
传统的CPTP假设每个被接受的需求（请求）必须由一辆车完整配送。然而，现实场景中存在两种重要的松弛情形：1) 可拆分配送（Split Delivery, SD）：允许一个客户点的需求由多辆车共同完成，这在需求量大或货物体积超过单车容量时是必要的。2) 不完全服务（Incomplete Service, IS）：允许部分满足一个客户的需求，即只配送其需求的一部分以获得相应比例的收益，这在资源极度紧张时可能更有利。尽管SD和IS在经典车辆路径问题（如SDVRP）中已有研究，但正如Archetti等人（2014b）所指出的，它们在以利润最大化为目标的CPTP类问题中的联合研究存在空白。这两种松弛增加了问题的计算复杂性，因此，评估在何种条件下引入SD和/或IS所带来的运营收益提升能够抵销其增加的计算成本，成为一个具有重要理论与实际价值的研究课题。为此，本研究提出了 “带不完全服务的可拆分配送能力约束盈利巡回问题”（SDCPTP-IS），旨在填补这一研究空白，并系统探究SD和IS对CPTP解决方案的影响。
二、 研究的详细工作流程
本研究的工作流程逻辑严谨，主要包含四个核心阶段：问题定义与性质分析、数学模型构建、求解算法设计以及计算实验与数值分析。
第一阶段：问题定义与理论性质分析。 研究首先明确定义了SDCPTP-IS：给定一个完全图、一个车队（同质车辆，容量有限）、一组潜在客户请求（每个请求包含位置、需求量和对应的完全满足时的总收益），目标是选择请求子集，并为每辆车规划一条从车场出发、访问部分选定客户点（每个被访问点仅被访问一次）后返回车场的可行路径，允许请求被多辆车服务（SD）且允许部分服务（IS），以最大化净收益（收集到的按比例计算的收益总和减去所有车辆的旅行成本）。在此定义基础上，研究推导并证明了SDCPTP-IS在满足三角不等式条件下的几个关键性质定理（Theorems 1-4）和最优解界限定理（Theorems 5-7）。例如，定理1证明了最优解中不存在“k-分割环”（k-split cycles）；定理2指出每辆车路径上最多有一个请求接受不完全服务；定理5-7则分别给出了允许SD或IS后，相对于不允许这些特性的CPTP最优解，目标函数值提升的理论下限（例如，在某些条件下，SDCPTP的解至少能达到SDCPTP-IS最优值的一半）。这些理论分析不仅加深了对问题结构的理解，也为后续算法设计和性能评估提供了理论基准。
第二阶段：数学模型构建。 基于对问题的深刻理解，研究者为SDCPTP-IS构建了一个混合整数线性规划（Mixed-Integer Linear Programming, MILP） 模型（公式5-19）。这是一个无向的三下标车辆流模型，其核心变量包括：表示弧是否被车辆使用的二元变量 (x_{i,j,k})，表示请求是否被接受的二元变量 (zi)，表示请求是否被车辆访问的二元变量 (h{i,k})，以及表示车辆向请求配送数量的整数变量 (q_{i,k})。目标函数（5）最大化净收益（比例收益减去旅行成本）。约束条件包括：对称性约束（6）、车辆离场与返回约束（7）、访问与流量平衡约束（8）、有效不等式（9）、请求接受与访问关系约束（10-11）、车辆容量约束（12）、配送量与访问关系一致性约束（13）以及关键的Bienstock子回路消除约束（Bienstock subtour elimination constraints）（14）。该模型结构清晰，并且研究指出，通过简单修改约束（10）和（11），该通用模型可以退化为仅允许SD的SDCPTP模型、仅允许IS的CPTP-IS模型以及两者都不允许的标准CPTP模型。这为对比研究提供了统一的建模框架。
第三阶段：求解算法设计——数学启发式（Matheuristic）。 鉴于包含SD和IS的扩展问题复杂度高，直接使用商业求解器（如Gurobi）求解MILP模型可能在大规模实例上效率不足。因此，本研究创新性地设计了一种数学启发式算法，该算法巧妙地将启发式搜索与精确数学规划相结合。算法核心流程（算法2）如下： 1. 生成候选请求集：根据请求的收益、需求及其与车场的距离计算一个“平均价值”指标，按降序排序，逐步将请求加入一个子集，确保该子集的总需求不超过车队总容量，从而构成一个可行的能力约束车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）实例。 2. 求解CVRP子问题：使用一种引导式局部搜索（Guided Local Search, GLS） 启发式算法（算法1）来求解上一步生成的CVRP实例。GLS通过在标准局部搜索的目标函数中引入对当前解中特定特征（如被使用的弧）的惩罚项来逃离局部最优，从而高效获得一个高质量的CVRP解。该解提供了每个车辆k为每个请求i的配送量 (q_{i,k}^{gls}) 和请求接受决策 (zi^{gls})。 3. 嵌入与求解MILP：将GLS得到的解信息以嵌入策略的方式固定到SDCPTP-IS的MILP模型中。具体有两种策略：a) hqκ策略：固定前κ辆车（κ ≤ |K|）的配送量变量 (q{i,k}^{gls})；b) hzκ策略：固定前κ辆车的请求接受变量 (z_i^{gls})。κ=0意味着不固定任何变量，即直接求解原MILP；κ=|K|则固定所有变量。通过调整κ，可以在求解质量和计算时间之间进行权衡。最后，求解这个部分变量被固定的、规模缩小的MILP模型，得到SDCPTP-IS的最终解。
第四阶段：计算实验与数值分析。 研究采用了两组共40个基准测试实例：一组改编自文献中的CVRP实例，另一组源自Archetti等人（2009）的CPTP研究。实验比较了四种问题变体（CPTP, SDCPTP, CPTP-IS, SDCPTP-IS）的求解性能，并对比了三种求解方法：a) 直接使用Gurobi求解器求解完整MILP模型（时间限制3600秒）；b) 使用上述数学启发式，采用hqκ嵌入策略（在GLS耗时60秒后，MILP求解限制900秒）；c) 使用数学启发式，采用hzκ嵌入策略。实验记录了获得的最佳目标函数值、计算时间或剩余MIP间隙（Gap），并统计了最优解中接受SD和IS的请求数量。
三、 研究的主要结果
实验数据详尽地展示了不同方法在不同问题变体上的表现，主要结果可归纳如下： 1. SD与IS的效益对比：允许不完全服务（IS）对目标函数值的提升显著高于允许可拆分配送（SD）。平均而言，CPTP-IS相比CPTP带来了约4.4% 的改进，而SDCPTP仅带来约1.1% 的改进。SDCPTP-IS（同时允许两者）相比CPTP的平均改进约为4.5%，与CPTP-IS非常接近，表明在CPTP中引入IS是收益提升的主要来源，而额外引入SD带来的边际收益有限。 2. 求解方法性能：所提出的数学启发式算法（特别是hqκ策略）在大多数情况下显著优于直接求解完整MILP模型。尽管启发式的总计算时间（GLS + 限制性MILP求解）更短（通常少于完整MILP求解时间的三分之一），但它往往能找到质量相当甚至更好的解。对于大规模或复杂实例，完整MILP模型在1小时后可能仍有较大的MIP间隙，而启发式则能更快地给出高质量可行解。 3. 嵌入策略有效性：在数学启发式中，hq1策略（即仅嵌入第一辆车的配送量变量）在绝大多数实验中被证明是表现最佳的单一策略，在求解质量和效率之间取得了最佳平衡。 4. 最优解结构：在找到的最佳SDCPTP-IS解中，平均仅有约0.4个请求接受了SD，而有约1.5个请求接受了IS。这进一步印证了IS在提升解质量方面扮演了更关键的角色。同时，最优解的结构特性（如每辆车最多一个IS请求、总分割数小于车辆数等）与理论分析相符。
四、 研究的结论与价值
本研究得出以下核心结论： 1. 管理启示：对于类似CPTP的运输规划问题，决策者应优先考虑允许不完全服务（IS），因为它能带来更显著的利润提升。而可拆分配送（SD） 的应用价值更具情境依赖性，例如在车辆容量很小或单个客户需求非常高时可能更有效，不应仅为了提升目标值而盲目引入。同时，引入SD和IS会增加问题的计算难度。 2. 方法学建议：不建议仅依赖商业求解器直接求解SDCPTP-IS、SDCPTP或CPTP-IS的MILP模型，尤其对于时间敏感或大规模问题。本研究提出的数学启发式算法（特别是嵌入GLS解中配送量变量的策略）是更高效、可靠的求解工具，能在更短的时间内提供优质解决方案。 3. 学术贡献：本研究首次系统地将SD和IS同时引入CPTP框架，建立了完整的MILP模型，证明了问题的重要理论性质，并开发了高效的数学启发式求解算法。研究通过详尽的数值实验，量化了不同松弛条件对问题解的影响，填补了该领域的研究空白。
五、 研究的亮点
六、 其他有价值内容
研究还讨论了SDCPTP-IS的实际应用场景，例如“最后一公里配送”（Last-mile delivery）中因货物体积过大而需要分车配送，以及垃圾收集中因分类要求需要在同一地点进行多次独立收集。这些联系增强了研究的现实意义。此外，论文包含详尽的文献综述，梳理了盈利巡回问题、可拆分配送及不完全服务在路径优化领域的研究脉络，为相关领域研究者提供了有价值的参考。