The emergency vehicle routing problem with capacity constraint and advanced information

Due to the frequent occurrence of natural disasters, routing of the emergency vehicles after disaster is gaining extensive attention. This paper considers the situation that emergency vehicle has finite capacity and the affected points can be informed in advance but can't be served immediately, and introduces disclosure date and release date into quota TSP model with advanced information, and gives the lower bound. When metric space is positive half-line, MLIB algorithm and SW algorithm are presented. For general metric space, greedy algorithm is presented, competitive analysis is given for these three algorithms respectively. The results show that with more advanced information, the performance of the three algorithms will be better.