An iterated local search algorithm for the team orienteering problem with variable profits
The orienteering problem (OP) is a routing problem that has numerous applications in various domains such as logistics and tourism. The objective is to determine a subset of vertices to visit for a vehicle so that the total collected score is maximized and a given time budget is not exceeded. The ex...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Taylor & Francis
2018
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/49526/ |
| _version_ | 1848798016460292096 |
|---|---|
| author | Gunawan, Aldy Ng, Kien Ming Kendall, Graham Lai, Junhan |
| author_facet | Gunawan, Aldy Ng, Kien Ming Kendall, Graham Lai, Junhan |
| author_sort | Gunawan, Aldy |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | The orienteering problem (OP) is a routing problem that has numerous applications in various domains such as logistics and tourism. The objective is to determine a subset of vertices to visit for a vehicle so that the total collected score is maximized and a given time budget is not exceeded. The extensive application of the OP has led to many different variants, including the team orienteering problem (TOP) and the team orienteering problem with time windows. The TOP extends the OP by considering multiple vehicles. In this article, the team orienteering problem with variable profits (TOPVP) is studied. The main characteristic of the TOPVP is that the amount of score collected from a visited vertex depends on the duration of stay on that vertex. A mathematical programming model for the TOPVP is first presented and an algorithm based on iterated local search (ILS) that is able to solve modified benchmark instances is then proposed. It is concluded that ILS produces solutions which are comparable to those obtained by the commercial solver CPLEX for smaller instances. For the larger instances, ILS obtains good-quality solutions that have significantly better objective value than those found by CPLEX under reasonable computational times. |
| first_indexed | 2025-11-14T20:13:04Z |
| format | Article |
| id | nottingham-49526 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:13:04Z |
| publishDate | 2018 |
| publisher | Taylor & Francis |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-495262020-05-04T19:27:17Z https://eprints.nottingham.ac.uk/49526/ An iterated local search algorithm for the team orienteering problem with variable profits Gunawan, Aldy Ng, Kien Ming Kendall, Graham Lai, Junhan The orienteering problem (OP) is a routing problem that has numerous applications in various domains such as logistics and tourism. The objective is to determine a subset of vertices to visit for a vehicle so that the total collected score is maximized and a given time budget is not exceeded. The extensive application of the OP has led to many different variants, including the team orienteering problem (TOP) and the team orienteering problem with time windows. The TOP extends the OP by considering multiple vehicles. In this article, the team orienteering problem with variable profits (TOPVP) is studied. The main characteristic of the TOPVP is that the amount of score collected from a visited vertex depends on the duration of stay on that vertex. A mathematical programming model for the TOPVP is first presented and an algorithm based on iterated local search (ILS) that is able to solve modified benchmark instances is then proposed. It is concluded that ILS produces solutions which are comparable to those obtained by the commercial solver CPLEX for smaller instances. For the larger instances, ILS obtains good-quality solutions that have significantly better objective value than those found by CPLEX under reasonable computational times. Taylor & Francis 2018-01-16 Article PeerReviewed Gunawan, Aldy, Ng, Kien Ming, Kendall, Graham and Lai, Junhan (2018) An iterated local search algorithm for the team orienteering problem with variable profits. Engineering Optimization . ISSN 1029-0273 Orienteering problem variable profit mathematical programming model iterated local search http://www.tandfonline.com/doi/full/10.1080/0305215X.2017.1417398 doi:10.1080/0305215X.2017.1417398 doi:10.1080/0305215X.2017.1417398 |
| spellingShingle | Orienteering problem variable profit mathematical programming model iterated local search Gunawan, Aldy Ng, Kien Ming Kendall, Graham Lai, Junhan An iterated local search algorithm for the team orienteering problem with variable profits |
| title | An iterated local search algorithm for the team orienteering problem with variable profits |
| title_full | An iterated local search algorithm for the team orienteering problem with variable profits |
| title_fullStr | An iterated local search algorithm for the team orienteering problem with variable profits |
| title_full_unstemmed | An iterated local search algorithm for the team orienteering problem with variable profits |
| title_short | An iterated local search algorithm for the team orienteering problem with variable profits |
| title_sort | iterated local search algorithm for the team orienteering problem with variable profits |
| topic | Orienteering problem variable profit mathematical programming model iterated local search |
| url | https://eprints.nottingham.ac.uk/49526/ https://eprints.nottingham.ac.uk/49526/ https://eprints.nottingham.ac.uk/49526/ |