前言

车辆路径问题（Vehicle Routing Problem，VRP）由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自拥有不同数量的货物需求，一个车队由配送中心出发为客户送货，如何设计合理的车辆运输路径使得所有客户需求被满足，以达到诸如行程最短、成本最小、耗时最少等目标。该问题在城市物流配送、车间工件加工排产、公共交通路线制定等多个领域具有广泛前景，因此车辆路径问题及其变种一直是学术界和企业界关注的热点。

众多生产、零售企业为了拓展市场，纷纷建立多个生产、分销网络，以服务区域型客户。对一些生产企业而言，生产原料需在多个生产厂进行储备，而产品由多种原料混合加工而成，将产生原料在各分厂转运的常见调拨问题。对于一些零售企业而言，市场结构的差异，导致商品在各分店销售水平不同，当分店中某些商品的当前库存持有量低于实际需求水平时应进行补货操作，对高于实际需求的商品应取走以补充其他分店的短缺，因此产生了各分店相互补货的商品调拨问题。此类调拨问题属于多商品供需未匹配（多对多）取送货车辆路径问题。

供需未匹配取送货车辆路径问题是传统车辆路径问题的复杂变种，可描述为：物流网络中有若干客户点，每个客户点供应一些商品的同时，还需求一些其他种类的商品，即每种商品同时存在多个供应和需求客户，针对每种商品的供需匹配关系事先未知（供需未匹配）的情况，需要研究如何以较低的运输成本在客户间取送货来满足所有客户需求。该问题不仅需要考虑客户间的访问路径决策，还需考虑客户间的商品供需匹配决策。

基于不同企业或企业不同运营阶段的优化需求不同，本书分别探讨三种不同情景下的多商品供需未匹配取送货车辆路径问题。主要研究成果如下：

（1）探讨单车场、单车型、单次访问条件下的多商品供需未匹配取送货车辆路径问题。综合考虑多商品、单车场、单车型和取送货需求可分批次等因素建立改进的数学优化模型，并推导了有效不等式来加强模型，采用改进的变邻域搜索算法求解。实验结果表明：①改进的模型需要较少的决策变量和约束，且在性能上优于文献中已有的模型；②提出的有效不等式显著地提高了模型的性能；③改进的算法在较短时间内能够对所研究的问题获得最优解或近似最优解，在求解质量、时间和稳定性上相对已有文献更具有优势。

（2）探讨多车场、多车型、单次访问条件下的多商品供需未匹配取送货车辆路径问题。综合考虑多商品、多车场、多车型和取送货需求可分批次等现实因素，尝试以“运距×运量”的车辆路径成本和基于额定吨位的固定派车成本之和最小为优化目标，建立混合整数数学规划模型，并设计基于大规模邻域搜索的迭代局部搜索求解算法。该算法采用基于运输效率提升的贪婪思想来快速构建高质量初始可行解，并通过引入四种移除算子、两种修复算子和车场车型调整优化策略形成大规模可行搜索邻域以增强全局寻优能力。基于18个文献算例和6个企业实例的数值实验结果表明：①本书提出的算法在求解质量和求解效率方面均优于相关文献中的算法；②相对于人工调拨方案，本书设计的方案能够帮助企业节约33%的运输成本和21%的车次。

（3）探讨多车场、多车型、多次访问条件下的多商品供需未匹配取送货车辆路径问题。综合考虑多商品、多车场、多车型和取送货需求可任意分批次等现实因素，以“运距×运量”的运输成本最小为优化目标，建立混合整数优化模型，设计两阶段启发式求解算法。该算法采用基于运输效率提升的贪婪思想来构建初始可行解，通过变邻域搜索来改善初始解质量。基于6组企业实例的实验结果表明：①考虑运输效率的初始解构建具有明显优势；②本书设计的算法在求解能力和效率方面优于相关文献中的算法；③相对于人工调拨方案，本书设计的方案能够帮助企业节约38%的运输成本及25%的车次。

总体而言，本书研究成果不仅可拓展取送货车辆路径问题现有理论，而且可帮助企业提高调拨效率，降低调拨成本，进而为其生产运营提供更有力的决策支持与指导。