Arrival and service time dependencies in the single- and multi-visit selective traveling salesman problem

David Canca, Eva Barrena, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

Abstract

We analyze several time dependency issues for the selective traveling salesman problem with time-dependent profits. Specifically, we consider the case in which the profit collected at a vertex depends on the service time, understood as the time spent at this vertex, and when the service time at each vertex depends on the arrival time at the vertex. For each of these two cases, we formulate two continuous-time problems: (i) a vertex can be visited at most once, and (ii) vertices may be visited more than once. In each case, we consider general profit functions at the vertices, i.e., the profit functions are not limited to monotonic functions of time. We also formulate the problems as discrete-time problems using appropriate variants of an auxiliary time-extended graph, and we solve them with Gurobi. We apply our methodology to two sets of instances. First, we use a set of artificial instances to illustrate the main differences amongst the different versions of the problem. We then solve several instances adapted from TSPLIB to evaluate the computational capabilities of the methodology.

Original languageEnglish
Article number106632
JournalComputers and Operations Research
Volume166
Early online date27 Mar 2024
DOIs
Publication statusPublished - 30 Jun 2024

Data Availability Statement

Data will be made available on request.

Funding

This work was partly supported by the Spanish Ministry of Science and Innovation and the European Regional Development Fund (ERDF) under grants PDC2021-121021-C21, RED2022-134703-T, PID2019-104263RB-C41, and PID2022-139543OB-C41, and by the Andalusian Regional Government, Spain (Consejería de Economía, Conocimiento, Empresas y Universidad) under the I+D+i FEDER Andalucía 2014–2020 initiative, grant US-1381656. This support is gratefully acknowledged. Thanks are due to an anonymous referee for several valuable suggestions. This work was partly supported by the Spanish Ministry of Science and Innovation and the European Regional Development Fund (ERDF) under grants PDC2021-121021-C21 , RED2022-134703-T , PID2019-104263RB-C41 , and PID2022-139543OB-C41 , and by the Andalusian Regional Government (Consejería de Economía, Conocimiento, Empresas Universidad) under the I+D+i FEDER Andalucía 2014–2020 initiative, grant US-1381656 . This support is gratefully acknowledged. Thanks are due to an anonymous referee for several valuable suggestions.

FundersFunder number
Ministerio de Ciencia e Innovacion
Consejería de Economía, Conocimiento, Empresas Universidad
Consejería de Economía, Conocimiento, Empresas y Universidad
Andalusian Regional Government
I+D+i FEDERUS-1381656
European Regional Development FundRED2022-134703-T, PDC2021-121021-C21, PID2019-104263RB-C41

    Keywords

    • Selective traveling salesman problem
    • Service time-dependent profit
    • Single- and multi-visit
    • Time-dependent service time

    ASJC Scopus subject areas

    • General Computer Science
    • Modelling and Simulation
    • Management Science and Operations Research

    Fingerprint

    Dive into the research topics of 'Arrival and service time dependencies in the single- and multi-visit selective traveling salesman problem'. Together they form a unique fingerprint.

    Cite this