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

项目编号: 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;

成为VIP会员查看完整内容
0

相关内容

【博士论文】吉布斯分布的局部、动态与快速采样算法
专知会员服务
28+阅读 · 2021年11月26日
逆优化: 理论与应用
专知会员服务
36+阅读 · 2021年9月13日
专知会员服务
38+阅读 · 2021年9月7日
专知会员服务
83+阅读 · 2020年12月11日
专知会员服务
73+阅读 · 2020年12月7日
【KDD2020-阿里】可调控的多兴趣推荐框架
专知会员服务
28+阅读 · 2020年8月11日
专知会员服务
42+阅读 · 2020年7月29日
排队3小时的烘焙店,B&C还能火多久?
36氪
0+阅读 · 2022年2月16日
面向自动驾驶的边缘计算技术研究综述
专知
4+阅读 · 2021年5月3日
约束进化算法及其应用研究综述
专知
0+阅读 · 2021年4月12日
【AGV】仓库内多AGV协作的全局路径规划算法的研究
产业智能官
27+阅读 · 2018年11月10日
一种轻量级在线多目标车辆跟踪方法
极市平台
13+阅读 · 2018年8月18日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月24日
Arxiv
11+阅读 · 2018年5月21日
小贴士
相关VIP内容
【博士论文】吉布斯分布的局部、动态与快速采样算法
专知会员服务
28+阅读 · 2021年11月26日
逆优化: 理论与应用
专知会员服务
36+阅读 · 2021年9月13日
专知会员服务
38+阅读 · 2021年9月7日
专知会员服务
83+阅读 · 2020年12月11日
专知会员服务
73+阅读 · 2020年12月7日
【KDD2020-阿里】可调控的多兴趣推荐框架
专知会员服务
28+阅读 · 2020年8月11日
专知会员服务
42+阅读 · 2020年7月29日
相关基金
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
微信扫码咨询专知VIP会员