article · 2001

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

Cited by 0Abstract and details only

Abstract

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

Cite this paper

APA 7

Lu, X., Regan, A., & Irani, S. (2001). THE DYNAMIC TRAVELING REPAIR PROBLEM: EXAMINATION OF AN ASYMPTOTICALLY OPTIMAL ALGORITHM.

MLA 9

Lu, Xiong, et al. “THE DYNAMIC TRAVELING REPAIR PROBLEM: EXAMINATION OF AN ASYMPTOTICALLY OPTIMAL ALGORITHM.” 2001.

Chicago

Lu, Xiong, Amelia Regan, and Sandy Irani. 2001. “THE DYNAMIC TRAVELING REPAIR PROBLEM: EXAMINATION OF AN ASYMPTOTICALLY OPTIMAL ALGORITHM.”

Harvard

Lu, X., Regan, A. and Irani, S. (2001) ‘THE DYNAMIC TRAVELING REPAIR PROBLEM: EXAMINATION OF AN ASYMPTOTICALLY OPTIMAL ALGORITHM’.

BibTeX

@article{lu2001dynamic,
  title = {{THE DYNAMIC TRAVELING REPAIR PROBLEM: EXAMINATION OF AN ASYMPTOTICALLY OPTIMAL ALGORITHM}},
  author = {Lu, Xiong and Regan, Amelia and Irani, Sandy},
  year = {2001}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.