期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 308, 期 3, 页码 960-989出版社
ELSEVIER
DOI: 10.1016/j.ejor.2022.11.050
关键词
Combinatorial optimisation; Travelling salesman problem; Positional consistency; Healthcare services
This paper explores the Consistent Traveling Salesman Problem with positional consistency constraints (CTSP), which aims to find a set of routes with minimal cost while ensuring that all visited clients maintain positional consistency across routes. Various compact formulations and a new aggregated model derived from Time-dependent TSP (TDTSP) models are presented. Computational experiments reveal that the new aggregated model outperforms existing models in cases with consistent nodes appearing in all or most routes, while the original time-dependent model is more efficient when consistent nodes appear in fewer routes or less frequently.
In this paper we study the Consistent Traveling Salesman Problem with positional consistency constraints (CTSP), where we seek to generate a set of routes with minimum cost, in which all the clients that are visited in several routes require total positional consistency , that is, they need to appear in the same rela-tive position in all the routes they are visited in. This problem was motivated by a scheduling application in healthcare. We present several compact formulations for the CTSP, which have been adapted from models known from the Time-dependent TSP (TDTSP) literature, and propose a new model, which is an aggregated version of a model adapted from the TDTSP. A preliminary computational experiment allowed us to identify the three most competitive models. These models were then evaluated in more detail, first through a set of instances with 2, 3 or 5 routes and characteristics that derive from an healthcare application; and second through a set of tests with 5 routes and seven different and more general con-sistency configurations. The computational results show that for consistency configurations in which the consistent nodes appear in all, or most, of the routes, the new aggregated model can outperform the best model adapted from the literature. For the cases where the consistent nodes appear in fewer routes or less frequently, the original time-dependent model is more efficient.(c) 2022 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据