基于竞合关系的车辆路径问题模型及算法研究

在全球经济一体化进程不断加快、市场竞争更加激烈以及市场分工进一步细化的情况下，被称作“第三利润源泉”的物流行业，作为前景广阔并具有增值功能的新兴服务业，已在全球范围内获得了高度重视并迅猛发展起来。目前，提高物流的运作效率已经成为很多企业提升其核心竞争力的重要举措，这也是提升整个国家资源配置优化程度和经济运行质量的手段。运输服务是运输配送环节的关键工作，加强运输服务管理有助于降低运输成本、减少客户流失、提高客户满意度、提高运输质量和效率。车辆路径问题的目标是实现运输配送环节的合理化和高效化，以及提高运输服务客户的满意度。然而，以往对于车辆路径问题的研究大多是基于确定性信息，建立的模型大部分是确定型数学模型，即假定安排车辆运输配送路线之前，模型中涉及的所有变量都是已知的且确定的。然而，在实际应用中，很多重要数据是很难完全确定的，如客户需求量、运输时间等。综合考虑前人研究和分析现实案例数据信息后发现，车辆路径问题中的很多不确定信息一般既包含随机不确定因素又包含模糊不确定因素。
　　随着物流与供应链行业的进一步细化，各方参与者越来越多，大型配送项目的计划不可能完全由一个人或者一个决策群组决定，而是需要多个决策群组或者多层级的决策者共同参与、同时决策。然而，现在大多数车辆路径问题的研究都是从单一决策人或决策群组的角度出发，很少考虑多个决策人或决策群组共同参与决策的情况，进而忽略了共同制订决策时多个参与者之间交互式的竞争合作关系的影响。Stackelberg均衡模型解决了此类问题，即在某个优化决策问题中，同时考虑多个决策者，并考虑决策者之间的竞争合作关系。在Stackelberg均衡模型中，不同层次的决策者控制的决策变量不同，因此，在制订自身策略时，也要考虑其他决策者或决策群组的策略，即他人决策对总体配送计划的影响，并根据层级不同，由上而下地依次做出决策。在前人研究基础之上，本书以模糊随机理论、Stackelberg均衡理论及启发式算法为研究工具，对模糊随机环境下的工程材料配送竞合车辆路径问题进行了研究，以期为实际车辆路径问题提供决策支持。
　　本书第1章和第2章介绍了问题研究背景、车辆路径问题、Stackelberg均衡理论及模糊随机理论研究现状，并给出了本书的研究框架。主体内容为第3章到第5章，后为结论部分。其中，第3章研究了模糊随机环境下的竞合车辆路径问题，即将Stackelberg均衡技术应用到车辆路径问题中，考虑了车辆路径问题中的多个决策群体，并考虑其包含的不确定因素，提出了基于竞合关系的车辆路径主从均衡数学模型。模型中，上级决策者，可以认为是供应商或者供应公司管理者，其目标是实现全局成本，包括路线初始成本、服务成本和运输成本；下级决策者，可以认为是外包运输公司或者公司运输规划部门，仅关心车辆运输成本，通过为每辆车安排运输路线，达到运输成本小化的目标。第4章对竞合车辆路径问题做了进一步研究，即在第3章的基础上加入顾客服务时间窗口要求，提出了时间窗口车辆路径主从均衡模型。在实际案例中，一般情况下，顾客会给定一个货物送达的时间范围，即给定其接受服务的时间窗口。在主从模型中，加入时间窗口约束以及顾客满意度约束，使模型更具普遍性和实用性。第5章提出了时间窗口取送货车辆路径主从均衡模型。即在顾客合理的时间要求内，基于前两章内容，更进一步地探讨了同时对顾客进行取货服务和送货服务的情况。
　　综上所述，在模糊随机双重不确定环境下，本书使用Stackelberg均衡理论对车辆路径问题进行了研究，依次研究了竞合关系下的车辆路径问题、时间窗口车辆路径问题以及时间窗口取送货车辆路径问题。首先，对这三类问题，分别建立了相应的Stackelberg均衡主从模型，并分析了这三类问题中的模糊随机不确定性。其次，车辆路径问题是组合优化和运筹学领域中非常著名的NP-Hard问题，双重不确定环境和复杂主从模型结构使得本书提出的车辆路径问题模型更加复杂和难解。由于该问题的复杂性和不确定性，本书使用启发式算法进行求解。后，针对这三类车辆路径问题分别进行了案例应用研究，进一步验证了该方法的可行性和有效性。决策模型和算法对于实际工程材料配送车辆路径问题有着一定的指导意义，对于不确定理论、Stackelberg均衡理论以及算法研究也有着积极的推动作用。
　　在此图书即将付梓之际，首先要向我的导师徐玖平教授表达由衷的感谢。在硕博连读期间，导师不厌其烦地指导我的研究工作，正是这些研究工作，让我度过了充实且富有收获的五年，这里，谨向老师表示衷心的感谢。另外，还要感谢曾给予我诸多帮助的师兄、师弟和师妹、同学和朋友们。后，我要向我的家人表达深深的谢意，感谢他们一直以来对我无微不至的照顾，感谢他们一直以来的鼓励和支持。
　　本书相关研究是国家自然科学基金应急管理项目“不确定同时取送货车辆路径主从均衡决策研究”（批准号：71640013），国家自然科学基金青年项目“工程供应链视角下‘调度.资源，运输’集成系统多层次主体博弈与动态协调研究”（批准号：71702167）以及*人文社会科学研究项目青年项目“互联网环境下考虑运输任务组合的车货匹配策略研究”（批准号：19YJC630198）的阶段性成果。此外，本书得到了河北省教育厅人文社会科学青年拔尖项目（批准号：BJ2016057）的资助，在此一并表示衷心的感谢。
　　鉴于作者水平有限，书中难免存在不妥之处，恳请读者批评指正。