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

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.

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

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