SALES-DELIVERY MAN PROBLEMS ON TREE-LIKE NETWORKS

Suppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location-routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O(n log n) or O(n). Multiserver variants of the problem on a tree are proved to be NP-complete. Some modifications of the problem are also investigated. (C) 1995 John Wiley and Sons, Inc.