The multiple shortest path problem with path deconfliction

Michael S. Hughes, Brian J. Lunday, Jeffrey D. Weir and Kenneth M. Hopkinson

European Journal of Operational Research, 2021, vol. 292, issue 3, 818-829

Abstract: To address the increasingly relevant challenge of routing autonomous agents within contested environments, this research formulates and examines the Multiple Shortest Path Problem with Path Deconfliction (MSPP-PD) to balance agent routing efficiency with group vulnerability. Within the general model formulation, multiple agents are routed between respective source and terminus nodes while minimizing both the total distance travelled and a measure of path conflict, where path conflict occurs for any instance of more than one agent traversing an arc and/or node. Within this modeling structure, this research presents and inspects a set of alternative, conceptually-motivated penalty metrics to inhibit path conflict between agents. Illustrative testing demonstrates the distinguishability of different MSPP-PD variants as they relate to optimal agent routing solutions, as well as the non-dominated solutions attainable via different relative priorities over the objective functions. Subsequent empirical testing over a set of synthetic instances demonstrates the effect of different penalty function metrics on both optimal solutions and the computational effort required to identify them. Concluding the work are recommendations about the utility of the MSPP-PD model variants, both individually and collectively.

Keywords: Routing; Shortest path problem; Path deconfliction; Multi-objective optimization; Multi-agent (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720309796
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:292:y:2021:i:3:p:818-829

DOI: 10.1016/j.ejor.2020.11.033

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().