Branching Optimization for Transporting Tasks in the Plane

摘要

In this work we propose a simulated annealing based search algorithm for optimal ramified or branched transportation route in R-2. The cost function of the transport network allows the system to merge small roads into larger highways, carry the goods together and separate them near the destination. As a result the transportation route has multiple branching-in and -out points, to some extent similar to nerve system of the tree leaf. The problem is known to be NP-complete even for finite set of branching points and metric spaces.