前言

现代物流作为现代经济的重要组成部分，在国民经济和社会发展中发挥着重要作用。发展现代物流对于提高国民经济运行的质量和效益、优化资源配置、改善投资环境、促进企业结构调整、提高我国经济实力等多方面都具有十分重要的意义。目前，国际上普遍把物流称为“降低成本的最后边界”，排在降低原材料消耗、提高劳动生产率之后的“第三利润源泉”。随着经济全球化和信息化进程的不断加快，物流业作为具有广阔前景和增值功能的新兴服务业，正在全球范围内迅速发展，掀起“现代物流革命”。

配送是物流系统中的一个重要环节，它是指按客户（包括零售商店、用户等）的订货要求（包括在货物种类、数量和时间等方面的要求），在配送中心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。配送是一种集集货、分货、配货、配装、送货等多种功能为一体的物资流通方式。在配送业务中，配送车辆优化调度问题的涉及面较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。该问题是物流系统优化的关键。

国外将配送车辆优化调度问题归结为VRP（Vehicle Routing Problem，车辆路径问题）、VSP（Vehicle Scheduling Problem，车辆调度问题）和MTSP（Multiple Traveling Salesman Problem，多路旅行商问题）。该问题于1959年由Dantzig和Ramser提出后，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为配送车辆优化调度问题。本书所研究的配送车辆优化调度问题的求解算法对解决上述问题也是有效的。可见，本书研究配送车辆优化调度问题的模型和算法，具有重要的理论和现实意义。

本书展示的是作者多年从事配送车辆优化调度问题研究的成果，包括作者的博士学位论文，作者在学术期刊和学术会议上发表的学术论文以及作者指导研究生的硕士学位论文。本书主要展示了以下创新研究成果。

（1）在对配送车辆优化调度问题的构成要素包括货物、车辆、配送中心、客户、运输网络、约束条件和目标函数等的属性进行系统分析和描述的基础上，分别建立了无时限单向、有时限单向、无时限双向和有时限双向单配送中心车辆优化调度问题，无时限和有时限多配送中心车辆优化调度问题以及动态车辆配送优化调度问题和动态网络配送车辆优化调度问题的基于直观描述的数学模型。上述模型均考虑了较为接近实际的约束条件和目标函数，并具有简单、直观、易于理解、易于设计算法求解及可扩充性强等特点。

（2）为构造配送车辆优化调度问题的求解算法提出了两种新的解的表示方法（即客户直接排列的表示方法及车辆和客户对应排列的表示方法）和两种新的邻域搜索策略（即逆转法和插入法）。进而分别针对多种解的表示方法设计了相应的解的评价方法和具体的邻域选点策略。

（3）分别设计和实现了无时限单向配送车辆优化调度问题的爬山算法、禁忌搜索算法、模拟退火算法和遗传算法，并通过实验计算分析了解的表示方法、邻域选点策略、迭代搜索策略、个体编码方法、选择策略、交叉算子、变异算子等算法策略及搜索次数、禁忌长度、初始温度、降温速度、交叉概率、变异概率、群体规模、进化代数等运行参数对算法性能的影响，结果表明，选择合适的算法策略和运行参数，有利于提高算法性能。

（4）通过实验计算比较了爬山算法、禁忌搜索算法、模拟退火算法和遗传算法的寻优性能：爬山算法具有很高的收敛速度，对于规模较小的问题寻优效果较好，对于规模较大或很大的问题寻优效果较差，且算法的稳健性较差；禁忌搜索算法和模拟退火算法性能接近，它们具有比爬山算法更好的寻优性能，可以得到质量很好的解，且具有较强的稳健性；遗传算法对于规模较小的问题寻优结果较好，但对于规模较大的问题寻优结果较差，在相同的搜索次数下，基本遗传算法的寻优结果远不如禁忌搜索算法和模拟退火算法，甚至不如爬山算法，遗传算法的计算效率远不如爬山算法，也不如禁忌搜索算法和模拟退火算法。

（5）针对基本遗传算法的不足，提出将局部搜索能力较强的爬山算法和模拟退火算法与基本遗传算法结合，并构造了求解配送车辆优化调度问题的两种混合遗传算法：爬山遗传算法和模拟退火遗传算法。实验计算结果表明：两种混合遗传算法可以在一定程度上克服基本遗传算法在局部搜索能力方面的不足，从而能得到比基本遗传算法更好的计算结果；两种混合遗传算法的计算效率均高于基本遗传算法；两种混合遗传算法的寻优性能均不如禁忌搜索算法和模拟退火算法。

（6）提出了更具一般性的双向配送车辆优化调度问题。针对硬时间窗和软时间窗双向配送车辆优化调度问题中因每个客户有供应和需求两个时间窗从而造成求解困难的情况，提出了一种通过拆分客户的方法将双时间窗问题转化为单时间窗问题进行求解的思路。

（7）设计了多配送中心车辆优化调度问题的求解策略，即利用距离最近分配法划定每个配送中心服务的客户，进而将一个多配送中心车辆优化调度问题转化成多个单配送中心车辆优化调度问题进行求解。

（8）分别设计并实现了硬时间窗单向、软时间窗单向、无时限双向、硬时间窗双向和软时间窗双向配送车辆优化调度问题以及无时限和有时限多配送中心车辆优化调度问题的禁忌搜索算法和模拟退火算法，实验计算结果表明：用禁忌搜索算法和模拟退火算法求解上述配送车辆优化调度问题均可以取得很好的计算结果，且算法的计算结果较稳定，计算效率也较高。

（9）研究了考虑车辆故障、车辆多次巡回配送等实际因素的动态车辆配送优化调度问题。为该问题设计了“制定整体优化配送计划+实时局部优化调度”的两阶段求解策略。设计和实现了求解该问题的“禁忌搜索+局部搜索”算法，既充分利用了禁忌搜索算法的优势，又通过局部搜索算法实现了对多次巡回车辆动态信息的实时处理，完成了局部调整的优化调度，从而使该问题得到满意的解决。

（10）构造了动态网络配送车辆优化调度问题的遗传算法。在制定配送计划阶段，可以得到在保证一定的顾客服务水平基础上运距最短、成本最小的配送方案。在配送计划的执行阶段，借助于GPS可随时得到车辆的在途位置，从而可以对后续顾客的服务保证率进行核定。若出现按计划不能满足对后续顾客的服务保证时，可以在最早的时间内知道计划可能违约的时间，从而可为采取适宜的补救措施赢得时间。

本书除突出强调内容的创新性外，还具有以下特点。

（1）循序渐进性。本书是按照先简单、后复杂的顺序循序渐进地研究各类配送车辆优化调度问题的。即先研究无时限问题，后研究有时限问题；先研究单向问题，后研究双向问题；先研究单配送中心问题，后研究多配送中心问题；先研究静态问题，后研究动态问题。这既符合科学研究规律，也增加了本书的易读性。

（2）技术路线的科学性。本书对每类配送车辆优化调度问题基本都按照“问题描述→数学建模→算法设计→实例计算→算法分析”的思路开展研究，技术路线清晰、合理，也体现了理论与实践的有机结合。

（3）实用性。本书在介绍各种配送车辆优化调度问题的优化算法时，均在设计各种算法要素的基础上，给出了详细的计算机编程思路，并在附录中给出了禁忌搜索算法和模拟退火算法的C语言程序源代码，而且都进行了实例计算。这有利于有关人员将这些优化算法嵌入到实际的物流管理和优化软件中，用以解决实际问题。

（4）读者的广泛性。本书可作为物流管理、物流工程、交通运输等相关专业师生的参考书，也可供物流行业的管理人员、专业技术人员及软件设计、开发人员学习参考。

本书得到了北京交通大学学术专著出版基金的资助和北京交通大学交通运输学院学术著作出版资助奖励，在此表示衷心的感谢！

作者的博士生导师胡思继教授、妻子张建琴工程师、硕士研究生石洪波工程师为本书的完成做出了很大贡献，在此深表谢意！并对为本书的出版提供帮助的单位、个人及本书参考文献的作者表示诚挚的感谢！

由于作者水平有限，书中难免有不当或错误之处，希望专家、学者和广大读者不吝指正。

郎茂祥
2008年12月于北京交通大学