Transportation Problem on a Tree Using Two-way Trips

This paper considers a transportation problem. Inventory or demand quantities for various commodities are specified at each warehouse. Warehouses and roads connecting them are represented as nodes and edges of a graph, respectively. We use many vehicles, moving around only locally instead of globally to carry commodities to fulfill demands at warehouses by visiting neighbors. We assume a vehicle at each node and a two-way transportation in which a vehicle carries commodities from a warehouse to an adjacent warehouse and then brings other commodities back to the warehouse. In this scenario we consider the problem of deciding whether there is a single round of two-way transportations of those vehicles that fulfill all demands. We show that the hardness of the problem heavily depends on whether some finite loading capacity is assumed or not. If the loading capacity is unbounded then it is solved in linear time, but otherwise it is NP-complete. We also present an efficient algorithm for deciding the feasibility of a tree or pseudotree in a special case of one commodity.