相信大家对线性规划和整数规划应该不陌生，在开始今天的问题之前我们不妨再来复习一下这两个概念，毕竟温故而知新嘛

线性规划与整数规划

线性规划是这样定义的：

求解线性规划问题的基本方法是单纯形法，后来又有改进单纯形法、对偶单纯形法等。而整数（线性）规划则是在线性规划的基础上增加了整数约束：

整数规划又可以大致分为几类：

1. 纯整数规划：所有的决策变量都要求为整数
2. 混合整数规划：部分决策变量要求为整数
3. 纯0-1整数规划：所有决策变量均要求为0或1
4. 混合0-1整数规划：部分决策变量要求为0或1

通过对比可发现，两种规划的不同之处在于整数规划增加了整数约束，在不考虑整数约束的情况下得到的是整数规划的线性松弛模型。整数规划的应用非常广泛，例如背包问题、选址问题、旅行商问题、车辆路径规划问题等等。整数规划问题常见的解法有割平面法和分支定界法，一些求解器也主要运用分支定界法来求解此类问题。

不知道大家平时有没有被老师问过下面的问题：

你觉得线性规划问题和整数规划哪个求解速度更快呀？快多少？

有的小伙伴的表情可能是这样的

但是没关系，今天我们来解个问题试试看不就知道了。既然是要对比这两种规划问题的求解速度，那当然得找一个有线性松弛解的整数规划问题咯。没错，它就是---

带时间窗约束的车辆路径规划问题

按照惯例我们先要介绍一下这个问题，具体可以参考我们之前的这篇文章“ 干货|十分钟快速掌握CPLEX求解VRPTW数学模型（附Java代码及CPLEX安装流程） ”

“

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

时间窗就是一种约束，车辆除了要满足VRP问题的限制之外，还必须满足需求点的时间窗约束（例如服务只能在早上八点到十点之间开始），而需求点的时间窗限制可以分为两种，一种是硬时间窗（Hard Time Window ），硬时间窗要求车辆必须要在时间窗内开始服务客户，早到必须等待，而迟到则拒收；另一种是软时间窗（Soft Time Window ），不一定要在时间窗内开始服务，但是在时间窗之外开始服务的话会受到处罚，以处罚替代等待与拒收是软时间窗与硬时间窗最大的不同。

”

问题模型如下：

这个问题模型本身是带有整数规划的，求解的方法在上面也有一些介绍。我们可以借助求解器例如CPLEX来帮助我们完成这个过程。然后我们再用相同的算例来求解这个模型的 线性松弛解 作为对比。小编是在Eclipse上用JAVA语言调用的接口。具体的操作说明可以参考上述的推文也可以在参考官网https://www.ibm.com/support/knowledgecenter/zh/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/homepages/usrmancplex.html

算例使用的是solomon的算例（C101、扩展算例C1_2_5），在C101中分别取前10、15、20、25、30、35、40、45、50、55、60、65、70、75、80、85、90、95、100个点；在C1_2_5中分别取前10、15、20、25、30、35、40、45、50、55、60、65、70、75、80、85、90、95、100、105个点进入模型求解，在得到最优解的条件下，记录求解的时间。

算例C101的求解结果如下

算例C1_2_5的求解结果如下：