Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid

Jake Weiner, Andreas T. Ernst, Xiaodong Li, Yuan Sun and Kalyanmoy Deb

European Journal of Operational Research, 2021, vol. 293, issue 3, 847-862

Abstract: This paper presents a new method to solve the Maximum Edge Disjoint Paths (MEDP) problem. Given a set of node pairs within a network, the MEDP problem is the task of finding the largest number of pairs that can be connected by paths, using each edge within the network at most once. We present a heuristic algorithm that builds a hybridisation of Lagrangian Relaxation and Particle Swarm Optimisation, referred to as LaPSO. This hybridisation is combined with a new repair heuristic, called Largest Violation Perturbation (LVP). We show that our LaPSO method produces better heuristic solutions than both current state-of-the-art heuristic methods, as well as the primal solution found by a standard Mixed Integer Programming (MIP) solver within a limited runtime. Significantly, when run with a limited runtime, our LaPSO method also produces strong bounds which are superior to a standard MIP solver for the larger instances tested, whilst being competitive for the remainder. This allows our LaPSO method to prove optimality for many instances and provide optimality gaps for the remainder, making it a “quasi-exact” method. In this way our LaPSO algorithm, which draws on ideas from both mathematical programming and evolutionary algorithms, is able to outperform both MIP and metaheuristic solvers that only use ideas from one of these areas.

Keywords: Combinatorial optimization; Large scale optimization; Metaheuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721000114
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:293:y:2021:i:3:p:847-862

DOI: 10.1016/j.ejor.2021.01.009

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 ().