本文将详细介绍一下Milk Collection Problem（牛奶收集问题）的数学模型，并给出其python的代码实现，其中调用了gurobi求解器，并采用了懒惰约束的方式。由于python与matlab两种方式在使用懒惰约束方式的不同之处，在前两期文章中已经介绍过了，都是callbacks函数和数据结构的不同，因此本文没有采用matlab这一效率较低的实现方法。
一、Milk Collection Problem介绍
这一部分将详细介绍介绍一下这个问题和数学模型，以及笔者在学习这一问题时的心得。
（1）问题原描述：一家小型牛奶加工公司致力于从20个农场收集牛奶并将其带回仓库进行加工。该公司拥有一辆罐车，可运载80 000升牛奶。其中11个农场很小，每隔一天才需要收集一次。其他九个农场每天都需要收集。下表列出了农场相对于仓库（编号 1）的位置及其收集要求。
目标是每天为油罐车找到最佳路线，同时必须满足以下要求：
①访问那些需每天访问的农场；②以合理方式安排访问那些需每隔一天访问一次的农场；③满足容量限制。
（2）问题的进一步理解：实际上我们总共有21个位置点，其id为0~20，其中仓库的id为0，需每天访问的农场（后面称Every day农场）的id为1~9（共9个），需每隔一天访问一次的农场（后面称Every other day农场）的id为10~20（共11个）。我们只有1个罐车，其容量为80kL（与表中的单位统一）。我们现在要为这辆罐车设计一条路线，使其从仓库出发，经过某些农场，再回到仓库。我们注意到，农场分为两类，Every other day农场必然每一天都被访问，而对于Every day农场来说，如果前一天没有被访问，则第二天必然被访问，这也意味着，我们必须将日期分为两类，相邻的两天属于不同类，中间隔一天的两天为同一类，假设日期分为“1类”和“2类”，则要合理安排部分Every other day农场在1类日期被访问，其余Every other day农场在2类日期被访问。我们的目标就是为这两类日期分别设计一条路线，使得其在不超过容量限制且满足前文所说的农场访问需求的情况下，使两类日期的平均路线最短。
（3）符号约定
i,j∈Farms={0,1,2,...,20}:Farms为各位置点，其中0为仓库，1~9为Every day农场，10~20为Every other day农场。
everyDay={1,2,3,...,9}⊂Farms:表示Every day农场的集合。
otherDay={10,11,12,...,20}⊂Farms:表示Every other day农场的集合。
k∈K={1,2}:表示日期的分类，日期分为1类和2类
Edges={(i,j)∈Farms×Farms}:所有位置点全连接组成的边集。
Sk∈S:k类日期的路径的所有子路径组成的集合。
G=(Farms,Edges):位置点及所有边组成的图。
di,j∈R+:i点与j点之间的距离（di,j=dj,i）
C∈R+:罐车的容量
Ri∈R+:农场i的收集需求
（4）决策变量
因为日期因为Every other day农场的关系被分为了两类，所以我们需要考虑每类日期访问哪些农场，还要考虑每类日期访问这些农场的顺序。
yi,k∈{1,2}, i∈otherDay, k∈K:在k类日期是否访问i点
xi,j,k∈{0,1}, i,j∈Farms, k∈K:在k类日期如果罐车访问i点且访问j点且i点和j点在路径上是相邻的话，则次变量取值为1；否则取值为0。
（5）目标函数
目标是最小化这两类日期的平均总路径长度，但其实如果不乘那个1/2对求解也没影响。
（6）约束条件
①Symmetry Constraints约束：
j点和i点的相连情况必然与i点和j点的相连情况相同。
②Entering and leaving an every day farm约束：
对于Every day农场来说，在访问路径上必然与另外两个位置相邻。
③Entering and leaving an every other day farm约束：
对于Every other day农场来说，如果要访问的话则在访问路线上必然与另外两个位置相邻，如果不访问则在访问路径上没有相邻的点。
④Tanker capacity约束：
每天收集的牛奶量不能超过油罐车的容量。这里我们可以看到，Every day农场由于每天都要被收集，其每天需收集的总牛奶量是固定的，所以可以直接算出来一个常数，而只有Every other day农场每天收集的总牛奶量会变动。
⑤Farms visited约束：
确保Every other day类型的农场每隔一天访问一次。
⑥Subtour elimination约束：
子回路消除约束。
二、python代码实现
（1）数据初始化
我们采用题目中给的数据，没有引入数据文件。tuplelist和tupledict类型的数据为我们提供了便利。我们还要根据坐标来求的两两位置点之间的距离，由于combinations函数的使用，结果相比距离矩阵来说，去掉对角线，剩下的只取一半。
（2）决策变量
在创建决策变量时应用了tuplelist和tupledict两种更加高效灵活的数据结构。其中的x没有定义“自己到自己”的决策变量，从根本上避免了求解结果中出现“自己到自己”的情况。
（3）约束条件（不包括子回路消除约束）
约束条件的设置与前文基本相同，不过Symmetry Constraints约束没有用到约束语句，而是用了gurobi更方便的语法。里面还有个消除对称约束，要知道最优解必然有对称的两个，以id为11的农场为例，要么k为1的时候访问，要么k=2的时候访问，这里其实就是说只取其中一种的意思。
（4）目标函数
目标函数中没有加那个1/2。
（5）子回路消除（懒惰约束实现过程）
callbacks函数，用户可以灵活指定约束增加的时机。每一次迭代出新解，即可检查子圈情况，如果出现子圈则增加破圈约束，这样能大大节省求解时间。这里的subtourelim函数即为本次使用的callbacks函数，where参数取值为MIPSOL，表示callbakcs函数的触发点是发现新的解时。subtourelim函数是一个用来找到最短的子回路的方法，每当找到这个子回路，加入破除这个子回路的约束。
三、代码链接
https://github.com/BDLab206/blog_code/blob/Gurobi_milk_collection_problem/python_Gurobi_milk_collection_problem
作者：段新龙
