| The necessary information to optimally serve sequential requests at the vertices of an undirected, unweighted graph with a single mobile resource is a known result of Chung, Graham, and Saks; however, generalizations of this concept to directed and weighted graphs present unforeseen and surprising changes in the necessary lookahead for strategic optimization. This research investigates the necessary information to provide an optimal-cost relocation schedule on directed graphs with arbitrary distance matrices. Traditional approaches as well as a novel algebraic framework are used to explore the distinctions between graphs which admit finite-lookahead optimization and those do not. In particular, a method developed by Cuninghame-Green to model industrial process timing is, with modifications, effective for mapping and analyzing possible request sequences and their associated costs. |
