期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 293, 期 3, 页码 847-862出版社
ELSEVIER
DOI: 10.1016/j.ejor.2021.01.009
关键词
Combinatorial optimization; Large scale optimization; Metaheuristics
资金
- ARC (Australian Research Council) [DP190101271]
This paper introduces a new heuristic algorithm, LaPSO, which combines Lagrangian Relaxation and Particle Swarm Optimization, and incorporates a new repair heuristic called Largest Violation Perturbation (LVP) to solve the Maximum Edge Disjoint Paths (MEDP) problem. LaPSO outperforms both state-of-the-art heuristic methods and standard MIP solvers, demonstrating superior heuristic solutions and strong bounds within limited runtimes.
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 cur-rent 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. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据