一、Lost Luggage Distribution Problem介绍
这一部分详细介绍介绍一下这个问题以及笔者在学习这一问题时的心得，对于这个问题比较了解的大佬可直接跳转到第二部分。
（1）问题原描述：一家拥有六辆面包车的小公司与多家航空公司签订了合同，每天晚上 6 点从希思罗机场领取属于伦敦地区客户的丢失或延误的行李。合同规定，每位乘客必须在晚上 8 点之前交付行李。该公司需要一个模型来告知他们需要使用的最小货车数量，以及每辆货车应该交付给哪些客户以及以什么顺序交付。每辆面包车没有实际容量限制。每辆面包车可以容纳需要在两小时内交付的所有行李。为了解决这个问题，我们可以制定一个优化模型，最大限度地减少需要使用的货车数量。
（2）问题抽象描述：假设有K辆交通工具（后面称“货车”），有n个位置点，其中机场（后面称“原点”）的id为0，id从1到（n-1）的点均为客户点。多辆货车每天在T1时从原点同时出发，在T2时之前须保证每个客户点被一辆货车访问过，即在（T2-T1）的时间限制内完成访问，货车无容量限制。现需要确定要使用的货车数，每辆货车要访问哪些客户点以及访问的顺序，建立一个优化模型，最大限度减少货车的使用数量。
（3）集合及参数
i, j ∈ Locations ≡ L = {0, 1, 2, ..., (n-1)}:L为位置点的集合，0为原点的id，客户点的id为1到(n-1)
k ∈ Vans ≡ V = {0, 1, 2, ..., (K-1)}:V为货车的集合
Sk ∈ S：货车k访问的位置点的集合，为L的子集
ti,j ∈ R+:从位置点i到位置点j所需花费的时间
（4）决策变量
对决策变量的介绍，笔者决定以“z->y->x”的顺序来介绍，三种变量也正对应着思考这一问题的三个步骤，笔者首先是从满足客户点访问的要求的角度思考的，即“用哪几辆车”->“每辆车访问哪些点”->“每辆车访问这些点的顺序是什么”的三个步骤，然后再引出目标函数。
①用哪几辆车，即每辆车是否要出动
zk ∈ {0, 1}:货车k是否被用，如果使用则zk=1，否则zk=0
很明显，这组变量的规模是"K"，因为总共有K辆货车，同时这也是和目标函数直接相关的一组变量。
②每辆车访问哪些点
yi,k ∈ {0,1}:如果货车k访问位置i，则yi,k=1，否则yi,k=0
有两点值得思考：一是被使用的货车一定是要经过原点的，因为每辆货车都是从原点出发再回到原点；二是yi,k与zk之间存在联系，对于每个k来说，只有当zk为1时，yi,k才有可能为1。这组变量的规模是“K*n”，因为要讨论每辆车是否要访问每个点。
③每辆车访问这些点的顺序是什么
xi,j,k ∈ {0,1}:如果货车k访问完位置i后直接移动到位置j并访问，则xi,j,k=1，否则xi,j,k=0。
对于每辆车来说，如果确认了需要访问哪些点的话，则接下来相当于是要解一个类TSP问题了，即在包括原点的各个需要访问的点中找到一条最优路径，当然，实际求解过程不是这样分步解的，但这样可以方便我们理解。这里需要注意xi,j,k与yi,k之间存在关联，具体到后面约束条件再详细讲解。这组变量的规模是"K*n*n"。
这三组0-1决策变量的设计是非常考究的、层层递进的，完美地体现了这个问题的‘“所有”变数，对于后续我们自己建立数学模型有很大启发。
（4）目标函数
目标函数实际上非常简单，就是使使用的货车数最小，那其另外两组决策变量x和y是干什么用的呢？按照笔者粗浅的理解，如果另两组变量想起到作用，一定是通过约束条件，对z产生了制约，详见约束条件部分。
（4）约束条件
①Van utilization约束：
对于0-1变量来说，这种"≤"的约束有两层含义：一是如果yi,k=1，则zk则必然为1，即如果某辆车访问了某点，则这辆车一定被使用；二是如果zk=0，则yi,k必然为0，即如果某辆车没被使用，则这辆车不能访问任何点。
值得注意的是，理论上这个约束是要包括原点的，这里却要删去对原点的约束，笔者最初百思不得其解，但后面笔者会给出原因及数学证明。
②Depot约束：
笔者之所以将Depot约束放到第二的顺序来讲，是因为这前两个约束都是在讲y和z之间的互相制约关系。
这个约束的含义是，原点必须被每个使用过的货车访问，但直观思考出来的约束应当是：
y0,k≥zk，∀k∈K
即如果k被使用，即zk=1，则强制y0,k也为1。但Depot约束却写成了求和的形式，这也同样使笔者百思不得其解，思考这样会不会使y0,k的值产生混乱，但后面笔者对于这样不会混乱会给出数学证明。
③Visit all customers约束：
这个约束是针对y的约束，表示每一个客户点都必须被访问过且只能被访问一次。
④Arriving at a location约束：
对于0-1变量来说，这种“左边多个0-1变量加起来=右边的0-1变量”的约束，有两层含义：一是如果yj,k=0，则左边所有的xi,j,k都是0；二是如果yi,k=1，则左边所有xi,j,k中只有一个为1且其它均为0。
这个约束的含义是每个位置点只能被某辆车从唯一1个访问完的位置点移动到这个位置点并访问。
⑤Leaving a location约束：
这个约束的含义是每个位置点被某辆车访问完离开后只能前往唯一1个位置点。
约束④和约束⑤都是在讲x和y之间的关系。
⑥Travel time约束：
约束⑥是针对x的约束，表示每辆车的行驶时间不能超过规定的时长。
需要注意的是，这其中不包括从最后一个客户点到原点那一段路程所花费的时间，通俗理解就是，当某辆车拿到最后一个客户点的行李后，可以慢悠悠地开回到原点，反正行李都拿到了，晚回来点可以被允许。
⑦Breaking symmetry约束：
这个约束保证了结果的有序性，笔者曾做了个实验，删去这一约束进行求解，对结果的影响仅为货车使用顺序不同，因此笔者不展开讲这一约束。
⑧Subtour elimination约束：
了解TSP问题的小伙伴们肯定了解子回路消除这一约束，求解过程中会出现子回路，显然不符合我们的实际需要，因此要加入一组子回路消除的约束，由于约束数量随求解规模指数型增长，无法枚举，因此必须引入懒惰约束来求解，而matlab与python两种方式在这个方面又有着明显不同，后续会重点详细讲解。
综上，约束条件已讲解完毕，数学模型也介绍完了，但对于约束①和约束②是否对y0,k的值产生有效约束（举个反例，假如只用了前三辆车，但y0,1=0，y0,4=1，这仍不与约束①和②矛盾，y值的混乱可能会对x以及最后结果都有影响）的问题，笔者给出了如下的数学证明，感兴趣的小伙伴可以看看，可以与笔者交流想法。
二、matlab与python代码实现及对比
（1）数据初始化
我们所使用的算例文件均为vrp文件，每个点给出了坐标，需要用坐标来计算两两位置点之间的距离，并假设速度为单位速度，从一个点到另一个点所花费的时间在数值上与这两点之间的距离相同。
matlab使用了两个转化函数，将tsp文件中的关键信息存储到一个结构体中，这个结构体中包含了位置点个数、距离矩阵等数据，用于后续计算，这两种数据都是以矩阵的形式参与运算。
python可以使用load函数直接读取tsplib95库中包含的所有类型的文件（包括tsp类型的文件），因此获得文件中的关键信息比较方便，不需要自己再编写函数。位置点的id以列表的形式来参与运算，但城市两两之间所花费的时间（距离）以字典的形式参与运算，键为由两个城市id组成的元组，值为两城市间花费的时间（距离）。需要注意的是，字典中不包含原距离矩阵中的对角线上的距离。
（2）决策变量
matlab是基于矩阵的，其创建了3组0-1决策变量，涵义与前文相同。
python在创建决策变量时应用了tuplelist和tupledict两种更加高效灵活的数据结构。其中的x没有定义“自己到自己”的决策变量，从根本上避免了求解结果中出现“自己到自己”的情况。与matlab不同的是，它为每辆车的行驶时间引入了一个松弛变量 tk和一个最大行驶时间s。
（3）约束条件（不包括子回路消除约束）
matlab对约束条件的设置与前文的介绍基本相同。
pyhton的时间约束，应用了松弛变量，其它基本相同。
（4）目标函数
matlab的目标函数很简单，使z最小。
python用到了两个分级目标，首先是货车数最小，其次是最小化最大时间。
（5）懒惰约束实现流程
懒惰约束实现流程的差异是两者之间最大的差别，也是最能影响求解时间的因素。
matlab在由于没有callbacks功能，所以在实现懒惰约束时是比较死板的，其基本思路是：不加入破除子圈约束，直接求解，根据得到的最优解的子圈情况来加入相应的破圈约束，并再次求解，循环上述流程，直到得到的最优解没有子圈 。这样做最大的弊端是，每次都要求出最优解后，才能根据最优解的子圈情况来增加约束，而不是每次迭代就根据新解来加入约束，这样会浪费较多的时间。
python则灵活的多，通过callbacks函数，用户可以灵活指定约束增加的时机。每一次迭代出新解，即可检查子圈情况，如果出现子圈则增加破圈约束，这样能大大节省求解时间。这里的subtourelim函数即为本次使用的callbacks函数，where参数取值为MIPSOL，表示callbakcs函数的触发点是发现新的解时。subtourelim函数是一个用来找到最小的子回路的方法，每当找到这个子回路，加入破除这个子回路的约束。
（6）求解时间对比
由上表可知，python的求解效率比matlab要高，甚至当求解规模比较大时，matlab会出现时间过长的影响。究其原因，最主要是因为python可以实现callback，大大减少了无用功的投入。总体上来说，python对于懒惰求解的应用比matlab更灵活方便，求解效率也更高， 所以更加适合进行懒惰约束相关的运算求解。
三、代码链接
matlab版本代码链接：https://github.com/BDLab206/blog_code/blob/Gurobi_lost_luggage_distribution/matlab_Gurobi_lost_luggage_distribution
python版本代码链接：https://github.com/BDLab206/blog_code/blob/Gurobi_lost_luggage_distribution/python_Gurobi_lost_luggage_distribution
作者：段新龙
