从固定到灵活：调度问题中访问次数约束的算法挑战与优化策略

1. 从“固定两次”到“灵活一到两次”：一个调度问题的本质跃迁

在调度问题的世界里，我们常常会遇到一些看似简单、实则暗藏玄机的约束条件。今天想和大家深入聊聊的，就是一个从“2-Visits”到“(1或2)-Visits”的转变。乍一看，这不过是把访问次数从固定的2次，放宽到了灵活的1次或2次，似乎只是参数上的一点小调整。但真正做过算法设计和结构分析的朋友都知道，这种约束条件的“软化”，往往意味着问题本质的深刻变化，其背后的算法复杂度和可行解空间的结构，可能会发生天翻地覆的改变。

我最初接触到这类问题，是在一个实际的物流配送场景中。当时的需求是，每个客户点（比如一个仓库或门店）必须被访问恰好两次——一次卸货，一次装货。这对应着经典的“2-Visits”约束。我们设计了一套基于启发式的算法，跑得还算顺畅。但后来业务需求变了：有些点只需要卸货（访问1次），有些点则需要既卸又装（访问2次）。需求方轻描淡写地说：“这不就是改成1次或2次嘛，应该很简单吧？” 结果，我们原有的算法框架几乎需要推倒重来。这次经历让我深刻体会到，在调度与组合优化领域，“或”这个字所带来的复杂性，常常远超“与”和“固定值”。

所以，这篇文章，我想结合“调度问题”、“算法扩展”和“结构分析”这几个关键词，把这次从“2-Visits”到“(1或2)-Visits”的升级之旅，以及其中涉及的算法思想、结构变化和实战心得，系统地梳理一遍。无论你是正在研究类似问题的算法工程师，还是对运筹优化感兴趣的研究者，希望这些从泥坑里爬出来的经验，能给你一些实实在在的参考。

2. 问题定义与建模：约束“软化”带来的根本性挑战

在深入算法之前，我们必须先把问题定义清楚。这不仅仅是学术上的严谨，更是为了避免后续开发中的方向性错误。

2.1 “2-Visits”问题的经典模型

首先，我们明确一下“2-Visits”调度问题的一个典型形式。假设我们有一个图G=(V, E)，其中V是顶点集合（代表需要访问的点），E是边集合（代表点之间的路径，有权重如距离或时间）。问题的目标是找到一条或多条路径（例如，车辆路径），使得每个顶点v ∈ V被恰好访问两次。此外，通常还会有其他约束，比如路径的总长度限制、时间窗、车辆容量等。

一个常见的建模方式是将其转化为一个广义的旅行商问题（TSP）变种或车辆路径问题（VRP）变种。每个需要访问两次的点，可以在模型中视为两个“任务点”（例如，v_in和v_out），它们必须被不同的访问序列所覆盖，并且可能带有先后顺序约束（如卸货必须在装货之前）。这种模型的解空间相对规整，因为每个点的处理模式是唯一确定的。

2.2 “(1或2)-Visits”问题的模型扩展与复杂性跃升

现在，我们将约束放宽为“(1或2)-Visits”。这意味着对于每个顶点v ∈ V，我们有一个决策变量k_v ∈ {1, 2}，表示访问该点的次数。这个决策本身，就成了优化的一部分。问题变成了：在满足所有其他约束（如总行程、时间窗）的前提下，同时决定每个点访问1次还是2次，并找到相应的最优访问路径。

这个小小的“或”字，引入了两个层面的根本性挑战：

1. 组合爆炸：决策空间从固定的2n个访问任务（假设n个点，每个点2次），变成了对每个点有2种选择（1或2次）。仅就访问次数决策而言，可能性就有2^n种。这直接导致了问题规模的指数级增长。
2. 耦合性增强：访问次数的决策与路径规划决策强烈耦合。为一个点选择访问2次，可能会因为需要往返或绕路，大幅增加总成本，从而使得选择访问1次在整体上更优。反之，如果某个点处于关键路径上，访问它2次可能并不会显著增加成本，甚至可能通过合并其他任务而变得更高效。这种“是否值得为某个点付出额外访问成本”的权衡，是原“2-Visits”问题所没有的。

从计算复杂性角度看，许多经典的“2-Visits”问题可能是NP-Hard的，但“(1或2)-Visits”版本几乎可以肯定是一个更难的优化问题，因为它包含了前者的一个特例（当所有k_v被强制设为2时）。这要求我们的算法不能仅仅是“打补丁”，而需要从结构上进行重新思考。

注意：在实际建模中，除了k_v，通常还需要引入二元决策变量来刻画具体的访问顺序和路径连接关系。模型会迅速变得庞大且非线性，直接使用商业求解器（如Gurobi, CPLEX）求解中等规模实例都可能非常耗时。因此，设计专用的启发式或元启发式算法几乎是必然选择。

3. 算法策略的演进：从“先决策后路由”到“协同进化”

面对“(1或2)-Visits”问题，最直接的算法扩展思路可能行不通。我们需要更精巧的策略。下面分享几种我们尝试过或研究过的算法思路，并分析其优劣。

3.1 策略一：两阶段法（先决策，后优化）

这是最直观的扩展思路：第一阶段，决定每个点v的访问次数k_v；第二阶段，将k_v=2的点拆分为两个子任务，然后求解一个经典的多次访问路径问题。

• 如何决策k_v？
  • 基于规则：例如，根据点的优先级、需求量、或与其他点的距离聚类中心程度来决定。优先级高、需求量大的点可能更需要2次访问（例如，核心枢纽）。孤立点访问2次的成本过高，则设为1次。
  • 简单成本估算：粗略估算将每个点从1次访问改为2次访问所增加的路径成本增量，与可能带来的收益（如服务水平提升）进行比较。但这需要非常粗略的路径成本估计模型，准确性存疑。
• 优缺点分析：
  • 优点：思路简单，模块化清晰，可以复用第二阶段成熟的路径优化算法。
  • 缺点：两阶段割裂了核心决策的耦合性。第一阶段的决策在没有精确路径信息的情况下做出，很可能导致第二阶段找不到优质解，甚至找不到可行解。第一阶段的一个糟糕决策（如错误地将一个偏远点设为2次访问），可能让第二阶段的优化陷入僵局。

我们在初期尝试了这种方法，结果往往是第一阶段觉得“合理”的决策，到了第二阶段优化出来的总成本却非常高。这印证了耦合决策的重要性。

3.2 策略二：基于大规模邻域搜索（LNS）的集成优化

这是更有效的思路，将访问次数决策和路径规划决策在同一个搜索框架中进行优化。大规模邻域搜索（LNS）非常适合这类问题。

• 核心思想：从一个完整解（包含所有点的访问次数和具体路径）开始，通过“破坏”和“修复”算子进行迭代改进。
• 破坏算子设计：
  • 访问次数扰动：随机选择一部分点，翻转其访问次数（1变2，2变1）。这是专门为“(1或2)-Visits”设计的关键算子。
  • 路径片段移除：随机移除一条路径中的连续若干访问点，或随机移除多个分散的点。
• 修复算子设计：
  • 将“破坏”后产生的“未安排点”（包括访问次数被改变的点）重新插入到现有路径中。插入时需要同时考虑插入1次还是2次（对于刚被扰动或原本未安排的点），以及插入的位置。这通常通过一个代价函数来评估所有可能的插入方式和位置，选择代价最小的。
• 算法流程：
  1. 生成一个初始可行解（例如，所有点都设为1次访问，并构造一个简单的路径）。
  2. 循环直到终止条件（如时间或迭代次数）： a.破坏：应用破坏算子，移除部分点及其访问安排。 b.修复：应用修复算子，以最优或启发式方式重新插入被移除的点，并决定其访问次数。 c.评估：计算新解的成本，根据模拟退火等准则决定是否接受新解。
• 优势：LNS框架允许算法动态地调整访问次数决策。在一次迭代中，一个点可能从1次访问变为2次，如果这有助于降低总成本（例如，通过合并顺路任务），这个改变就会被保留下来。它很好地处理了决策耦合性。

我们在实际项目中最终采用了以LNS为核心的算法框架，因为它提供了足够的灵活性来探索庞大的解空间。

3.3 策略三：数学规划启发式（Matheuristic）

对于问题规模不是特别大，但又需要较高求解质量的情况，可以结合数学规划的力量。

• 核心思想：将原问题分解为主问题和子问题。主问题负责处理“高层”决策，如访问次数的分配、点的粗略分簇；子问题则是对每个簇或局部区域，求解一个带固定访问次数约束的精确路径问题（使用MIP求解器）。
• 具体做法（一种可能）：
  1. 松弛模型：先建立一个混合整数规划（MIP）模型，但松弛掉一些复杂约束（如具体的子环路消除约束），或者将问题分解为“决定访问次数”和“粗略分配点到路径”两个部分。
  2. 求解松弛模型：使用求解器快速得到一个松弛解。这个解给出了每个点k_v的取值建议，以及点与点之间的大致关联关系。
  3. 固定与细化：将松弛解中k_v值明确（例如，取值接近2的固定为2，接近1的固定为1），或者将关联紧密的点固定到同一条路径上。然后，对于每一条被固定的“路径骨架”或“点簇”，构建一个精确的、规模较小的TSP或VRP子问题（此时每个点的访问次数已确定），调用求解器精确求解。
  4. 迭代改进：根据子问题的求解结果，可以调整主问题的参数或约束，进行下一次迭代。
• 优势：能够利用商业求解器强大的精确求解能力，在局部搜索中跳出局部最优。对于k_v决策这种离散组合决策，MIP求解器有时能提供很好的洞察。
• 劣势：实现复杂，需要精心设计分解策略，且子问题调用求解器可能较慢，整体算法效率需要仔细权衡。

4. 解空间的结构性分析：为什么“(1或2)”比“2”难得多？

算法设计离不开对问题解空间结构的理解。从“2-Visits”到“(1或2)-Visits”，解空间发生了结构性变化，这直接影响了算法的设计和性能。

4.1 解空间的维度与连通性

• “2-Visits”空间：解空间主要由路径排列顺序构成。每个点出现两次，但这两个“副本”是有序的（如卸货、装货）。搜索算子（如交换、倒置）主要在这个排列空间中进行。空间的维度相对“规整”。
• “(1或2)-Visits”空间：解空间是“访问次数决策空间”和“路径排列空间”的笛卡尔积。这是一个更高维、更复杂的空间。更重要的是，这两个子空间并非独立。空间的连通性变得更差。一个仅改变路径但不改变访问次数的移动，可能无法到达另一个需要改变某个点访问次数才能抵达的优质解区域。这就要求算法必须包含能改变k_v的专门算子（如我们LNS中的“访问次数扰动”），否则算法会被困在某个k_v决策固定的子空间里。

4.2 局部最优的“陷阱”密度

在“(1或2)-Visits”问题中，局部最优解的数量可能远多于原问题。考虑一个简单场景：一个点v处于“临界状态”——访问它1次和2次的成本差异很小。在某个解S1中，k_v=1是局部最优（稍微改变路径，k_v=1仍是最优）。但在另一个解S2中，由于其他点的安排发生了较大变化，k_v=2可能变得更好。然而，从S1到S2，可能需要先经历一个k_v=2但路径未调优的“差解”阶段，才能到达调优后的S2。如果算法不能容忍这种暂时的成本上升（即缺乏“爬山”能力），就永远找不到S2。这使得“(1或2)-Visits”问题的能量地形图更加崎岖，布满深坑。

4.3 对启发式信息依赖的变化

在经典路径问题中，距离是核心启发式信息：两点近则更可能被安排在相邻位置访问。在“(1或2)-Visits”问题中，启发式信息需要扩展。除了距离，我们还需要一个关于“访问次数收益比”的启发式估计。

例如，我们可以为每个点v预先计算一个粗略的“二次访问边际成本”估计值。这个估计值可以通过计算v到其他所有点平均距离的某种函数来获得。如果一个点的“二次访问边际成本”很低，那么它在搜索初期被赋予k_v=2的可能性就应该增加。这种动态的、与问题实例相关的启发式信息，对于引导搜索方向至关重要，而这在固定访问次数的问题中是不需要的。

5. 实战案例：磁盘驱动调度问题的启示

网络热词中提到了“7-5 求解磁盘驱动调度问题”。这虽然是一个不同的领域，但其核心思想——磁头移动调度以最小化寻道时间——与我们讨论的路径调度有深刻的相似性，尤其是在处理访问次数灵活性时。

在传统的磁盘调度算法（如SCAN, C-SCAN）中，磁头对柱面的访问请求通常是“1-Visit”的：每个柱面在本次扫描中最多访问一次来处理其上的I/O请求。但我们可以设想一个更复杂的场景：某些“热点”数据块可能需要被连续读写多次（类似“2-Visits”），或者根据请求类型，某些柱面可能需要优先访问（影响访问顺序决策）。

将这个场景抽象并联系到我们的问题：

• 柱面->顶点（V）
• 磁头移动轨迹->路径
• 寻道时间->路径成本（距离）
• 对某个柱面的一次I/O请求->对该顶点的一次访问
• 热点数据块需要多次访问->该顶点需要“2-Visits”

那么，“求解磁盘驱动调度问题”的扩展版本就可以是：给定一组I/O请求，其中某些请求可能指定了对同一柱面的多次访问（或允许一次或两次访问以平衡延迟和吞吐量），如何规划磁头的移动顺序，以最小化总寻道时间？

这个类比告诉我们，从固定访问模式到灵活访问模式的扩展，是一个跨领域的共性挑战。在磁盘调度中，如果允许对某些柱面进行二次访问而不立即离开，可能会减少总的磁头移动距离（例如，在处理完一个柱面的多个请求后，再移动到下一个，而不是来回跳动）。这类似于在物流配送中，为某个客户完成卸货和装货两次操作后再离开，可能比分开两次访问更省油。

解决这类问题的算法核心依然是在“额外访问成本”和“任务合并收益”之间做动态权衡。无论是磁头在磁盘柱面间移动，还是车辆在城市道路间行驶，其背后的组合优化逻辑是相通的。

6. 实现细节与性能调优经验

理论分析之后，分享一些在具体实现和调优“(1或2)-Visits”算法时积累的实战经验。

6.1 初始解构造策略

一个好的初始解能显著加快收敛速度。不建议从全1或全2开始，因为那可能离最优解太远。

• 聚类优先法：先忽略访问次数，对所有点进行空间聚类（如K-Means）。在同一个簇内，点之间距离近，为其中某些点安排2次访问的额外成本可能较低。可以尝试将每个簇的中心点或需求量大的点初始化为2次访问，其余为1次。
• 贪婪插入法：从一个空路径开始，每次选择一个未安排的、且“性价比”最高的点插入。插入时评估插入1次和插入2次的成本增量，选择增量小的那种方式。这里的“性价比”可以定义为（需求量/预估二次访问成本）。

6.2 破坏与修复算子的平衡

在LNS框架中，破坏和修复的强度需要仔细调节。

• 破坏强度：一次破坏多少个点？这包括改变访问次数的点数和从路径中移除的点数。强度太小，搜索局限于局部；强度太大，修复阶段计算量大，且可能丢失当前解的所有优良特性。我们的经验是从中等强度开始（如扰动10%-20%的点的访问次数，并移除15%-25%的路径点），根据算法收敛情况动态调整。
• 修复策略：修复算子是计算成本的主要来源。评估所有可能的插入位置和方式（1次或2次）是O(n^2)的复杂度。需要优化：
  • 限制搜索范围：对于一个待插入点，只考虑当前解中距离它最近的K条路径，或每条路径上距离插入点最近的几个前后位置进行评估。
  • 增量计算：缓存路径的距离、负载等信息，在评估插入代价时进行增量更新，避免每次重新计算整条路径的成本。

6.3 评估函数的设计

成本函数不能只考虑总行驶距离。对于“(1或2)-Visits”问题，需要加入对访问次数决策的软约束或惩罚项。

• 基础成本：总行驶距离或时间。
• 惩罚项：如果业务上对“访问1次”和“访问2次”有偏好（例如，尽量让所有点都访问2次以提高服务频率，但允许例外），可以在成本函数中加入对k_v=1的惩罚。这样，算法会在“增加距离”和“减少惩罚”之间进行权衡。
• 多目标考虑：有时可以将距离最小化和访问次数最大化（或1次访问点数最小化）作为两个目标，采用帕累托优化思想。

6.4 算法停止与解的选择

由于问题复杂，算法可能运行很长时间。需要合理的停止准则：

• 迭代次数/时间限制：最直接的方式。
• 改进停滞：连续N次迭代没有找到更优解，可能意味着陷入局部最优，可以触发一次强扰动（大幅增加破坏强度）来跳出。
• 解池管理：维护一个精英解池，记录搜索过程中找到的多个互不支配的帕累托最优解（如果有多目标）。最终可以从解池中根据业务偏好选择一个。

7. 总结与延伸思考

回顾从“2-Visits”到“(1或2)-Visits”的算法扩展之路，其核心难点在于决策变量的耦合引入了离散的组合选择，从而极大地复杂了解空间的结构。应对这一挑战，两阶段法往往力不从心，而将访问次数决策与路径规划决策置于同一优化框架下的集成方法（如LNS）或分层协同方法（如Matheuristic）更为有效。

这次升级给我的深刻启示是：在调度优化中，任何约束条件的“软化”（从“等于”到“属于某个集合”，从“必须”到“尽可能”）都不仅仅是参数调整，而是一次对问题本质和算法架构的重新审视。它要求算法具备在更高维、连通性更差的解空间中进行有效搜索的能力，这通常意味着需要设计专门的搜索算子和更精巧的启发式策略。

最后，联想到磁盘调度等其它领域的问题，这种“灵活访问次数”的范式其实广泛存在。其背后的核心优化思想——在“额外操作成本”与“任务合并/顺序调整收益”之间进行动态的、全局的权衡——是一个具有普遍意义的运筹学主题。掌握了对这类问题的分析和求解方法，就相当于掌握了一把钥匙，能够去开启更多复杂的、贴近现实世界灵活性的调度优化之门。在实际项目中，当产品经理再次提出“这个小改动很简单吧”时，我们至少能从算法复杂性的角度，给出更有力的分析和更靠谱的工期评估了。