Query:
学者姓名:陆永亮
Refining:
Year
Type
Indexed by
Source
Complex
Co-
Language
Clean All
Abstract :
The Set Orienteering Problem (SOP) is a variant of the popular Orienteering Problem (OP) arising from a number of real-life applications. The aim is to find a tour across a subset of customers, while maximizing the collected profit within a given travel time limit. In SOP, vertices (customers) are partitioned into clusters, where a profit is associated to each cluster. The profit of a cluster is collected only if at least one vertex belonging to the cluster is contained in the tour. For NP-hard problem, we present a highly effective hybrid evolutionary algorithm that integrates cluster-based crossover operator, a randomized mutation operator to generate multiple distinct promising offspring solutions, and a two-phase local refinement procedure that explores feasible and infeasible solutions in search of high-quality local optima. Extensive experiments 192 large benchmark instances show that the proposed algorithm significantly outperforms the existing approaches from the SOP literature. In particular, it reports improved best-known solutions (new lower bounds) for 54 instances, while matching the existing best-known for 133 instances. We further investigate the contribution of the key algorithmic elements to success of the proposed approach.
Keyword :
Heuristics Heuristics Hybrid evolutionary algorithm Hybrid evolutionary algorithm Orienteering problem Orienteering problem Tabu search Tabu search
Cite:
Copy from the list or Export to your reference management。
GB/T 7714 | Lu, Yongliang , Benlic, Una , Wu, Qinghua . An effective hybrid evolutionary algorithm for the set orienteering problem [J]. | INFORMATION SCIENCES , 2023 , 654 . |
MLA | Lu, Yongliang 等. "An effective hybrid evolutionary algorithm for the set orienteering problem" . | INFORMATION SCIENCES 654 (2023) . |
APA | Lu, Yongliang , Benlic, Una , Wu, Qinghua . An effective hybrid evolutionary algorithm for the set orienteering problem . | INFORMATION SCIENCES , 2023 , 654 . |
Export to | NoteExpress RIS BibTex |
Version :
Abstract :
The capacitated modular hub location problem is a realistic variant of the popular hub location problem arising from the design of telecommunications networks. Given a set of demand nodes, the problem consists in selecting a subset of nodes to represent hubs and assigning the rest of the nodes to the hub nodes, such that the transportation cost is minimized while satisfying the capacity constraints. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory to store blocks of solutions. At each iteration, the recombination operator uses these solution blocks to create an offspring solution. In this paper, we present a parallel adaptive memory algorithm for the capacitated modular hub location problem that stores both solution blocks and complete solutions in a shared memory for the creation of an offspring. Other distinguishing features of our proposed algorithm include specially designed recombination and mutation operators for search diversification, an effective tabu search procedure for search intensification, and parallel computing for global optimization. Extensive computational results on three well-known data sets of 170 benchmark instances show that the proposed algorithm competes very favorably with the state-of-the-art heuristics from the literature. In particular, it finds 115 improved best-known solutions (for more than 67% of the cases). Furthermore, we analyze the key algorithmic components and shed lights on their impact on the proposed algorithm.
Keyword :
Heuristics Heuristics Hub location problem Hub location problem Parallel computing Parallel computing Tabu search Tabu search
Cite:
Copy from the list or Export to your reference management。
GB/T 7714 | Wu, Qinghua , Sun, Zhe , Benlic, Una et al. A parallel adaptive memory algorithm for the capacitated modular hub location problem [J]. | COMPUTERS & OPERATIONS RESEARCH , 2023 , 153 . |
MLA | Wu, Qinghua et al. "A parallel adaptive memory algorithm for the capacitated modular hub location problem" . | COMPUTERS & OPERATIONS RESEARCH 153 (2023) . |
APA | Wu, Qinghua , Sun, Zhe , Benlic, Una , Lu, Yongliang . A parallel adaptive memory algorithm for the capacitated modular hub location problem . | COMPUTERS & OPERATIONS RESEARCH , 2023 , 153 . |
Export to | NoteExpress RIS BibTex |
Version :
Abstract :
In this paper, we study a variant of the orienteering problem called the clustered orienteering problem. In this problem, customers are grouped into clusters. A profit is associated with each cluster and is collected if and only if all customers in the cluster are served. A single vehicle is available to visit the customers. The goal is to maximize the total profits collected within a maximum travel time limit. To address this NP-hard problem, we propose the first evolutionary algorithm that integrates a backbone-based crossover operator and a destroy-and-repair mutation operator for search diversification and a solution-based tabu search procedure reinforced by a reinforcement learning mechanism for search intensification. The experiment results indicate that our algorithm outperforms the state-of-the-art algorithms from the literature on a wide range of 924 well-known benchmark instances. In particular, the proposed algorithm obtains new records (new lower bounds) for 14 instances and finds the best-known solutions for the remaining instances. Furthermore, a new set of 72 large instances with 50 to 100 clusters and at least 400 vertices is generated to evaluate the scalability of the proposed algorithm. Results show that the proposed algorithm manages to outperform three state-of-the-art COP algorithms. We also adopt our algorithm to solve a dynamic version of the COP considering stochastic travel time.(c) 2023 Elsevier B.V. All rights reserved.
Keyword :
Clustered orienteering problem Clustered orienteering problem Heuristics Heuristics Hybrid evolutionary algorithm Hybrid evolutionary algorithm Reinforcement learning Reinforcement learning Tabu search Tabu search
Cite:
Copy from the list or Export to your reference management。
GB/T 7714 | Wu, Qinghua , He, Mu , Hao, Jin-Kao et al. An effective hybrid evolutionary algorithm for the clustered orienteering problem [J]. | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH , 2023 , 313 (2) : 418-434 . |
MLA | Wu, Qinghua et al. "An effective hybrid evolutionary algorithm for the clustered orienteering problem" . | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 313 . 2 (2023) : 418-434 . |
APA | Wu, Qinghua , He, Mu , Hao, Jin-Kao , Lu, Yongliang . An effective hybrid evolutionary algorithm for the clustered orienteering problem . | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH , 2023 , 313 (2) , 418-434 . |
Export to | NoteExpress RIS BibTex |
Version :
Abstract :
The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.
Keyword :
Clustered traveling salesman Clustered traveling salesman Heuristics Heuristics Problem transformation Problem transformation Traveling salesman Traveling salesman
Cite:
Copy from the list or Export to your reference management。
GB/T 7714 | Lu, Yongliang , Hao, Jin-Kao , Wu, Qinghua . Solving the clustered traveling salesman problem via traveling salesman problem methods [J]. | PEERJ COMPUTER SCIENCE , 2022 , 7 . |
MLA | Lu, Yongliang et al. "Solving the clustered traveling salesman problem via traveling salesman problem methods" . | PEERJ COMPUTER SCIENCE 7 (2022) . |
APA | Lu, Yongliang , Hao, Jin-Kao , Wu, Qinghua . Solving the clustered traveling salesman problem via traveling salesman problem methods . | PEERJ COMPUTER SCIENCE , 2022 , 7 . |
Export to | NoteExpress RIS BibTex |
Version :
Abstract :
The cyclic cutwidth minimization problem (CCMP) is a graph layout problem that involves embedding a graph onto a circle to minimize the maximum cutwidth of the graph. In this paper, we present breakout local search (BLS) for solving CCMP, which combines a dedicated local search procedure to discover high-quality local optimal solutions and an adaptive diversification strategy to escape from local optima. Extensive computational results on a wide set of 179 publicly available benchmark instances show that the proposed BLS algorithm has excellent performance with respect to the best-performing state-of-the-art approaches in terms of solution quality and computational time. In particular, it reports improved best-known solutions for 31 instances, while finding matching best-known results on 139 instances.
Keyword :
Adaptive diversification Adaptive diversification Cyclic cutwidth Cyclic cutwidth Graph layout problem Graph layout problem Heuristics Heuristics
Cite:
Copy from the list or Export to your reference management。
GB/T 7714 | He, Mu , Wu, Qinghua , Lu, Yongliang . Breakout local search for the cyclic cutwidth minimization problem [J]. | JOURNAL OF HEURISTICS , 2022 , 28 (5-6) : 583-618 . |
MLA | He, Mu et al. "Breakout local search for the cyclic cutwidth minimization problem" . | JOURNAL OF HEURISTICS 28 . 5-6 (2022) : 583-618 . |
APA | He, Mu , Wu, Qinghua , Lu, Yongliang . Breakout local search for the cyclic cutwidth minimization problem . | JOURNAL OF HEURISTICS , 2022 , 28 (5-6) , 583-618 . |
Export to | NoteExpress RIS BibTex |
Version :
Abstract :
The capacitated minimum spanning tree (CMST) problem is a fundamental problem in telecommunication network design. Given a central node and a set of remote terminal nodes with specified demands for traffic, the goal of CMST is to find a minimum cost spanning tree (network) such that the traffic on any arc of the network satisfies the capacity constraint. To tackle this NP-hard problem, we propose an effective hybrid evolutionary algorithm that integrates a backbone-based crossover operator, a destroy-and-repair mutation operator to generate meaningful offspring solutions, and an intensification-driven adaptive tabu search procedure that considers both feasible and infeasible solutions in search of high-quality local optima. Extensive computational results on a set of 126 well-known CMST benchmark instances from the literature indicate that the proposed algorithm competes favorably with the state-of-the-art heuristics. For a selection of 25 most challenging CMST instances with unknown optimal solutions, the proposed algorithm reports new upper bounds (improved best-known solutions) in 9 cases, while reaching the best-known result for 12 instances. Furthermore, we provide experimental analyses to identify the key algorithmic features of the proposed approach.
Keyword :
Capacitated minimum spanning tree Capacitated minimum spanning tree Heuristics Heuristics Hybrid evolutionary algorithm Hybrid evolutionary algorithm Tabu search Tabu search
Cite:
Copy from the list or Export to your reference management。
GB/T 7714 | Lu, Yongliang , Benlic, Una , Wu, Qinghua . A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem [J]. | COMPUTERS & OPERATIONS RESEARCH , 2022 , 144 . |
MLA | Lu, Yongliang et al. "A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem" . | COMPUTERS & OPERATIONS RESEARCH 144 (2022) . |
APA | Lu, Yongliang , Benlic, Una , Wu, Qinghua . A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem . | COMPUTERS & OPERATIONS RESEARCH , 2022 , 144 . |
Export to | NoteExpress RIS BibTex |
Version :
Export
Results: |
Selected to |
Format: |