A branch-and-cut algorithm for the target visitation problem

被引:0
作者
Hildenbrandt, Achim [1 ]
机构
[1] Heidelberg Univ, INF 205, D-69120 Heidelberg, Germany
关键词
Traveling salesman problem; Linear ordering problem; Polyhedra theory; Branch-and-cut;
D O I
10.1007/s13675-019-00111-x
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we consider the target visitation problem (TVP) which arises in the context of disaster treatment. Mathematically speaking, the problem is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance travelled, a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. In this paper, we point out some polyhedral properties, develop a branch-and-cut algorithm for solving the TVP to optimality and present some computational results.
引用
收藏
页码:209 / 242
页数:34
相关论文
共 50 条
[41]   A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants [J].
Jozefowiez, Nicolas ;
Laporte, Gilbert ;
Semet, Frederic .
COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (11) :1534-1542
[42]   A branch-and-cut algorithm for the connected max- k-cut problem [J].
Healy, Patrick ;
Jozefowiez, Nicolas ;
Laroche, Pierre ;
Marchetti, Franc ;
Martin, Sebastien ;
Roka, Zsuzsanna .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2024, 312 (01) :117-124
[43]   A branch-and-cut algorithm for solving the Non-Preemptive Capacitated Swapping Problem [J].
Erdogan, Guenes ;
Cordeau, Jean-Francois ;
Laporte, Gilbert .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) :1599-1614
[44]   An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem [J].
Minh Anh Nguyen ;
Hai Long Luong ;
Minh Hoàng Hà ;
Ha-Bang Ban .
4OR, 2023, 21 :609-637
[45]   A Branch-and-Cut Algorithm for Partition Coloring [J].
Frota, Yuri ;
Maculan, Nelson ;
Noronha, Thiago F. ;
Ribeiro, Celso C. .
NETWORKS, 2010, 55 (03) :194-204
[46]   A branch-and-cut algorithm for a skip pick-up and delivery problem [J].
Belenguer, Jose M. ;
Cubillos, Maximiliano ;
Wohlk, Sanne .
COMPUTERS & OPERATIONS RESEARCH, 2024, 168
[47]   A Branch-and-Cut algorithm for the stochastic uncapacitated lot-sizing problem [J].
Guan, YP ;
Ahmed, S ;
Nemhauser, GL ;
Miller, AJ .
MATHEMATICAL PROGRAMMING, 2006, 105 (01) :55-84
[48]   A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem [J].
Avila, Thais ;
Corberan, Angel ;
Plana, Isaac ;
Sanchis, Jose M. .
TRANSPORTATION SCIENCE, 2016, 50 (02) :750-761
[49]   A branch-and-cut framework for the consistent traveling salesman problem [J].
Subramanyam, Anirudh ;
Gounaris, Chrysanthos E. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 248 (02) :384-395
[50]   A branch-and-cut algorithm for the one-commodity pickup and delivery location routing problem [J].
Dominguez-Martin, Bencomo ;
Hernandez-Perez, Hipolito ;
Riera-Ledesma, Jorge ;
Rodriguez-Martin, Inmaculada .
COMPUTERS & OPERATIONS RESEARCH, 2024, 161