Anh Son Ta, Hoai An Le Thi, Trong Sy Ha: Solving Relaxation Orienteering Problem Using DCA-CUT.

Abstract: Orienteering problem is well-known as a NP-hard problem in transportation with many applications. This problem aims to find a path between a given set of control points, where the source and destination points are specified with respect to maximize the total score of collected points and satisfy the distance constraint. In this paper, we first analyze the structure of a generalized orienting problem and a new solution method, based on DC programming, DCA and Cutting plane method, is introduced. Preliminary numerical experiments are reported to show the efficiency of the proposed algorithm.

 

Keywords: Orienteering problem DC programming DC Algorithm Binary Linear Integer Program.

 

Download link