TY - JOUR
T1 - Arrival and service time dependencies in the single- and multi-visit selective traveling salesman problem
AU - Canca, David
AU - Barrena, Eva
AU - Laporte, Gilbert
PY - 2024/6/30
Y1 - 2024/6/30
N2 - 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.
AB - 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.
KW - Selective traveling salesman problem
KW - Service time-dependent profit
KW - Single- and multi-visit
KW - Time-dependent service time
UR - http://www.scopus.com/inward/record.url?scp=85188952204&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2024.106632
DO - 10.1016/j.cor.2024.106632
M3 - Article
SN - 0305-0548
VL - 166
JO - Computers and Operations Research
JF - Computers and Operations Research
M1 - 106632
ER -