The Prize Collecting Traveling Salesman Problem (PCTSP) represents a generalization of the well-known Traveling Salesman Problem. The PCTSP can be associated with a salesman that collects a prize in each visited city and pays a penalty for each unvisited city, with travel costs among the cities. The objective is to minimize the sum of the costs of the tour and penalties, while collecting a minimum amount of prize. This paper suggests MIP-based heuristics and a branch-and-cut algorithm to solve the PCTSP. Experiments were conducted with instances of the literature, and the results of our methods turned out to be quite satisfactory.
Keywords: prize-collecting traveling salesman problem, MIP heuristics, Branch-and-cut
@article{RO_2021__55_S1_S719_0,
author = {Cl{\'\i}maco, Glaubos and Simonetti, Luidi and Rosseti, Isabel},
title = {A {Branch-and-Cut} and {MIP-based} heuristics for the {Prize-Collecting} {Travelling} {Salesman} {Problem}},
journal = {RAIRO. Operations Research},
pages = {S719--S726},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020002},
mrnumber = {4223136},
zbl = {1472.90109},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020002/}
}
TY - JOUR AU - Clímaco, Glaubos AU - Simonetti, Luidi AU - Rosseti, Isabel TI - A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem JO - RAIRO. Operations Research PY - 2021 SP - S719 EP - S726 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020002/ DO - 10.1051/ro/2020002 LA - en ID - RO_2021__55_S1_S719_0 ER -
%0 Journal Article %A Clímaco, Glaubos %A Simonetti, Luidi %A Rosseti, Isabel %T A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem %J RAIRO. Operations Research %D 2021 %P S719-S726 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020002/ %R 10.1051/ro/2020002 %G en %F RO_2021__55_S1_S719_0
Clímaco, Glaubos; Simonetti, Luidi; Rosseti, Isabel. A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem. RAIRO. Operations Research, Tome 55 (2021), pp. S719-S726. doi: 10.1051/ro/2020002
and , Hybrid branching. In: International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Springer (2009) 309–311.
, , and , New approximation guarantees for minimum-weight -trees and prize-collecting salesmen. SIAM J. Comput. 28 (1998) 254–262. | MR | Zbl | DOI
, The prize collecting traveling salesman problem. Networks 19 (1989) 621–636. | MR | Zbl | DOI
, The Prize Collecting Traveling Salesman Problem and its Applications. Springer, Boston, MA (2007). | DOI
, Primal heuristics for mixed integer programs (2006).
, Heuristics of the branch-cut-and-price-framework scip. In: Operations Research Proceedings 2007. Springer (2008) 31–36. | Zbl | DOI
, , and , A note on the prize collecting traveling salesman problem. Math. Program. 59 (1993) 413–420. | MR | Zbl | DOI
and , Hybrid algorithms with detection of promising areas for the prize collecting travelling salesman problem. In: Fifth International Conference on Hybrid Intelligent Systems (HIS’05). IEEE (2005) 49–54.
and , About preflow algorithms for the minimum flow problem. WSEAS Trans. Comput. Res. 3 (2008) 35–42.
, , and , Combining integer linear programming with a state-of-the-art heuristic for the 2-path network design problem. Int. Trans. Oper. Res. 26 (2018) 615–641. | MR | Zbl | DOI
, , and , A lagrangian heuristic for the prize collectingtravelling salesman problem. Ann. Oper. Res. 81 (1998) 289–306. | MR | Zbl | DOI
and , An additive approach for the optimal solution of the prize collecting traveling salesman problem. Veh. Routing: Methods Stud. 231 (1988) 319–343. | MR | Zbl
, and , New insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. 40 (1992) 1086–1094. | MR | Zbl | DOI
and , The christofides approximation algorithm. In: Algorithm Design and Applications. Wiley (2015) 513–514.
, Genetic Algorithm Essentials. In Vol. 670 of Studies in Computational Intelligence. Springer (2017). | MR | Zbl
, Tabu search. In: Handbook of Heuristics (2018) 741–758. | DOI
, , and , A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. Eur. J. Oper. Res. 220 (2012) 270–285. | MR | Zbl | DOI
PassMark, CPU Benchmarks. Available from: https://www.cpubenchmark.net/compare.php (2019).
, and , A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem. Electron. Notes Discrete Math. 41 (2013) 261–268. | DOI
, , and , A biased random-key genetic algorithm for the maximum quasi-clique problem. Eur. J. Oper. Res. 271 (2018) 849–865. | MR | Zbl | DOI
and , Optimization by GRASP. Springer (2016). | MR | Zbl
, , , and , A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems. J. Heuristics 21 (2015) 687–717. | Zbl | DOI
and , Problemas de coleta de prêmios seletiva. In: Simpósio Brasileiro de Pesquisa Operacional (SBPO) 35 (2003) 1359–1371.
and , Integer and Combinatorial Optimization. John Wiley & Sons (2014). | MR | Zbl
Cité par Sources :
