Online Nomadic TSP based on advanced information

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.