汽车保有量的逐年增加和快递行业的快速发展在推动我国经济的发展的同时也带来了一系列问题,如城市交通拥堵、雾霾等问题。在快递投送时,配送路线的选取是至关重要的,其配送路线是否合理高效,直接关系着企业的物流成本。虽然,我国城市物流配送的专业化水平得到不断提升,但是由于我国汽车总量多,因此仍然面临着严峻的交通拥堵、车辆“通行难”等问题。为了改善交通拥堵状况,上海、北京、天津等国内多家城市相继推出分区域、分车型、道路限行等措施来限制城市配送车辆通行。在现实生活中,车辆容量是有限的,客户请求时间窗大多是一个时间段,车辆到达时间早于客户开始时间会增加物流企业的时间成本,而晚于客户结束时间则会降低客户满意度。为了企业长期健康发展,保证客户的良好体验,需要在满足限行约束的条件下规划合理的车辆路径,以在规定的时间窗内进行配送。此外,由于交通拥堵、天气变化及客户需求变化等,事先规划好的车辆路径往往不能按计划进行,需要重新对原有车辆路径进行调整。因此,研究限行约束下带容量和时间窗约束的动态城市物流配送车辆路径优化问题具有较强的现实意义和实用价值。本文首先研究静态的带容量和软时间窗限制的有限行约束的车辆路径问题;然后研究无限行约束下客户需求未知的动态车辆路径问题;最后对限行约束下的动态车辆路径问题进行研究。主要研究成果如下:(1)在研究限行约束下的车辆路径问题时,同时考虑区域限行、道路限行、软时间窗、容量约束等因素,构建新的优化模型,并设计模型求解的改进的蝙蝠算法。通过引入差分算法更新种群,局部搜索采用变邻域思想,设计一种离散化的带有变邻域的蝙蝠算法(Discrete bat algorithm with variable neighborhood,VDBA)。以Solomon数据为基础构造实验数据,并与遗传算法、粒子群算法进行分析比较,实验结果验证了VDBA算法的优越性。(2)在研究无限行约束下的动态车辆路径问题时,考虑客户需求动态到达,同时考虑软时间窗、容量约束因素,构建周期性策略下的动态车辆路径问题模型。采用两阶段算法求解,将整个工作日分为初始规划阶段及动态优化阶段,两个阶段规划路径时均采用VDBA算法。在动态优化阶段,通过划分时间片,将动态车辆路径问题转化为一个个瞬时静态车辆路径问题。通过实验结果分析比较获得如下结论,在Lackner测试库中的12个测试实例,有11个实例采用VDBA算法所求得结果优于遗传算法、粒子群算法所求结果;在求解动态车辆路径问题时,并不是时间片越小所求得的结果越好。(3)将限行约束下的车辆路径问题和动态车辆路径问题相结合,研究限行约束下的动态车辆路径问题。构建限行约束下的动态车辆路径问题模型,采用周期性策略,两阶段求解算法。以Lackner数据为基础构造12个测试实例,并与遗传算法、粒子群算法进行分析比较。实验结果表明,在求解限行约束下的问题时,有8个实例采用VDBA算法所求得结果略优于遗传算法、粒子群算法所求得结果。在实际案例测试中,VDBA算法表现出较好的性能,能够为企业规划出合理的配送路线,有效降低成本。