| 基于方格路网的两车应急救援路径在线选择 |
| |
| 引用本文： | 徐寅峰,张惠丽,余海燕,张文明.基于方格路网的两车应急救援路径在线选择[J].系统工程理论与实践,2013,33(1):175-180. |
| |
| 作者姓名： | 徐寅峰 张惠丽 余海燕 张文明 |
| |
| 作者单位： | 1. 西安交通大学 管理学院, 710049 西安;
2. 西安交通大学 过程控制与效率工程教育部重点实验室, 710049 西安;
3. 机械制造系统工程国家重点实验室, 710049 西安 |
| |
| 基金项目： | 国家自然科学基金(71071123, 60736027, 60921003); 长江学者和创新团队发展计划(IRT1173) |
| |
| 摘 要： | 针对方格路网上道路堵塞的位置和数量信息不完全的情形, 本文研究了两辆应急救援车的在线路径选择问题, 使得最多有k条边堵塞时, 至少一辆车尽快到达事故点进行救援. 根据网络的特点, 对两车分别设计了 横向优先和纵向优先的在线路径选择策略, 通过竞争分析法得出该在线策略 的在两种情形下的竞争比: 出发点和事故点在同一条直线上以及出发点和事 故点不在同一条直线上, 并证明两种情形下的竞争比均是紧的; 最后说明了 该在线策略在某些情形下的最优性.
|
| 关 键 词： | 应急救援 车辆路径 在线策略 方格网 |
| 收稿时间： | 2010-09-19 |
Online routing of two vehicles to an emergency scene in grid transportation network |
| |
| XU Yin-feng,ZHANG Hui-li,YU Hai-yan,ZHANG Wen-ming.Online routing of two vehicles to an emergency scene in grid transportation network[J].Systems Engineering —Theory & Practice,2013,33(1):175-180. |
| |
| Authors: | XU Yin-feng ZHANG Hui-li YU Hai-yan ZHANG Wen-ming |
| |
| Institution: | 1. School of Management, Xi'an Jiaotong University, Xi'an 710049, China;
2. Ministry of Education Key Lab for Process Control & Efficiency Engineering, Xi'an Jiaotong University, Xi'an 710049, China;
3. State Key Lab for Manufacturing Systems Engineering, Xi'an 710049, China |
| |
| Abstract: | The online routing problem of two vehicles to an emergency scene is considered. In grid transportation network, some of the edges may be suddenly blocked and the blockage will not be observed until reaching an endpoint of the blocked edge. The goal is to minimize the arrival time of the first vehicle with at most k blockages. An online strategy named Row-first and Line-first is presented and the competitive ratio is analyzed, and the ratio is proved to be tight. The optimization of the online strategy in some situations is also proved. |
| |
| Keywords: | emergency vehicle routing online grid transportation network |
|
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
|
