前言

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

取送货车辆路径问题是对传统车辆路径问题的扩展，可简要描述如下：在某个供求系统中，有若干个取货节点和送货节点（有些节点既是取货节点也是送货节点），在货物取送量、最大车载量、最长行驶时间等约束条件下，合理安排客户的访问次序和货物取送量，把客户需求的货物从取货节点运送至送货节点，并实现所需车辆数最少、行驶距离最短、总运输成本最少等优化目标。

本书研究了供需未匹配多商品取送货车辆路径问题。在此问题中，客户点之间的供需匹配关系事先未知；每个客户点的取货需求和送货需求必须被满足；需要做供需匹配决策和车辆路径决策。本书在供需匹配关系未知的情况下，研究了在单次访问和多次访问情况下供需未匹配的多商品取送货车辆路径问题。

本书所研究的问题是经典的车辆路径问题的一种复杂衍生体，普遍存在于国际原油运输、烟草制造行业中生产原料调拨、零售行业的商品库存重新布局及共享单车系统的自行车重新分配等网络中。问题高度复杂且受到的关注较少，因此本书分别从模型构建、问题特性分析、启发式算法设计和精确算法设计、数值测试的角度对所研究问题进行深入研究。本书的主要研究成果如下：

（1）多次访问条件下的供需未匹配多商品取送货车辆路径问题模型构建与问题特性分析方面：首先，借鉴相关文献的研究成果，建立一个混合整数线性规划模型作为基础模型。其次，为消除决策变量之间的耦合关系，提出了一个单元化思想以拆分顶点，进而建立了一个单元化数学模型。再次，提出了6类多项式型有效不等式来加强单元化模型构建。最后，基于数值实验验证了单元化模型相对基础模型具有明显的优势（需要较少的决策变量），以及本书提出的有效不等式可显著提高模型的性能。

（2）多次访问条件下的供需未匹配多商品取送货车辆路径问题启发式算法设计方面：为快速求解现实中常见的较大规模的问题，基于本书提出的模型，首先，设计一个贪婪式算法来构建初始解。其次，基于优化供需匹配决策和车辆路径决策的思想，提出高效的邻域结构。再次，提出一个禁忌搜索算法来改善初始解的质量。最后，为验证该算法的效果，借助CPLEX ^[1] 设计求解问题下界的方法。实验结果表明，本书提出的禁忌搜索算法在较短时间内能够对所研究的问题提供最优或近似最优解。

（3）多次访问条件下的供需未匹配多商品取送货车辆路径问题精确算法设计方面：为针对现实中中小规模的问题求出最优解，首先，基于单元化模型具有的优势，建立一个更简便的数学模型。其次，提出2类新的多项式型有效不等式和6类指数型有效不等式来加强模型。再次，针对每类指数型有效不等式设计了相应的分离算法。最后，基于初始上界选取、预处理操作、分支策略和分离算法调用策略的深入讨论，设计了一个分支切割算法。实验结果表明，本书设计的分支切割算法在规定时间内能够求解9个客户和5种商品的算例，且在求解规模、求解时间和上下界值方面相对优化软件CPLEX均具有明显优势。

（4）单次访问条件下的供需未匹配多商品取送货车辆路径问题模型构建与问题特性分析方面：首先，借鉴相关文献的研究成果，通过采用更简便的方式来表示“服务次序约束”和“装卸约束”，以建立一个更简便的混合整数线性规划模型。其次，基于对问题特性的深入分析，提出了6类多项式型有效不等式来加强模型构建。最后，基于数值实验验证了本书提出的改进模型具有明显的优势（求解性能提高），以及本书提出的有效不等式可显著提高模型的性能。

（5）单次访问条件下的供需未匹配多商品取送货车辆路径问题启发式算法设计方面：为快速求解现实中常见的较大规模的问题，基于本书提出的模型，首先，设计一个基于运输效率提升的贪婪式算法来构建初始解。其次，基于优化供需匹配决策和车辆路径决策的思想，对已有的相关邻域结构进行整合改进，进而提出一个改进的变邻域搜索算法来改善初始解的质量。最后，为验证该算法的效果，借助CPLEX设计求解问题下界的方法。实验结果表明，本书提出的改进的变邻域搜索算法在较短时间内能够对所研究的问题提供最优或近似最优解，且在求解质量和求解效率方面均优于文献中已有变邻域搜索算法。

（6）单次访问条件下的供需未匹配多商品取送货车辆路径问题精确算法设计方面：为针对现实中中小规模的问题求出最优解，首先，基于前面建立的数学模型，通过松弛一些较松弛的约束来建立一个容易求解的数学模型。其次，基于对问题特性的深入分析，提出3类指数型有效不等式来加强模型。再次，针对每类指数型有效不等式设计了相应的分离算法。最后，基于初始上界选取、预处理操作、分支策略和分离算法调用策略的深入讨论，设计了一个分支切割算法。实验结果表明，本书设计的分支切割算法在规定时间内能够求解10个客户和6种商品的算例，且在求解规模和求解时间方面均优于优化软件CPLEX。

[1] CPLEX是一种数学优化技术，主要用于提高效率、快速实现策略并提高收益率。