Research And Application On Orienteering Problem With Variable Profits

Orienteering Problem(OP)is a special kind of NP-hard combinatorial optimization problem,which needs to ordered through some points with profits under a specified time limit,and form a path to make the total profits is biggest.Because of the good model characteristics,the OP has gained significant popularity over the past few years within industrial and academic circles at home and abroad.Its basic models and variants are widely used in the practical application scenarios such as travel planning,logistics transportation,disaster relief,location planning and so on,to optimize resource allocation,cost reduction,and obtain maximum benefits.The OP can be divided into single path Orienteering Problem(OP)and Team Orienteering Problem(TOP)according to the number of paths to be solved.This paper focuses on single path orienteering problems.After introducing the research status at home and abroad,this paper leads to the study of two kinds of orienteering problems with variable profits,taking into account the two categories of the problem: one is the orienteering problem with variable profitss in the whole time limit,which is called the Generalized Orienteering Problem with Variable Profits(GOPVP);the other is the orienteering problem of variable profits in the time window,called the Orienteering Problem with Time Windows and Variable Profits(OPTWVP).Two types Orienteering Problems with variable profits also enriched the research in the field of orienteering,and are applied to the actual scenario of path optimization to reflect its application value.Specifically,considering the actual situation of post-disaster search and rescue,each rescue site has many different types and levels of salvage materials that are of different importance,and its value will face the risk of being destroyed with the extension of rescue time.It is necessary to plan the optimal search and rescue routes within a limited time to reduce losses and ensure maximum benefits.Therefore,it is necessary to study the optimization problem of the decline of multiple types of returns over time,which is called Generalized Orienteering Problem with Variable Profits(GOPVP).In tourist trip design problem,due to the limitation of the opening time of the points of interest(POIs),the tourists cannot finish the recommended playing time,resulting in the inability to experience the fun of the POI.To solve this problem,an Orienteering Problem with Time Windows and Variable Profits(OPTWVP)problem is proposed.After describing the problems of GOPVP and OPTWVP separately,the problems were modeled with the maximize profit,and the improved genetic algorithm is designed to solve the Orienteering problem variable profits of two different situations.Because the Orienteering Problem is a complex combinatorial optimization problem,designing a fast and efficient solution algorithm is the key and difficult point in the research at home and abroad.The improved genetic algorithm proposed in this paper improves the solution of the problem from two aspects:(1)based on the characteristics of the variable profits,using the targeted heuristic information to help the algorithm select new points to construct a competitive path;(2)the genetic algorithm itself is easy to be precocious and fall into the local optimal.Integrating the niching idea and multiple local search operations to avoid premature convergence and improve the local search capability of the algorithm.Simulation experiments were conducted on multiple public data sets,and compared with the research progress methods respectively,the superiority of the algorithm was verified.At the same time,the algorithm and model are applied to real data,indicating the feasibility of the algorithm.Starting from the actual application situation,considering the two-variety variable orienteering problem,it not only enriches the research in the field of orienteering problems,but also provides decision-making reference and a more efficient and rapid planning path for similar practical applications.