Research On Models And Algorithms For Several Orienteering Problems

The orienteering problem is a routing problem. This dissertation firstly gave a review of the orienteering problem in the national and international literature. Then three problems were proposed which were the orienteering problem with compulsory vertices and time window, the time-dependent orienteering problem with compulsory vertices and the capacitated orienteering problem with time window. The dissertation studied these problems in the problem description, the model foundation, and the algorithm design. Because of the complexity of the orienteering problem, it is very difficult and important to have an effective and efficient algorithm to solve it. Several common heuristics and genetic algorithms to solve each problem were mainly designed in the dissertation. Based on characteristics of problems,some heuristic rules and methods used in similar problems, effect and efficiency were traded off in the genetic algorithms for each problem.In the thought of network flow, a mathematic model was made for the orienteering problem with compulsory vertices and time window. Then the route order and the priority rules were found and used in a greedy algorithm to solve the problem. What's more, an improved genetic algorithm involving the greedy algorithm was designed for the problem. Finally, the effect and the efficiency between different algorithms were compared.Minimizing the total time of compulsory vertices and maximizing scores per hour were regarded as important heuristic rules in the time-dependent orienteering problem with compulsory vertices. Based on these rules, a greedy algorithm were designed and used to solve a case. Also, a genetic algorithm for the problem was proposed.The capacitated orienteering problem with time window is a multi-constraints problem. To solve it well, an iterated local search algorithm was designed as well as a genetic one. The former combined an insert step and a shaking step to escape from local optima. The latter used a penalty function and the gene recombination to deal with constraints.The study of models and algorithms for different orienteering problems extends theories of the route optimization and the algorithm. Meanwhile it can be used for the decision support in similar routing problems.