Computing inter-site distances for routing and scheduling problems

Routing and scheduling problems have received considerable attention in the literature in terms of model building and algorithm development. On these fronts, progress has been substantial. However, one often neglected (yet critical) aspect concerning the use of these models and algorithms is their data requirements. In particular, the distance matrix yielding the shortest distance between each pair of sites (nodes) represents a major portion of the data required by all such problems. Yet, such data are seldom available with the degree of accuracy desired and often are not available at all.This paper describes an efficient method for obtaining this distance matrix that is based on the underlying road structure for the geographic region in question. Thus, the distances obtained reflect ‘actual’ distances. Finally, the paper presents some brief computational experience and discusses an implementation concerning the routing of environmental inspectors in the state of Pennsylvania.