Route bundling in polygonal domains using Differential Evolution

Route bundling implies compounding multiple routes in a way that anchoring points at intermediate locations minimize a global distance metric to obtain a tree-like structure where the roots of the tree (anchoring points) serve as coordinating locus for the joint transport of information, goods and people. Route bundling is a relevant conceptual construct in a number of path-planning scenarios where the resources and means of transport are scarce/expensive, or where the environments are inherently hard to navigate due to limited space. In this paper we propose a method for searching optimal route bundles based on a self-adaptive class of Differential Evolution using a convex representation. Rigorous computational experiments in scenarios with and without convex obstacles show the feasibility and efficiency of our approach.