论文部分内容阅读
针对方格路网上道路堵塞的位置和数量信息不完全的情形,本文研究了两辆应急救援车的在线路径选择问题,使得最多有k条边堵塞时,至少一辆车尽快到达事故点进行救援.根据网络的特点,对两车分别设计了横向优先和纵向优先的在线路径选择策略,通过竞争分析法得出该在线策略的在两种情形下的竞争比:出发点和事故点在同一条直线上以及出发点和事故点不在同一条直线上,并证明两种情形下的竞争比均是紧的;最后说明了该在线策略在某些情形下的最优性.
In view of the incomplete location and quantity information of road blockage on the grid road network, this paper studies the problem of online route selection of two emergency vehicles so that at least one vehicle reaches the accident point for rescue According to the characteristics of the network, the horizontal and vertical priority routing strategies are designed for the two vehicles respectively, and the competitive ratio of the online strategy in two situations is obtained by competition analysis: the starting point and the accident point are on the same straight line And the starting point and the accident point are not in the same straight line, and prove that the competition ratio in both cases is tight. Finally, the optimality of the online strategy in some cases is illustrated.