中文摘要：

车辆路径优化问题长期以来都是物流研究中的基础问题。随着应急物流的发展，应急物流中的救灾车辆调度问题和在规定时间内完成紧急调运的车辆调度问题都受到了越来越多的关注。本项目主要研究应急物流中的两类基本问题应用于救灾的最小化最长客户等待时间的车辆路径问题，和应用于紧急调运的带时间约束的最小化成本的车辆路径问题。本项目首先从最小化最长客户等待时间的车辆路径问题入手，首先分析其近似复杂度，然后提出多项式时间的近似算法，最后在多项式时间近似算法基础上力求得到良好的启发式搜索算法，最终目标是提出创新的兼顾最坏情况保障和平均效果保障的算法。我们将进一步研究不确定环境下带时间约束的最小化成本的车辆路径问题。与以往研究随机车辆路径问题不同，我们仅仅假设车辆运行时间的随机变量属于某闭区间，而忽略随机变量的分布等其它信息，力图综合运用鲁棒性规划和整数规划的方法来获得保证每辆车按时完成任务概率的车辆路径方案。