The swapping problem on a line

We consider the problem of optimally swapping objects between N workstations, which we refer to as nodes, located on a line. There are m types of objects, and the set of object-types is denoted by S = f1;:::; mg. Object-type 0 is a dummy type, the null object. Each node v contains one unit of a certain object-type av 2 S [ f0g and requires one unit of object-type b(v) 2 S [ f0g. We assume that the total supply equals the total demand for each of the object-types separately. A vehicle of unit capacity ships the objects so that the requirements of all nodes are satisfied. The set of object-types is partitioned into two sets: objects that may be temporarily dropped at intermediate nodes before reaching their destination and objects that have to be shipped directly from their origin to their destination. The objective is to design a route that starts and ends at the depot and a feasible assignment of object-types to the route's arcs so that the total distance is minimized. We propose an O(N-2) algorithm to compute the optimal solution for this problem.