应急物流中的车辆路径优化问题

项目名称： 应急物流中的车辆路径优化问题

项目编号： No.71201127

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 管理科学与工程

项目作者： 徐亮

作者单位： 西南财经大学

项目金额： 22万元

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

中文关键词： 应急物流；车辆路径；近似算法；鲁棒优化；

英文摘要： Vehicle routing problem is one of the most important combinatorial optimization problems. After the two earthquakes occurred in China and Japan, the vehicle routing for emergency distribution has drawn more and more attention. Our project focuses on two main problems in the vehicle routing for emergency distribution: the min-max vehicle routing problem for the relief efforts, and the min-sum vehicle routing problem with time limitation constraint for emergency dispatching. For the min-max vehicle routing problem, we analyze its approximation hardness results, derive polynomial time approximation algorithms, and develop heuristic algorithms with both worst-case performance and average performance guarantees. For the min-sum vehicle routing problem with time limitation constraint, we focus on the stochastic problem, in which the travle time between any pair of customers is assumed to be a random variable in a closed interval, without any assumption on its distribution or scenarios. Combining the robust optimization programming and the integer programming techniques, we are trying to obtain a vehicle routing plan, in which the probability that each vehicle finish its service before the time limitation is greater than a pre-specified value, and the total travel cost is minimized.

英文关键词： Emergency Distribution；Vehicle Routing；Approximation Algorithm；Robust Optimization；