作为一类主要的组合优化问题,车辆路径问题(VRP)一直受到了计算机科学和运筹学界的广泛关注,在实际工业生产调度中发挥了重要的作用。然而随着交通线路的日趋复杂化以及客户需求的多样化与个性化,基本VRP模型很难有效指导物流企业进行配送作业。现代物流企业在进行配送路线规划时,需要考虑方方面面的因素,比如客户的动态请求,时间窗限制,还有企业自身资源的限制。如何从满足顾客需求和优化企业自身网点角度来研究动态车辆路径问题(DVRP)越来越受到理论界的重视并逐渐成为研究热点。本文是在前人研究的基础上,重点对DVRP及其扩展和元启发式求解算法进行了研究,主要研究工作总结如下:(1)研究了基本DVRP问题,提出了一种改进的蝴蝶优化算法。该算法利用自然数编码的方式对DVRP进行离散问题连续编码;在迁移算子和调节算子的操作过程中采用一种贪婪策略接受局部解;每当有新解产生时,利用2-opt*算子对新解进行扰动,旨在帮助搜索过程避免陷入局部最优,增加搜索的多样性,加快搜索速度,从而得到最终的满意解。在通用的22个基准测试集上进行了实验,算法更新了 12个实例的已知最好解,与现有文献中的方法相比平均性能至少提高9.38%,从而验证了算法的有效性。(2)研究了有时间窗DVRP问题,提出一种改进的和声搜索算法。该算法结合了和声搜索算法与变邻域下降算法的优势。与经典和声搜索相比,重新定义了编码方式、初始解构造方式、即兴创作新和声操作及接收方式;设计了四种邻域结构以扩大搜索空间;以信息熵评价种群优劣,防止过早收敛;动态对客户请求进行检查,以提高搜索性能。并在通用的基准测试数据集上将该算法与现有算法进行对比实验,实验结果表示,算法的平均拒绝率最少,即使在相同的拒绝率的条件下,车辆行驶距离与车辆使用数在大部分情况下也优于现有算法,从而检验了算法的有效性。(3)研究了车辆数受限与带时间窗DVRP问题,提出了一种基于自适应大型邻域搜索的改进算法。设计了一系列特殊删除/修复策略;并对每一种策略指定初始评分及权重,在搜索过程根据当前的表现动态更新评分及权重,根据权重按照轮盘赌的机制选择删除/修复策略;引入一个周期性的扰动策略,加快了搜索速度;此外,针对动态客户的插入,设计了一个针对时间窗的提前等待策略。最后通过Lacker基准数据集对算法性能进行测试,更新了 19组实例的最少车辆使用数,检验算法的有效性。(4)研究了众包条件下的带时间窗动态车辆路径问题,在该问题中,假设一部分客户的需求是通过物流公司自营的车队进行运输,另一部分则以外包的形式发布到第三方物流平台,通过临时司机接收任务的方式完成相关运输配送。为了求解该问题提出一种贪婪随机自适应搜索算法。该方法的迭代过程包括构造和局部搜索两个阶段。在解的构造阶段,采用两种不同的贪婪函数来构造初始解;在局部搜索阶段,设计了4种邻域结构,扩展了解的搜索空间。为了促进临时司机的积极性,设计了两个不同的补偿策略。通过Lackner的基准实例验证了算法的有效性,再利用真实案例对其进行测试,验证了众包策略的优越性。(5)开发基于众包的包裹配送平台。从软件开发的角度对系统的功能模块进行分析,设计众包条件下包裹配送的业务流程,集成本文提出的相关求解算法,并展示包裹配送平台的主界面和功能模块。该平台可以为物流公司使用众包进行包裹配送提供有效的物流整合方案。