车辆路径问题是研究如何通过合理规划行驶路线和路线调度，来实现运输成本最优的一类优化问题，其相关理论和算法对于降低物流成本具有重要的应用价值。车辆路径问题已经广泛地应用于生产和生活的各个方面，包括货物配送、拼车服务、校车接送等，并且产生了巨大的经济效益。
　　随着城市化进程的推进以及城市汽车保有量的增加，交通拥堵成为中国各大城市的焦点问题，同时，环境因素也越来越多地被考虑到车辆的安排和调度中。因此，本文研究了城市环境下若干带时间窗车辆路径问题的扩展问题，主要包括考虑时变行驶速度、环境成本、引入电动车辆进行运输的充电安排、拥堵收费等的问题。研究成果及核心内容主要有以下六个方面:
　　(1)查阅国内外大量的专著、期刊、会议论文集、研究报告等文献，并对相关领域的研究情况进行了综述。首先对车辆路径问题进行了概述;然后介绍了时变车辆路径问题的发展现状;接着对绿色车辆路径问题的两个方面——以低碳为目标的车辆路径问题和以电动汽车为运输工具的车辆路径问题进行了综述;最后介绍了可调鲁棒优化方法的研究现状和模型。
　　(2)针对论文涉及的带时间窗等复杂约束的给定路径的可行性判定问题，设计了判定算法。首先针对一类叫车服务问题，设计了基于时空的“插入-移出-再插入”的并行插入算法，算法引入分散化因子，在插入请求的过程中同时考虑时间和空间因素，并对插入请求时路径的可行性进行判定。通过随机生成的算例对算法进行测试，结果表明了算法的有效性。然后，根据叫车服务问题中约束复杂多样，调度的可行性不容易判定的特点，研究了在时变速度下，给定路径的可行性判定问题。考虑时间窗约束，容量约束，最大行程时间约束和路径最大持续时间约束，设计了最坏情况下时间复杂度为二次的三阶段判定算法。最后，将该算法进一步扩展到本文其它问题的可行性判定的情形。
　　(3)针对城市环境下具有相同目的地的顾客配送问题，考虑拥堵时段，建立了以碳排放成本，耗油量成本和行驶时间成本为目标的集客车辆路径问题的模型，设计了基于集划分的两阶段算法。在算法中，主要针对单条路径的调度进行了详细的研究，建立了混合整数线性规划模型，将最大行程时间约束和时间窗约束综合考虑，开发了启发式算法求解车辆的出发时间和行驶速度。最后，通过随机生成的算例，说明算法的有效性，并分析了交通拥堵和最大行程时间约束对结果的影响。
　　(4)针对电动汽车作为运输工具的车辆路径问题，建立了考虑拥堵时段的城市电动车辆路径问题的混合整数线性规划模型，设计了自适应大邻域搜索算法。该算法给出了顾客点和充电站的插入和移出策略，并主要研究了单条路径中充电量的确定和路径成本的计算方法。最后，修改标准数据集，得到中小规模和大规模的测试算例，并设计了仿真数值实验。通过与商业软件得到的精确解进行比较，说明算法的有效性。同时，数值实验分析了拥堵时段收费的影响。结果表明，拥堵收费使得进入高峰期的车辆数目明显减少，因此，这种收费模式可以有效缓解高峰期的道路拥堵问题。
　　(5)针对电动汽车访问充电站时可能出现等待的城市电动车辆路径问题，考虑了拥堵时段收费和拥堵区域收费两种收费模式，并分别建立了混合整数线性规划模型，设计了自适应大邻域搜索算法。在内容(4)中优化算法的基础上，根据拥堵区域收费的特点，引入了距离因素和时间因素分开讨论的插入和移出策略。通过与精确解和类似文献的研究结果进行比较，验证了算法的有效性。最后，分别设计了仿真实验，分析了在不同的拥堵收费模式下充电等待对结果的影响。
　　(6)针对车辆的行驶时间不确定的电动车辆路径问题，建立可调鲁棒优化模型，考虑多面体不确定集，并设计基于行生成和集划分的精确算法对模型进行求解。最后，设计了仿真实验，验证了算法的性能。同时，通过对各种不确定程度的结果进行比较，说明了鲁棒的代价，分析了不确定性对车辆路径的安排的影响。