Optimization Models And Algorithms For Migratory Beekeeping Routing Problem Based On The Spatial-Temporal Pattern Of Nectar Sources

Apiculture has gained worldwide interest because of its remarkable contributions to the agricultural economy and environmental conservation.Compared with breeding the bees in a fixed position(i.e.,local beekeeping),migratory beekeeping,as a bee breeding technique for significantly increasing yield and efficiency,is extensively adopted in the apicultural practice.Based on the temporal-spatial distribution of nectar sources,migratory beekeepers always move the bee colonies to places where the forage is abundant at certain periods to produce,which can overcome the shortage of nectar sources in the local beekeeping mode and increase revenue.However,because of the lack of an overall routing plan,beekeepers who follow the experiential migratory routes frequently suffer income losses and opportunity costs since encountering unexpected congestions and detours detrimental to the production of bee products.The migratory beekeeping routing problem(MBRP)is proposed based on the practical background of the commercial apiculture industry.It optimizes both the routing scheme and migrating schedule to realize the maximization of global revenue for beekeepers by comprehensively considering factors such as the nectar source species,planting scales,flowering periods,product yields,the chronological succession of nectar sources,the transportation conditions,and the prices of bee products.The MBRP is a new variant of the vehicle routing problem but with significantly characteristic production time decisions at the network vertices(i.e.,nectar sources);only the overlaps between residence durations and flowering periods generate production benefits.For this novel productive-routing problem,the following contents are studied:(1)The Sales-oriented MBRP.With the comprehensive consideration of the attributes of nectar sources—such as the location,flowering periods,and yields—and the remote market sale prices of bee products gained from different nectar species,the sales-oriented MBRP aims to utilize the nectar sources efficiently and maximize the total revenue by optimizing the routing scheme,migrating schedule,and the selection of sales markets when meeting the environmental carrying capacity and timing constraints related to the flowering periods.Different sales visits to the remote markets cause different gains from the same products;in turn,these lead to different production time decisions at previously visited nectar source locations and even change the visit decisions for production.Based on these,a nonlinear model that incorporates the remote sales decisions is formulated,then linearized and decomposed using Dantzig–Wolfe decomposition method.In order to improve the solving efficiency,a column generation algorithm was designed for the solution of the degradation model,i.e.,the basic MBRP model(without considering remote sales),to obtain the suboptimal routes of sales-oriented MBRP.On this basis,we further propose a column generation method with the revised labeling algorithm for the subproblems to cope with the solution difficulty of salesoriented MBRP resulting from the complicated time decisions.The tests performed on instances and a real-world case demonstrate that the proposed algorithm is efficient for solving the sales-oriented MBRP.Compared with traditional routes,a more efficient overall routing schedule for migratory beekeepers is proposed.(2)The MBRP with pollination subsidy.To improve the use of the external benefits in MBRP,besides the original attributes,certain vertices on the MBRP network(i.e.,nectar source)further incorporate the attributes of the external benefits of bee pollination and pollination service time requirements—when resident duration satisfies the requirement of pollination service time,beekeepers can get the corresponding pollination subsidy.The government needs to reasonably allocate the budget for pollination subsidies to encourage beekeepers to visit and produce in the nectar sources that can produce significant external benefits and,hence,complete pollination service there to increase production and efficiency.Given the rational response from the beekeeper group,i.e.,the arrangement of migratory routes,under each pollination subsidy scheme,the government should optimize the subsidy scheme to maximize the comprehensive objective with economic benefits of bee products production and external benefits of pollination included.As the government and beekeeper group make subsidy and route decisions,respectively,they have an obvious leader-follower game relationship.Therefore,an integer linear bilevel programming model for migratory beekeeping routing with external benefits and pollination subsidies is formulated.Based on the proposed model transformed and decomposed,an implicit enumeration algorithm based on branch and price and cut method is proposed to solve the problem efficiently.The model and algorithm are beneficial to the sustainable development of apiculture by coordinating the government’s pursuit of social welfare of the government and beekeepers’ pursuit of economic benefits.(3)The Dynamic MBRP based on the information updating of nectar sources.With the uncertainty of nectar source conditions caused by the factors such as geographical conditions,weather,flowering rules of nectar source plants,and natural disasters,as well as the rolling updated nectar source information in the process of migratory beekeeping,the migratory routes are dynamically optimized and adjusted to cope with the production risk resulting from the uncertainty of nectar source conditions flexibly.Besides the uncertainty of general parameters(yield and price),the network nodes of dynamic MBRP further contain the uncertainty of time dimension(i.e.,flowering periods).The uncertainty of flowering periods will influence the visiting order of the vertices and the production time decisions and even influence the structure of the migratory network,which significantly increases the difficulty of the solution.The dynamic MBRP is formulated as a Markov Decision Process model based on discretizing the temporal-spatial relationships between nectar sources and beekeepers.After that,a tailored approximate dynamic programming algorithm is proposed to solve the dynamic MBRP to overcome the "dimension disaster" caused by the multidimensional state space related to the temporal-spatial relationships and the uncertainty of the nectar source information.The result comparison between the dynamic routing scheme and the deterministic routing scheme shows that the dynamic MBRP can significantly improve the production efficiency of migratory beekeepers in the long run.The above three research contents provide decision support for solving the problems of extensive production and low efficiency,the insufficient utilization of external benefits of bee pollination,and the production risks caused by the uncertainty of nectar source conditions in the apicultural practices,respectively.Through the modeling and algorithm design of these problems in production practices,managerial methods and suggestions for increasing production efficiency and sustainable development of the apicultural industry are provided.Based on the specific optimization contents and objective requirements,we innovatively propose and further enrich the MBRP,a productive-routing problem including time decisions,and put forward a set of adequate and effective modeling and solution methods for the MBRPs;meanwhile,the MBRPs also provide a reference for modeling and algorithm designing of other similar productive routing problems with timing decisions.