6533b86cfe1ef96bd12c8b9b

RESEARCH PRODUCT

The Steiner Traveling Salesman Problem and its extensions

Antonio Martinez-sykoraGilbert LaporteJessica Rodríguez-pereiraElena FernándezEnrique Benavent

subject

Discrete mathematics050210 logistics & transportation021103 operations researchInformation Systems and ManagementGeneral Computer ScienceComputer science05 social sciences0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchTravelling salesman problemIndustrial and Manufacturing EngineeringGraphVertex (geometry)Modeling and Simulation0502 economics and businessInteger programmingBranch and cutMathematicsofComputing_DISCRETEMATHEMATICS

description

Abstract This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.

yearjournalcountryeditionlanguage
2019-10-16European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2019.04.047