THE DYNAMIC TRAVELING REPAIR PROBLEM: EXAMINATION OF AN ASYMPTOTICALLY OPTIMAL ALGORITHM

摘要: The dynamic traveling repair problem involves providing service to customers whose locations are uniformly distributed over a bounded area in the Euclidean plane. authors assume that customer requests arrive according Poisson point process. Earlier research provided conjecture asymptotically optimal algorithm for this under very heavy traffic intensity following: partition into sub-regions, wait sufficient demand accumulate serve demands sub-regions salesman (TSP) tour, and visit first-come first-served order as GI/G/m queue. Further, researchers conjectured single server case can be extended m-server by simply partitioning region m of same size assigning one vehicle sub-region. In paper they define class algorithms which includes above algorithm. They then demonstrate asymptotic optimality an is among class. Therefore, prove first made researchers. Finally, argue about multiple also true.