A variable neighborhood search to solve migratory beekeeping routing problem
Loading...
Date
2021-12
Authors
Qiu, Xintong
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Commercial apiculture plays an important role because of its contributions to reducing poverty and conserving biodiversity. In this thesis, a migratory beekeeping routing problem (MBRP) is studied and a mathematical model of MBRP is established to optimize the total profit of beekeepers, comprehensively considering flower region allocation, flowering periods, environment capacity of flower regions, flexible terminal depots, selection of best markets on the routes and so on. A variable neighbourhood search (VNS) algorithm involving an initial solution generation procedure based on greedy strategy, a perturbation procedure and a local search procedure is proposed to solve the complicated MBRP. Finally, thirty computational instances reflecting structural factors of the MBRP are utilized to test the proposed VNS. Reasonable near-optimal solutions which are averagely 2.68% worse than the global optimal solutions of CG-LA in (Ma, Yang, Dai, & Shen, 2020) are finally obtained through our VNS. The average consumption of CPU time decreases dramatically from 1930 seconds in CG-LA to only 144 seconds in our VNS. Besides, more experiments on features of VNS and MBRP are conducted to gain more insights into them. Theoretically, this is the first application of a meta-heuristic method (VNS) on MBRP. The results indicate the feasibility and efficiency of the VNS to achieve acceptably good near-optimal solutions while reducing computation time sharply compared to the exact algorithms in (Ma et al., 2020). Practically, the outcome of this thesis can help related organizations to change traditional beekeeping production and operation methods, enhancing production efficiency and profit and reducing costs and resource waste.
Description
Keywords
Migratory Beekeeping Routing Problem, MBRP, Variable Neighborhood Search, VNS, Vehicle Routing Problem