New Formulations for the Team Orienteering Problem
Main Article Content
Abstract
Routing problems have many practical applications in distribution and logistics management. The Traveling Salesman Problem (TSP) and its variants lie at the heart of routing problems. The Orienteering Problem (OP) is a subset selection version of well-known TSP which comes from an outdoor sport played on mountains. In the OP, the traveller must finish its journey within a predetermined time (cost, distance), and gets a gain (profit, reward) from the visited nodes. The objective is to maximize the total gain that the traveller collects during the predetermined time. The OP is also named as the selective TSP since not all cities have to be visited. The Team Orienteering Problem (TOP) is the extension of OP by multiple-traveller. As far as we know, there exist a few formulations for the TOP. In this paper we present two new integer linear programming formulations (ILPFs) for the TOP with O(n2) binary variables and O(n2) constraints, where n is the number of nodes on the underlying graph. The proposed formulations can be directly used for the OP when we take the number of traveller as one. We demonstrate that, additional restrictions and/or side conditions can be easily imported for both of the formulations. The performance of our formulations is tested on the benchmark instances from the literature. The benchmark instances are solved via CPLEX 12.6 by using the proposed and existing formulations. The computational experiments demonstrate that both of the new formulations outperform the existing one. The new formulations are capable of solving optimally most of the benchmark instances, which have solved by using special heuristics so far. As a result, the proposed formulations can be used to find the optimal solution of small- and moderate-size real life OP and TOP by using an optimizer.
Keywords: Traveling salesman problem, orienteering problem, modeling;
Downloads
Article Details
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
References
Butt, S., Cavalier, T. (1994). A heuristic for the multiple tour maximum collection problem. Computers and Operations Research, 21, 101 – 111.
Butt, S., Ryan, D. (1999). An optimal solution procedure for the multiple tour maximum collection problem using column generations. Computers and Operations Research, 26, 427 - 441.
Chao, I., Golden, B., Wasil, E. (1996). The team orienteering problem. European Journal of Operational Research, 88, 464 – 474.
Dang, D.-C., Guibadj, R.N., Moukrim, A. (2013). An effective pso-inspired algorithm for the team orienteering problem. European Journal of Operational Research, 229(2), 332 – 344.
Dantzing, G., Fulkerson, R., Johnson, S. (1954). Solution of a large-scale traveling salesman problem. Operations Research, 2, 393 - 410.
Golden, B., Levy, L., Vohra, R. (1987). The Orienteering Problem. Naval Research Logistics, 34, 307 - 318.
Ke, L., Archetti, C., Feng, Z. (2008). Ants can solve the team orienteering problem. Computers and Industrial Engineering, 54, 648 – 665.
Laporte, G., Martello, S. (1990). The Selective Travelling Salesman Problem. Discrete Applied Mathematics, 26, 193 - 207.
Miller, C.E., Tucker, A. W., Zemlin, R.A. (1960). Integer Programming Formulations and Traveling Salesman Problems. Journal of the Association for Computing Machinery, 7, 326 - 329.
Poggi, M., Viana, H., Uchoa, E. (2010). The Team Orienteering Problem: Formulations and Branch-Cut and Price. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10), 142 – 155.
Tang, H., Miller-Hooks, E. (2005). A tabu search heuristic for the team orienteering problem. Computers and Operations Research, 32, 1379 - 1407.
Tsiligrides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35, 797 - 809.
Vansteenwegen, P., Souffriau, W., Oudheusden, D.V. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209, 1 - 10.