什么是柔性车间作业调度参考 遗传算法求解柔性车间调度问题CP-SAT在之前的文章中我们使用遗传算法求解，这篇文章会尝试用CP-SAT求解。CP-SAT的相关内容参考 运筹优化工具ortools解读与实践-ortools求解CP问题数学建模集合与索引\(J\): 作业集合，\(j \in J\)\(O_j\): 作业\(j\)的操作集合，\(o \in O_j\)\(M\): 机器集合...

车间调度问题，也称为作业车间调度问题，其核心目标是：在满足一系列约束条件的前提下，为一系列工件在多台机器上的加工安排一个最优的时间表（调度方案）。

运筹优化求解算法可以大体分为两类，精确求解和近似求解。其中，精确求解算法包括了单纯形法、梯度法、动态规划法、分支定界法等；近似求解算法包括了遗传算法、粒子群算法、近似搜索、大规模邻域搜索等。遗传算法就属于后者。

美团配送2022KDD论文：Applying Deep Learning Based Probabilistic Forecasting to Food Preparation Time for On-Demand Delivery Service

菜鸟网络2022KDD论文：Graph2Route: A Dynamic Spatial-Temporal Graph Neural Network for Pick-up and Delivery Route Prediction

美团配送2021KDD论文：A Deep Learning Method for Route and Time Prediction in Food Delivery Service

高清版本在这里

假设一家出租车公司有四个客户在等车，四个出租车司机(工人)可以接他们，任务是给每个客户分配一名司机去接他们。任务的成本是司机接一个特定客户所花费的时间。问题是，如何将司机分配给客户，以最小化总等待时间。

上一篇文章我们介绍了CP-SAT的简单用法，以及CP-SAT包含的不同变量、约束函数。实践出真知，本篇文章将用几个例子加深对CP-SAT使用的理解。

如前文所说，约束规划（CP）指求解满足各项约束的可行解的问题。与线性规划、整数规划不同，约束规划更加关注可行解，没有明确的优化目标。典型的场景包括员工排班问题、N皇后问题。CP问题虽然没有目标函数，但可以通过目标添加到约束的方式缩小到更易于管理的子集，变相解决整数规划问题。

MPSolver接口：ortools提供一个名为MPSolver的接口，实现了对众多LP、MIP第三方求解器的封装，其中也包含了google自研的线性规划求解器Glop。

公司有一个由10辆车组成的车队，从仓库出发为100家企业配送物资，每家企业都有不同的收货时间窗口，物资体积、重量也各不相同，同时，车辆有其最大载容、载重及最大行驶距离。如何做车辆与企业匹配和路径规划，能够满足要求的同时最小化成本？