THE MEDIAN TOUR AND MAXIMAL COVERING TOUR PROBLEMS - FORMULATIONS AND HEURISTICS

In this paper, the authors introduce two bicriterion routing problems: the median tour problem (MTP) and the maximal covering tour problem (MCTP). In both problems the tour must visit only p of the n nodes on the network. In addition, both problems have as one of their objectives the minimization of total tour length. The second objective in both problems maximizes access to the tour for the nodes not directly on it. In the MTP, the access objective is the minimization of the total travel distance necessary for demand at the nodes to reach their nearest stop on the tour. In the MCTP, the access objective is to maximize the total demand within some prespecified maximal travel distance from a tour stop. It is shown that the MCTP may be viewed as a special case of the MTP; consequently, solution procedures developed for the MTP may also be employed to solve the MCTP. Unfortunately, both problems are NP-hard. In addition, the number of efficient solutions may grow exponentially with the number of nodes in the particular problem instance. Consequently a heuristic procedure is developed to generate a good approximation of the efficient frontier. Not only does this approximation provide the decision maker with insight into the magnitudes of the inherent tradeoffs between the two objectives, but it also provides him or her with a set of feasible options to consider. Computational experience, on a realistically scaled problem, is provided. Applications of the problems include the design of mobile service delivery systems (e.g. healthcare delivery in rural areas of developing countries), bi-modal transportation systems (e.g. overnight mail delivery), and distributed computer networks, among others.