  Motivated by an emerging framework of Autonomous Modular Vehicles, we
consider the abstract problem of optimally routing two modules, i.e., vehicles
that can attach to or detach from each other in motion on a graph. The modules'
objective is to reach a preset set of nodes while incurring minimum resource
costs. We assume that the resource cost incurred by an agent formed by joining
two modules is the same as that of a single module. Such a cost formulation
simplistically models the benefits of joining two modules, such as passenger
redistribution between the modules, less traffic congestion, and higher fuel
efficiency. To find an optimal plan, we propose a heuristic algorithm that uses
the notion of graph centrality to determine when and where to join the modules.
Additionally, we use the nearest neighbor approach to estimate the cost routing
for joined or separated modules. Based on this estimated cost, the algorithm
determines the subsequent nodes for both modules. The proposed algorithm is
polynomial time: the worst-case number of calculations scale as the eighth
power of the number of the total nodes in the graph. To validate its benefits,
we simulate the proposed algorithm on a large number of pseudo-random graphs,
motivated by real transportation scenario where it performs better than the
most relevant benchmark, an adapted nearest neighbor algorithm for two separate
agents, more than 85 percent of the time.
