A New Transportation Problem on a Graph with Sending and Bringing-Back Operations

摘要

This paper considers a transportation problem which is different from the conventional model. Suppose we are given many storages (nodes) to store multiple kinds of commodities together with roads (edges) interconnecting them, which are specified as a weighted graph. Some storages have surplus and others have shortages. Problem is to determine whether there are transportations to eliminate all of shortages. For transportation we can use a vehicle with the loading capacity at each node. Each vehicle visits one of its neighbors with some commodities which are unloaded at the neighbor. Then, we load some other commodities there, and then bring them back to the original node. How to design such send-and-bring-back transportations to eliminate all shortages is the problem. When we define a single round of transportations to be a set of those transportations at all nodes, whether there is a single round of valid transportations that eliminate all of shortages is our concern. After proving NP-completeness of the problem we present a linear time algorithm for a special case where an input graph is a forest.