In this article, we introduce an extension of the classical shortest path problem for a symmetric directed graph. In our problem, a subset of the arcs in the graph are not initially available to the primary vehicle (referred to as the convoy). These initially unavailable arcs are referred to as impeded arcs, and they represent paths that the convoy cannot use due to some obstruction. For example, a path may have rocks that need to be cleared before the convoy can use this path. Alternatively, a path may potentially have hostile agents that could harm the convoy and so these paths need to be confirmed to be safe before the convoy uses these paths. A secondary vehicle (referred to as the support) is deployed simultaneously to assist the convoy. The support is able to make impeded arcs available for use by the convoy by performing some appropriate action (such as clearing obstacles or confirming the safety of the path). The convoy is unable to use an impeded arc until the support has performed the appropriate action. The objective is then to find a pair of paths for the convoy and support so that the convoy reaches its desired destination in minimal time while using arcs that are either initially available or have been made available through the actions of the support. Coordination problems such as this naturally occur in civil and military applications where vehicles of different types and capabilities are required to work tightly to accomplish a mission. In this article, we present a mixed-integer nonlinear program (MINLP) formulation and use the standard Big-M method to reformulate it as a mixed-integer linear program (MILP). We then solve randomly generated instances of the MILP and compile the computational results. We find that the MILP's difficulty is heavily dependent on the particular instance. We then briefly discuss some potential future work.
展开▼
