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

Hyunjoon Kim and Byung-In Kim

European Journal of Operational Research, 2022, vol. 303, issue 2, 550-566

Abstract: 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.

Keywords: Dynamic programming; Bounding; Multi-profit orienteering problem; Exact approach (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722001667
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:303:y:2022:i:2:p:550-566

DOI: 10.1016/j.ejor.2022.02.045

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().