The Optimal Path Tour Problem
Chao Yan, Cai Gao, Jianjun Yu, Yong Deng and Kai Nan
Solving variations of classical operational research problems, especially transportation problem (TP) and supply chain network (SCN) design, which are concerning optimally allocating scarce resources to new demanding requirements, has been becoming central in research community. In this paper, we define and study the optimal path tour problem (OPTP), whose goal is to select a set of paths and to decide their corresponding loads from a given source node subset to a given sink node subset in a directed weighted graph. The constraint of such paths is that they have to sequentially and successively pass through all given disjoint node subsets. The optimal transportation strategy guarantees the least total cost of the transportation under certain supply-demand conditions. Two kinds of OPTP are modeled respectively according to whether there are supply-demand constraints in intermediate node subsets. The algorithms inspired by the basic Physarum Polycephalum model, which displays high competency for network optimization, are proposed to solve OPTP. We demonstrate efficiency of the proposed algorithms using several illustrative examples.
Keywords: Optimal path tour, transportation problem, multi-source multi-sink, physarum polycephalum, network optimization