Palace: A Parallel Adaptive Local-Search Algorithm Based on Competition and Evolution for Orienteering Problems and Variants

Preprints.org

Abstract

A number of challenging combinatorial optimization problems in logistics, transportations, aeronautics, and astronautics can be modeled as orienteering problems (OPs). To address the classic OP and its real-world variants, a parallel adaptive local-search algorithm based on competition and evolution (Palace) is proposed in this paper. In this algorithm, the parallelism runs proper local-search metaheuristics and operators to obtain the population per generation; then the competition grades those metaheuristics and operators to highlight the outperforming and eliminate the underperforming; also, the evolution explores large solution space and reproduces the best solutions for next generation. In this manner, the parallelism, competition, and evolution are organized in an easy-to-use algorithm and enable the expansibility, adaptivity, and exploration abilities, respectively. The Palace is examined on the classic and real-world Benchmarks about the OP, the time-dependent/independent OP with time windows, and the unmanned aerial vehicle and agile earth observation satellite planning. As a result, the Palace shows good performance in applicability and effectiveness in comparison with the state-of-the-art algorithms.

Authors 4

1. Haiwei Lei corresponding

   Zhejiang University

   Affiliation as printed

   . Key Laboratory of Excited-State Materials of Zhejiang Province , Department of Chemistry , Zhejiang University , Hangzhou 310027 , China

   Key Laboratory of Excited-State Materials of Zhejiang Province , Department of Chemistry , Zhejiang University , Hangzhou 310027 , China

   . Key Laboratory of Excited-State Materials of Zhejiang Province, Department of Chemistry, Zhejiang University, Hangzhou 310027, China

2. Yonghao Du Aachen Leiden Institute of Advanced Computer Science

   Leiden University · National University of Defense Technology

   Affiliation as printed

   . College of Systems Engineering , National University of Defense Technology , Changsha 410072 , China

   . Leiden Institute of Advanced Computer Science , Leiden University , Leiden 2332 CA , Netherlands

   College of Systems Engineering , National University of Defense Technology , Changsha 410072 , China

   Leiden Institute of Advanced Computer Science , Leiden University , Leiden 2332 CA , Netherlands

   . College of Systems Engineering, National University of Defense Technology, Changsha 410072, China

   . Leiden Institute of Advanced Computer Science, Leiden University, Leiden 2332 CA, Netherlands

3. Lining Xing

   Xidian University

   Affiliation as printed

   . School of Electronic Engineering , Xidian University , Xian , 710000 , China

   School of Electronic Engineering , Xidian University , Xian , 710000 , China

   . School of Electronic Engineering, Xidian University, Xian, 710000, China

4. Yingwu Chen

   National University of Defense Technology

   Affiliation as printed

   . College of Systems Engineering , National University of Defense Technology , Changsha 410072 , China

   College of Systems Engineering , National University of Defense Technology , Changsha 410072 , China

   . College of Systems Engineering, National University of Defense Technology, Changsha 410072, China