A cutting-plane algorithm for an orienteering problem with mandatory visits and simultaneous production.

International Journal of Production Research. Jun2025, Vol. 63 Issue 12, p4287-4305. 19p.

This work investigates an orienteering problem with mandatory visits and simultaneous production (denoted by OPMV-SP) in additive manufacturing, where some nodes must be visited and others are optional, and the objective is to maximise the total collected scores. The problem is firstly formulated as a mixed-integer linear programming (MILP) model. Four sets of valid inequalities are then introduced to enhance the MILP. Based on the MILP, an exact method namely cutting-plane algorithm (CPA) is developed and evaluated on both benchmark and simulated instances. The results of benchmarks demonstrate that CPA is competitive, proving the optimality for 191 out of 202 feasible instances. Additionally, the performance of different combinations of valid inequalities are evaluated. Sensitivity analysis on the effects of mandatory visits and waiting times offers managerial insights for production and delivery strategies. The results of simulated instances of real-world cases further demonstrate CPA's efficiency and effectiveness. [ABSTRACT FROM AUTHOR]

*Linear programming, *Algorithms, Orienteering, Orienteers, Sensitivity analysis

Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)