基于预知信息的占线Nomadic TSP问题

Online nomadic TSP based on advanced information

自然灾害的频繁发生使得应急减灾倍受关注,尤其有效的应急救援车辆调度对应急减灾非常重要.针对受灾点被提前获知但是不能立即接受救援服务的情形,通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题,并分别给出了问题的下界,直线网络结构下的ENO-dd算法,和一般网络结构下的GTR-dd算法,并对算法进行了竞争性能分析.结果表明两个算法随着预知信息的增多会有明显改进.更为一般的预知信息结构以及最优的算法设计是下一步研究的方向.

The frequent occurrence of natural disasters has drawn people＇s attention to the aftermath work, especially the effective routing of emergency vehicles carrying relief efforts. Based on the situation where some disaster hit areas can be informed in advance while could not accept emergency service, this paper introduces the disclosure date and release date to nomadic TSP model, studies an online nomadic TSP problem based on advanced information, and gives a lower bound. When the metric space is the real line, an ENO-dd algorithm is presented. For general metric spaces, a GTR-dd algorithm is presented. Competitive analysis is given for these two algorithms respectively. The results indicate that the more advanced information, the better these two algorithms perform. More general information structure and optimal algorithm design can be the future research