第四篇：约束规划 CP 完全指南：从核心理论到求解器实战，附主流 CP 求解器对比（CP-SAT、CP Optimizer、OptalCP 和 Hexaly）

第四篇：约束规划 CP 完全指南：从核心理论到求解器实战，附主流 CP 求解器对比

• • 第一部分：什么是约束规划？
  • • 1.1 从数学规划到约束规划
    • 1.2 CP 与 MILP 的本质区别
    • 1.3 CP 的核心机制
    • • 1.3.1 域与传播
      • 1.3.2 搜索与回溯
      • 1.3.3 启发式
  • 第二部分：主流 CP 求解器全景图
  • 第三部分：CP Optimizer（IBM CPLEX）完全指南
  • • 3.1 快速开始
    • 3.2 核心概念：区间变量、序列变量、状态变量
    • 3.3 高级调度约束
    • 3.4 完整示例：带换型时间的流水车间
    • 3.5 CP Optimizer 的优势与局限
  • 第四部分：OptalCP——CP Optimizer 的现代化继任者
  • • 4.1 什么是 OptalCP？
    • 4.2 安装与环境配置
    • 4.3 快速入门：最小调度示例
    • 4.4 核心建模概念
    • 4.5 完整示例：作业车间调度问题（JSSP）
    • 4.6 参数配置与调优
    • 4.7 适用场景总结
  • 第五部分：Hexaly——后 MILP 时代的全局优化求解器
  • • 5.1 什么是 Hexaly？
    • 5.2 为什么 Hexaly 值得单独关注？
    • 5.3 Hexaly 安装与验证
    • 5.4 Hexaly 核心建模概念
    • • 5.4.1 决策变量类型
      • 5.4.2 表达式与操作符
      • 5.4.3 一个完整的最小示例：最优水桶（非线性优化）
    • 5.5 生产排程实战：Hexaly 在作业车间调度（JSSP）中的应用
    • 5.6 车辆路径问题（CVRP）的 Hexaly 建模示例
  • 第六部分：Hexaly 对比 CP Optimizer、OptalCP 与 CP-SAT
  • • 6.1 性能基准：大规模调度问题上的压倒性优势
    • 6.2 学术基准：CP 求解器综合对比（2025-2026 最新研究）
    • 6.3 综合对比表：CP Optimizer vs CP-SAT vs OptalCP vs Hexaly vs CPLEX
  • 第七部分：选型决策框架
  • 第八部分：综合资源
  • 结语

在上一篇文章中，我们深入探索了 NVIDIA cuOpt 在 GPU 加速优化领域的突破性能力，分别掌握了 LP、QP、MILP 等标准数学规划范式在 cuOpt 中的建模与求解。本篇将目光转向约束规划（Constraint Programming, CP） 这一独特的优化范式。

第一部分：什么是约束规划？

1.1 从数学规划到约束规划

传统的数学规划（MILP、LP）采用代数建模方式：用线性或二次表达式描述目标函数和约束，通过求解器在连续松弛和分支定界框架下寻找最优解。这种方法对于线性结构明显的问题非常高效，但在面对复杂的逻辑约束（如“如果 A 则 B”、“任务 C 必须在任务 D 之后”）和高阶组合约束（如“所有变量的值互不相同”、“这些资源的总消耗不能超过容量”）时，往往需要引入大量的 0-1 辅助变量和 Big-M 系数，导致模型规模膨胀、数值稳定性下降。

约束规划（Constraint Programming, CP） 采取了完全不同的路径：

• 关系型建模：直接使用高级全局约束（all_different、circuit、cumulative 等）表达复杂关系
• 约束传播：通过域缩减（domain reduction）主动剪枝，而非依赖 LP 松弛
• 搜索与回跳：结合启发式搜索和冲突驱动的回跳（backjumping），高效探索组合空间

CP 尤其擅长处理组合爆炸问题——即变量多、约束复杂、但可行域离散的问题。典型的 CP 应用领域包括：

• 生产调度（作业车间、流水车间、项目调度）
• 人员排班与轮班计划
• 车辆路径问题（CP 变体）
• 拼图与谜题（数独、八皇后、拉丁方）
• 配置与设计（产品配置、航线设计）

1.2 CP 与 MILP 的本质区别

关键结论：对于具有强约束结构、离散决策多、逻辑关系复杂的问题（如车间调度），CP 往往比 MILP 建模更简洁、求解更快；对于包含连续变量和线性目标的大规模问题，MILP 依然是首选。

1.3 CP 的核心机制

1.3.1 域与传播

CP 中每个变量都有一个初始域（可能的取值集合，如整数区间或枚举值）。求解器通过约束传播算法不断缩减这些域：当一个约束导致某个值的不可行，该值会从对应变量的域中删除，并可能触发其他约束的进一步传播。这个过程一直持续到固定点（没有更多值可删）。传播算法针对不同全局约束有专门的高效实现（如 all_different 的基于图匹配的传播器）。

1.3.2 搜索与回溯

当传播无法再缩减域时，求解器选择一个变量进行分支（比如尝试一个具体值），然后继续传播。若分支导致矛盾（空域），则回溯到上一个选择点，并记录冲突原因（回跳）。冲突驱动的回跳（类似于 SAT 求解器的 clause learning）是现代 CP 求解器性能的关键。

1.3.3 启发式

CP 求解器使用大量启发式来加速搜索：

• 变量选择：选择域最小的变量（min-domain）、影响最大的变量等。
• 值选择：选择最可能成功或影响最小的值。
• 重启：定期重启搜索并利用之前学习到的约束加快收敛。

第二部分：主流 CP 求解器全景图

目前最常用的 CP 求解器（或支持 CP 的框架）主要包括四大类：

重点选择：

• 如果您需要免费、性能强大、Python 接口友好的通用 CP 求解器，首选 CP-SAT。
• 如果您已经使用 IBM CPLEX 或需要专业的调度原生支持（区间变量、换型时间等），选择 CP Optimizer。
• 如果您希望用模型与求解器解耦、支持多种后端，选择 MiniZinc。
• 如果您追求中等规模调度最优解，或希望从 CP Optimizer 平滑迁移，OptalCP 是值得关注的选择。
• 如果您的问题包含大规模组合结构（如超大规模调度、路径优化、打包、聚类等）且希望开箱即用无需调参，那么 Hexaly 会成为您的最优利器。

在接下来的篇幅中，我们将重点介绍 CP Optimizer 和 OptalCP 的用法——它们与 APS 系统关系最密切。而 Hexaly 将以独立章节深度展开，因为它的设计理念和内在算法路径与典型的 CP 求解器大相径庭，却正在成为越来越多生产排程和供应链优化项目的首选方案。MiniZinc 则作为建模语言，在模型快速原型和多求解器比较测试场景中仍然具备不可替代的独特价值。

第三部分：CP Optimizer（IBM CPLEX）完全指南

3.1 快速开始

CP Optimizer 是 IBM CPLEX Optimization Studio 中的约束规划模块，不与 CPLEX MIP 求解器共享同一个内核，而是独立的 CP 引擎，专门优化了调度类问题。

安装 CPLEX Optimization Studio 后，通过 Python 使用：

from docplex.cp.model import CpoModel

model = CpoModel(name="scheduling")

3.2 核心概念：区间变量、序列变量、状态变量

CP Optimizer 在传统 CP 的整数变量基础上，增加了区间变量、序列变量和状态变量，使调度建模更自然。

3.3 高级调度约束

# 创建区间变量（可选）
task = model.interval_var(size=5, optional=True)

# 过渡时间矩阵（换型时间）
transition_matrix = [[0, 2, 3], [2, 0, 1], [3, 1, 0]]
model.no_overlap(seq, transition_matrix, 0) # 第一个参数是 sequence_var

# 累积资源
model.cumulative([task1, task2], [1, 2], capacity=3)

# 可选资源分配（每个任务从多个资源中选择一个）
model.alternative(task, [machine1_interval, machine2_interval])

# 并行任务同步（如多工序同时开始）
model.sync(task1, task2)

3.4 完整示例：带换型时间的流水车间

from docplex.cp.model import CpoModel

# 数据：3个产品，2台机器，换型时间矩阵
products = ['A', 'B', 'C']
setup_time = {
('A','A'):0, ('A','B'):2, ('A','C'):3,
('B','A'):2, ('B','B'):0, ('B','C'):1,
('C','A'):3, ('C','B'):1, ('C','C'):0,
}
processing_times = {'A': 5, 'B': 4, 'C': 6}

# 构造 transition matrix（序列变量所需格式）
setup_time_matrix = [[0, 2, 3], [2, 0, 1], [3, 1, 0]]

model = CpoModel()

# 为每个产品在每台机器上创建任务
tasks_m1 = {}
tasks_m2 = {}
for p in products:
tasks_m1[p] = model.interval_var(size=processing_times[p], name=f"M1_{p}")
tasks_m2[p] = model.interval_var(size=processing_times[p], name=f"M2_{p}")
# 工序顺序约束
model.add(model.end_before_start(tasks_m1[p], tasks_m2[p]))

# 机器 M1 序列，带换型时间
seq_m1 = model.sequence_var([tasks_m1[p] for p in products])
model.add(model.no_overlap(seq_m1, setup_time_matrix))

# 机器 M2 序列
seq_m2 = model.sequence_var([tasks_m2[p] for p in products])
model.add(model.no_overlap(seq_m2))

# 目标：最小化最大完工时间
makespan = model.max([model.end_of(tasks_m2[p]) for p in products])
model.add(model.minimize(makespan))

solution = model.solve()
# 输出结果…

3.5 CP Optimizer 的优势与局限

优势：

• 调度专用约束非常丰富，过渡时间、可选资源等天然支持
• 与 CPLEX 统一许可证，可混合 MILP+CP 建模
• IBM 企业级支持，文档详尽
• 搜索策略可高度定制（多阶段搜索、操作选择器）

局限：

• 商业软件，需要许可证（但提供学术免费版）
• 纯 Python API 性能略低于原生 C++，但对大多数问题足够
• 在某些组合优化问题（如不包含时间维度的纯逻辑约束）上，可能不如 CP-SAT 高效

第四部分：OptalCP——CP Optimizer 的现代化继任者

4.1 什么是 OptalCP？

OptalCP 由捷克理工大学（CTU）与 ScheduleOpt 公司联合开发，是一款专为调度场景设计的现代约束规划求解器。它并非从零开始的独立求解器，而是在继承 CP Optimizer 核心建模概念的基础上，针对性地解决了 CP Optimizer 长期存在的三个结构性缺陷：

• 多核利用率不足：传统 CP 求解器难以充分发挥现代多核 CPU 的计算能力；
• 下界信息利用不充分：求解器内部的界信息未能有效指导搜索方向；
• 与领域启发式结合困难：难以将业务经验转化为求解器可用的搜索引导。

OptalCP 通过全新的架构设计，在这三个方向上实现了系统性突破。在 2025 年发表于《Computers & Industrial Engineering》的基准研究中，OptalCP 在 332 个 JSSP 基准实例上的最优性证明率达到 57.5%，平均最优性间隙仅 3.55%，均优于 CP Optimizer 和 CP-SAT。不过在大规模工业实例（如 1000×1000）上，Hexaly 仍然凭借其组合启发式框架占据统治地位，贡献了 31 个新的已知最优上界。

OptalCP 的加速效果在学术界已得到验证。经过改进的失败导向搜索（FDS）结合多臂老虎机（MAB）算法后，在 JSSP 基准上比原始实现快 1.7 倍，比 IBM CP Optimizer 22.1 中的当前最先进 FDS 算法快 3.5 倍；在 RCPSP 上则分别快 2.1 倍和快 2.1 倍。

4.2 安装与环境配置

OptalCP 提供官方 Python 建模库 optalcp-py。对于已有 CP Optimizer 模型的用户，也可以使用兼容层 optalcp-cpo 实现无缝迁移。推荐新项目使用 optalcp-py，因为它更快、支持所有 OptalCP 特性且 API 更简洁。

安装步骤：

# 安装 optalcp-cpo 兼容层（包含 Python API）
pip install git+https://github.com/ScheduleOpt/optalcp-cpo.git

# 安装 OptalCP 二进制包（预览版免费，报告目标值但不输出解详情）
pip install git+https://github.com/ScheduleOpt/optalcp-py-bin-preview.git

若需要完整版（Academic / Full），请联系 OptalCP 官方并提供 GitHub 用户名，学术版本通常免费提供。使用 optalcp-cpo 后，只需将原有 docplex.cp 导入改为 optalcp_cpo.model 即可，无需修改其他代码。

4.3 快速入门：最小调度示例

以下代码展示 OptalCP Python API 的基本用法：

from optalcp_cpo.model import CpoModel

model = CpoModel()

# 创建两个任务
task1 = model.interval_var(size=10, name="Task1")
task2 = model.interval_var(size=20, name="Task2")

# 约束：Task1 结束后 Task2 才能开始
model.add(model.end_before_start(task1, task2))

# 目标：最小化完成时间
model.minimize(model.end_of(task2))

# 求解
result = model.solve(TimeLimit=10)

if result:
print(f"Objective: {result.get_objective_value()}")
else:
print("No solution found")

若需切换回 CP Optimizer 作为后端，只需在 solve() 方法中指定 agent='local'：

result = model.solve(agent='local', TimeLimit=10)

或通过全局配置更改默认后端：

from optalcp_cpo.config import context
context.solver.agent = 'local'

4.4 核心建模概念

OptalCP 的建模概念与 CP Optimizer 高度一致，熟悉 CP Optimizer 的开发者可以平滑过渡。其支持的核心建模元素包括：

常用约束：

# 基础约束
model.add(task1.end() <= task2.start()) # 先后顺序
model.add(task1.start() == 10) # 固定起始时间

# 可选任务
optional_task = model.interval_var(size=5, optional=True)
model.add(model.presence_of(optional_task)) # 强制该任务出现

# 序列约束（资源不重叠）
seq = model.sequence_var([task1, task2])
model.add(model.no_overlap(seq))

# 累积资源约束
model.add(model.cumulative([task1, task2], [1, 2], capacity=3))

# 可选资源分配
model.add(model.alternative(task, [machine1, machine2]))

4.5 完整示例：作业车间调度问题（JSSP）

以下是一个完整的 OptalCP Python 示例，求解作业车间调度问题：

from optalcp_cpo.model import CpoModel

def solve_jssp(nb_jobs, nb_machines, processing_times, machine_order, time_limit=60):
"""
使用 OptalCP 求解作业车间调度问题
processing_times[j][m]: 作业 j 在机器 m 上的加工时间
machine_order[j][k]: 作业 j 的第 k 道工序所在的机器编号
"""
model = CpoModel()

# 1. 创建任务变量（区间变量）
tasks = {}
for j in range(nb_jobs):
for m in range(nb_machines):
tasks[(j, m)] = model.interval_var(
size=processing_times[j][m],
name=f"J{j}_M{m}"
)

# 2. 同一作业内的工序优先约束
for j in range(nb_jobs):
for k in range(nb_machines – 1):
curr_machine = machine_order[j][k]
next_machine = machine_order[j][k + 1]
model.add(
model.end_before_start(tasks[(j, curr_machine)], tasks[(j, next_machine)])
)

# 3. 每台机器的作业顺序（序列变量 + 不重叠约束）
for m in range(nb_machines):
tasks_on_machine = [tasks[(j, m)] for j in range(nb_jobs)]
seq = model.sequence_var(tasks_on_machine)
model.add(model.no_overlap(seq))

# 4. 目标：最小化最大完工时间
last_job_tasks = [tasks[(j, machine_order[j][–1])] for j in range(nb_jobs)]
makespan = model.max([model.end_of(task) for task in last_job_tasks])
model.minimize(makespan)

# 5. 求解
result = model.solve(TimeLimit=time_limit)

if result and result.is_solution():
return result.get_objective_value()
else:
return None

# 示例数据：2个作业，2台机器
processing_times = [
[3, 2], # Job 0: 机器0需3，机器1需2
[4, 1] # Job 1: 机器0需4，机器1需1
]
machine_order = [
[0, 1], # Job 0: 先机器0后机器1
[0, 1] # Job 1: 先机器0后机器1
]

makespan = solve_jssp(2, 2, processing_times, machine_order, time_limit=10)
print(f"Makespan: {makespan}")

4.6 参数配置与调优

OptalCP 支持通过 solve() 方法传入求解参数：

# 时间限制（秒）
result = model.solve(TimeLimit=60)

# 并行线程数
result = model.solve(Workers=4, TimeLimit=60)

目前兼容层支持的求解参数包括 TimeLimit 和 Workers，其他参数（如 KPI、起点、多数求解器参数）会被接受但暂时忽略。

4.7 适用场景总结

OptalCP 与 CP Optimizer 概念一脉相承，但在并行计算、界利用和搜索策略上实现了质的飞跃。对于追求中等规模调度最优解或希望平滑迁移的场景，OptalCP 是值得深入探索的选择。

第五部分：Hexaly——后 MILP 时代的全局优化求解器

5.1 什么是 Hexaly？

Hexaly（原 LocalSolver）是一种新型的全局优化求解器。与传统 MILP 或 CP 求解器不同，Hexaly 不依赖传统的树搜索方式，而是采用了混合优化框架，融合了启发式搜索、精确方法、约束传播、自动列生成等多种技术，形成了一种被业界称为 “后 MILP 范式” 的全新求解路线。

Hexaly APIs 统一并扩展了混合线性规划、非线性规划和约束规划的建模概念。其建模接口是非线性的，面向集合（set-oriented），同时也支持用户自定义函数（黑盒优化）。

Hexaly 的底层融合了空间分支定界、单纯形法、内点法、自动 Dantzig-Wolfe 重表述、列生成与行生成、约束传播、局部搜索、群体方法和替代建模技术等多种优化手段。这种“组合拳”式的混合架构，使得 Hexaly 在面对大规模、强组合、非凸结构等问题时，展现出远超传统求解器的性能和扩展性。

5.2 为什么 Hexaly 值得单独关注？

在传统 CP 的世界里，变量类型局限于整数、布尔、区间等，求解器依赖的仍然是分支定界和约束传播。但当问题的离散决策变量以指数级增长（例如，车辆路径问题中在数千个点之间选择访问顺序），传统分支定界树的规模会迅速失控，无法在合理时间内收敛。

Hexaly 带来了四个根本性的突破：

第一，非线性且面向集合的建模 API。它支持 set 变量、list 变量等集合类型的直接声明，使得“排列”“分组”“分区”这类组合概念可以用几行代码天然表达，而不需要膨胀成海量的 0-1 变量和 Big-M 约束。

第二，开箱即用的模型设计，零调参。用户声明完约束、目标函数和变量类型后，Hexaly 内部会自动选择合适的启发式、局部搜索和精确方法组合进行求解。

第三，同时提供对偶界（dual bounds）。Hexaly 不仅能够快速找到高质量可行解，还能通过内部的列生成、能量松弛等机制，计算出当前解离最优解的理论下界，从而提供类似 MILP 解所带的“间隙（Gap）”指标，这在纯粹的启发式算法中是不常见的。

第四，超大规模实例上的统治级表现。在作业车间调度问题（JSSP）1,000 个作业 × 1,000 台机器（总计 100 万道工序）的超大规模实例上，Hexaly 在 60 秒内即可将业界已知最优解平均提升 7.4%，而其他传统 CP 或 MILP 求解器甚至无法在此规模下产出任何可行解。在资源约束项目调度问题（RCPSP, 300 个任务规模）上，Hexaly 在 1 分钟内可达成平均 2.0% 的间隙；在简单装配线平衡问题（SALBP）上，Hexaly 在 1 分钟内的平均间隙仅为 0.2%。对于物流路径优化问题，Hexaly 求解带有容量约束的车辆路径问题（CVRP）的速度比主流商业求解器快 10~100 倍。

5.3 Hexaly 安装与验证

Hexaly 支持 Python 2.7 和 Python ≥ 3.4。使用 pip 在线安装 Python 接口：

pip install hexaly -i https://pip.hexaly.com

⚠️ 注意：上述命令仅配置了 Hexaly 在 Python 中的集成，还需在 Hexaly 官网 注册并获取许可证（提供一个月免费试用和免费学术许可）。

验证安装：

import hexaly.optimizer
print(hexaly.optimizer.get_license_info()) # 输出版本和许可信息

5.4 Hexaly 核心建模概念

Hexaly 的 API 极为轻量，主要围绕 HexalyOptimizer 环境、model 对象以及表达式构建。

5.4.1 决策变量类型

Hexaly 原生支持多种决策变量类型，覆盖了从传统优化到复杂组合问题的所有需求：

5.4.2 表达式与操作符

Hexaly 支持几乎完整的数学表达式，包括加减乘除、幂、开方、取模、三角函数、对数指数、逻辑运算等，约束可以直接表达为非线性表达式，无需线性化近似。

5.4.3 一个完整的最小示例：最优水桶（非线性优化）

以下是一个经典的 Hexaly 入门示例，演示了如何用极少的代码构建一个非线性优化模型——在给定材料表面积（π）的条件下，最大化水桶的体积。

import hexaly.optimizer
import sys

with hexaly.optimizer.HexalyOptimizer() as optimizer:
PI = 3.14159265359

# 声明优化模型
m = optimizer.model

# 决策变量：上底半径 R，下底半径 r，高度 h
R = m.float(0, 1)
r = m.float(0, 1)
h = m.float(0, 1)

# 表面积约束：侧面积 + 底面积 ≤ π
surface = PI * r ** 2 + PI * (R + r) * m.sqrt((R – r) ** 2 + h ** 2)
m.constraint(surface <= PI)

# 目标：最大化体积
volume = PI * h / 3 * (R ** 2 + R * r + r ** 2)
m.maximize(volume)

m.close()

# 设置时间限制（秒），默认为 2 秒
optimizer.param.time_limit = 2
optimizer.solve()

print(f"Volume = {volume.value:.4f}")
print(f"R = {R.value:.4f}, r = {r.value:.4f}, h = {h.value:.4f}")

5.5 生产排程实战：Hexaly 在作业车间调度（JSSP）中的应用

作业车间调度问题（JSSP）是生产排程中最经典的 NP-Hard 问题之一。以下是一个完整的 Hexaly 模型，展示如何使用区间变量和列表变量对 JSSP 进行简洁建模。

import hexaly.optimizer

def solve_jssp(nb_jobs, nb_machines, processing_time, machine_order, time_limit=60):
"""
使用 Hexaly 求解作业车间调度问题（最小化最大完工时间）
processing_time[j][m]: 作业 j 在机器 m 上的加工时间
machine_order[j][k]: 作业 j 的第 k 道工序所在的机器编号
"""
with hexaly.optimizer.HexalyOptimizer() as optimizer:
m = optimizer.model

# 1. 区间决策变量：每道工序的时间区间
max_start = sum(processing_time[j][m] for j in range(nb_jobs) for m in range(nb_machines))
tasks = [[m.interval(0, max_start) for _ in range(nb_machines)] for _ in range(nb_jobs)]

# 2. 持续时间约束
for j in range(nb_jobs):
for mch in range(nb_machines):
m.constraint(m.length(tasks[j][mch]) == processing_time[j][mch])

# 3. 工序优先顺序约束（同一作业内的先后顺序）
for j in range(nb_jobs):
for k in range(nb_machines – 1):
m.constraint(tasks[j][machine_order[j][k]] < tasks[j][machine_order[j][k+1]])

# 4. 机器资源约束（每台机器上的作业不重叠）：使用列表变量
jobs_order = [m.list(nb_jobs) for _ in range(nb_machines)]

for mch in range(nb_machines):
m.constraint(m.count(jobs_order[mch]) == nb_jobs) # 每个作业在每台机器上恰好出现一次
# 用 lambda 表达式声明列表元素之间的先后顺序约束
m.constraint(m.and_([tasks[jobs_order[mch][i]][mch] < tasks[jobs_order[mch][i+1]][mch]
for i in range(nb_jobs–1)]))

# 5. 目标：最小化最大完工时间
makespan = m.max([m.end(tasks[j][machine_order[j][–1]]) for j in range(nb_jobs)])
m.minimize(makespan)

m.close()

# 设置求解参数
optimizer.param.time_limit = time_limit
optimizer.param.verbosity = 1 # 日志详细程度

# 求解
optimizer.solve()

if optimizer.solution.is_feasible():
return makespan.value
else:
return None

这个模型在 1,000 个作业 × 1,000 台机器的超大规模实例上，Hexaly 能在 60 秒内产出高质量解，而传统的 CP Optimizer、OR-Tools CP-SAT、Gurobi 和 CPLEX 都无法在相同时间内获得任何可行解。

5.6 车辆路径问题（CVRP）的 Hexaly 建模示例

在车辆路径问题中，列表变量天然地对应每辆车的访问顺序：

def solve_cvrp(nb_vehicles, nb_customers, demands, capacity, distance_matrix):
with hexaly.optimizer.HexalyOptimizer() as optimizer:
m = optimizer.model

# 每辆车的访问顺序（列表变量）
tours = [m.list(nb_customers) for _ in range(nb_vehicles)]

# 分区约束：每个客户恰好被分配给一辆车
for v in range(nb_vehicles):
m.constraint(m.partition(tours[v])) # 分区约束确保每个元素恰好出现一次

# 容量约束：每辆车的总需求不超过容量
for v in range(nb_vehicles):
load = m.sum([demands[c] for c in tours[v]])
m.constraint(load <= capacity)

# 目标：最小化总路程
total_distance = m.sum([m.sum([distance_matrix[tours[v][i]][tours[v][i+1]]
for i in range(nb_customers–1)])
for v in range(nb_vehicles)])
m.minimize(total_distance)
m.close()

optimizer.param.time_limit = 60
optimizer.solve()

return total_distance.value

第六部分：Hexaly 对比 CP Optimizer、OptalCP 与 CP-SAT

6.1 性能基准：大规模调度问题上的压倒性优势

6.2 学术基准：CP 求解器综合对比（2025-2026 最新研究）

在一项 2026 年发表的覆盖 332 个 JSSP 基准实例的综合评估中，四个主流 CP 求解器的表现如下：

关键结论：在 工业级大规模问题（如 1,000×1,000 矩阵）上，Hexaly 占据统治地位；OptalCP 在中等规模实例上的最优性证明能力最强；而求解器的竞争力高度依赖于问题规模与结构。

6.3 综合对比表：CP Optimizer vs CP-SAT vs OptalCP vs Hexaly vs CPLEX

第七部分：选型决策框架

基于前面对于 Hexaly、CP Optimizer、OptalCP、CP-SAT 等工具的深入讲解，我们建立一个清晰的 “问题特征 → 推荐求解器” 的映射表，方便你在实际项目中进行快速选择：

第八部分：综合资源

结语

约束规划为组合优化问题提供了与 MILP 互补的强大范式。

Hexaly 的核心定位：它不是要替代 CPLEX 或 Gurobi 处理线性/凸二次问题的角色，而是专注于那些迫使传统求解器“模型膨胀”的超大规模组合问题。在生产排程、路径优化、设施选址、供应链网络设计等领域，Hexaly 凭借其面向集合的建模能力和混合求解引擎，正在迅速成为业界首选。

OptalCP 的核心定位：它与 CP Optimizer 概念一脉相承，但在并行计算、界利用和搜索策略上实现了质的飞跃。对于追求中等规模调度最优解或希望平滑迁移的场景，OptalCP 是值得深入探索的选择。

在 APS 系统中，合理的策略可以是 CP-SAT / CP Optimizer 处理中小规模调度与逻辑约束，OptalCP 优化中等规模调度的最优解质量，Hexaly 接管超大规模组合优化部分，并通过数据交换实现混合求解。掌握 CP-SAT、CP Optimizer、OptalCP 和 Hexaly 四种不同的工具，将使你在面对真实世界中千变万化的生产排程、路径规划与组合优化问题时，始终保持选择最佳工具的能力。