Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem SCIE SCOPUS

Title
Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem
Authors
Kim, HyunjoonKim, Byung-In
Date Issued
2022-12
Publisher
Elsevier B.V.
Abstract
© 2022 Elsevier B.V.The multi-profit orienteering problem (MPOP), a variant of the orienteering problem, was introduced in 2020. In MPOP, each vertex has multiple profits, and a profit is determined by the time of visit. Therefore, the vertices to visit as well as the visit sequence and visit times must be optimally selected. The purpose of MPOP is to maximize the total profits collected from the vertices while satisfying the travel time limit constraint. To date, no exact algorithm has been developed for MPOP. This paper proposes a dynamic programming (DP)-based exact algorithm for MPOP for the first time. The proposed algorithm combines DP, ng-route relaxed DP, incumbent solution generation algorithms, and bounding rules. The proposed algorithm can obtain the optimal solutions for 33 previously unsolved benchmark instances and update the best solutions in 23 benchmark instances for MPOP.
URI
https://oasis.postech.ac.kr/handle/2014.oak/112914
DOI
10.1016/j.ejor.2022.02.045
ISSN
0377-2217
Article Type
Article
Citation
European Journal of Operational Research, vol. 303, no. 2, page. 550 - 566, 2022-12
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

김병인KIM, BYUNG IN
Dept of Industrial & Management Enginrg
Read more

Views & Downloads

Browse