Restricted Delivery Problems on a Network

We consider a delivery problem on a network in which nodes have supplies or demands for certain products and arcs have lengths satisfying the triangle inequality. A vehicle of infinite capacity travels through the network, carrying products to their destinations, and is limited in that it can carry only a single type of product at a time. The general problem asks for a shortest delivery route of all products from their 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 general and restricted problems are NP-hard, and we discuss approximation algorithms. We also give a constant factor approximation algorithm for the Clustered Traveling Salesman Problem.