The multi-profit orienteering problem. (November 2020) - Kim, Hyunjoon; Kim, Byung-In; Noh, Dong-jin
Highlights: The multi-profit orienteering problem (MPOP) is newly defined. A mixed integer programming model for the MPOP is developed. A benchmark set for the MPOP is introduced. A visiting-time optimization algorithm is developed for the sub-problem of MPOP. An efficient simulated annealing algorithm is proposed for the MPOP. Abstract: The orienteering problem (OP), which is a selective version of the traveling salesman problem, has been widely studied by many researchers in recent years. The purpose of the OP is to maximise profits collected from customers in a limited time period, during which all customers cannot be visited. In this paper, we introduce a new type of OP called the multi-profit orienteering problem (MPOP). In the MPOP, each customer vertex has a time-dependent profit such that its value varies on the basis of visiting time. To maximise the total profit, a vehicle should carefully select both the customer vertices and visiting time. We introduce a benchmark problem set for the MPOP and propose a mathematical model and a hybrid heuristic algorithm to solve it. Experimental results demonstrate that the proposed algorithm can solve most of the instances well within a reasonable time.