The multi-profit orienteering problem. (November 2020)

• Record Type: Journal Article
• Authors: Kim, Hyunjoon; Kim, Byung-In; Noh, Dong-jin
• Is Part Of: Computers & industrial engineering. Volume 149(2020)
• Publication Date: 2020-11
• Subjects: Multi-profit orienteering problem -- Simulated annealing -- Orienteering problem -- Longest path problem -- Hybrid heuristic algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106808
• Languages: English
• ISSNs: 0360-8352

Abstract

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.