The orienteering problem with compulsory nodes and time window

The orienteering problem (OP) is a well established problem in combinatorial optimization. In this paper, we generalize the orienteering problem and propose a new type of problem-the orienteering problem with compulsory nodes and time window (OPCNTW). We first formulate the orienteering problem with compulsory nodes and time window into an integer linear programming base on network flow theory. Then we solve the integer linear programming model by Lingo software to obtain the exact optimal solution for small size of problem. Since it is time consuming to solve the integer linear programming for large size of the problem, we propose the route order and the priority rules, and give a heuristic algorithm based on these rules for solving the large size of the problem. Finally, we give some computational results of both exact and heuristic algorithms and analyze the simulation results. The results show that our algorithms is efficient.