Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm
- PDF / 823,570 Bytes
- 13 Pages / 595.22 x 842 pts (A4) Page_size
- 46 Downloads / 167 Views
1
Frontiers of Information Technology & Electronic Engineering www.jzus.zju.edu.cn; engineering.cae.cn; www.springerlink.com ISSN 2095-9184 (print); ISSN 2095-9230 (online) E-mail: [email protected]
Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm* Hu-sheng WU1, Jun-jie XUE2, Ren-bin XIAO‡3, Jin-qiang HU1 1
School of Equipment Management and Support, Armed Police Force Engineering University, Xi’an 710086, China 2
3
Air Traffic Control and Navigation College, Air Force Engineering University, Xi’an 710051, China
School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China E-mail: [email protected]; [email protected]; [email protected]; [email protected] Received Aug. 26, 2019; Revision accepted Dec. 2, 2019; Crosschecked Apr. 10, 2020
Abstract: To address indeterminism in the bilevel knapsack problem, an uncertain bilevel knapsack problem (UBKP) model is proposed. Then, an uncertain solution for UBKP is proposed by defining the E Nash equilibrium and E Stackelberg–Nash equilibrium. To improve the computational efficiency of the uncertain solution, an evolutionary algorithm, the improved binary wolf pack algorithm, is constructed with one rule (wolf leader regulation), two operators (invert operator and move operator), and three intelligent behaviors (scouting behavior, intelligent hunting behavior, and upgrading). The UBKP model and the E uncertain solution are applied to an armament transportation problem as a case study. Key words: Bilevel knapsack problem; Uncertainty; Improved binary wolf pack algorithm https://doi.org/10.1631/FITEE.1900437 CLC number: TP18
1 Introduction The bilevel knapsack problem (BKP) is a typical bilevel programming problem that models the hierarchical relationship between two autonomous, and possibly conflicting, decision-makers (the leader and the follower). BKP was first studied by Dempe and Richter (2000). In this problem, the follower solves a 0–1 knapsack problem subject to the capacity set by the leader. The leader earns a profit from the items selected by the follower, and both decision-makers ‡
Corresponding author Project supported by the National Science and Technology Innovation 2030 Major Project of the Ministry of Science and Technology of China (No. 2018AAA0101200), the National Natural Science Foundation of China (No. 61502534), the Natural Science Foundation of Shaanxi Province, China (No. 2020JQ-493), and the Domain Foundation of China (No. 61400010304) ORCID: Hu-sheng WU, https://orcid.org/0000-0003-0692-7467; Ren-bin XIAO, https://orcid.org/0000-0003-0951-2734 © Zhejiang University and Springer-Verlag GmbH Germany, part of Springer Nature 2020 *
seek to maximize their individual profits. BKP is formulated as a mixed-integer bilevel programming problem. Recently, researchers have increasingly focused on BKP, and several types of algorithms have been developed to solve BKP. Such algorithms include branch-and-cut (Özaltın et al., 2010), approximation (Qiu and Kern
Data Loading...
