RESTRICTED DELIVERY PROBLEMS ON A NETWORK

We consider a delivery problem on a network in which nodes have suppli es or demands for certain products and arcs have lengths satisfying th e triangle inequality. A vehicle of infinite capacity travels through the network, carrying products to their destinations, and is limited i n that it can carry only a single type of product at a time. The gener al problem asks for a shortest delivery route of all products from the ir origin to their destination. Here, we consider certain restrictions on the delivery paths allowed and compare the quality of the solution of the unrestricted problem to that of the restricted one. Both the g eneral and restricted problems are NP-hard, and we discuss approximati on algorithms. We also give a constant factor approximation algorithm for the Clustered Traveling Salesman Problem. (C) 1997 John Wiley & So ns, Inc.