Article
Operations Research & Management Science
Enrico Bartolini, Dominik Goeke, Michael Schneider, Mengdie Ye
Summary: This study focuses on the Traveling Salesman Problem with Time Windows (TSPTW) under travel time uncertainty, proposing an exact algorithm based on column generation and dynamic programming to address robust TSPTW under both knapsack- and cardinality-constrained travel time uncertainty. The algorithm successfully solves instances with up to 80 customers, and investigates the trade-off between service quality and cost resulting from the two uncertainty sets.
TRANSPORTATION SCIENCE
(2021)
Article
Computer Science, Artificial Intelligence
Yongliang Lu, Jin-Kao Hao, Qinghua Wu
Summary: In this work, we investigate a transformation approach to solve the Clustered Traveling Salesman Problem (CTSP) by converting it to the well-studied Traveling Salesman Problem (TSP). We explore the performance of state-of-the-art TSP solvers on clustered instances converted from CTSP and compare it with methods specifically designed for CTSP. Intensive computational experiments on benchmark instances are presented to draw conclusions.
PEERJ COMPUTER SCIENCE
(2022)
Article
Computer Science, Software Engineering
Robert Carr, R. Ravi, Neil Simonetti
Summary: This article introduces two variants of the Traveling Salesman Problem (TSP): Symmetric TSP and Graphical TSP. The authors propose a new integer programming formulation for Graphical TSP and present promising preliminary computational results.
MATHEMATICAL PROGRAMMING
(2023)
Article
Computer Science, Interdisciplinary Applications
Liyang Xiao, Lu Zhen, Gilbert Laporte, Roberto Baldacci, Chenghao Wang
Summary: Rehabilitation is a crucial part of modern healthcare, but the length and complexity of treatment routes for patients pose challenges for hospital managers. This study focuses on reducing the timespan of rehabilitation patients' treatment routes through addressing the scheduling and routing problem. By formulating it as an integer linear program and utilizing a greedy heuristic and column generation method, we propose an efficient solution approach that generates high-quality solutions.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Computer Science, Interdisciplinary Applications
Pengfei He, Jin-Kao Hao
Summary: The paper presents a hybrid algorithm for solving the multiple traveling salesman problem, combining different optimization strategies to achieve good results.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Mathematics
Vincent F. Yu, Shih-Wei Lin, Panca Jodiawan, Yu-Chi Lai
Summary: This study investigates the Flying Sidekick Traveling Salesman Problem (FSTSP) and proposes a revised mixed-integer linear programming (MILP) model and an effective heuristic based on simulated annealing (SA) to solve the problem. The proposed SA heuristic outperforms existing algorithms and achieves satisfactory results in various benchmark instances.
Article
Mathematics, Applied
E. Duman
Summary: The Turkish Cashier Problem (TCP) is a special case of the traveling salesman problem, focusing on finding the optimal route to minimize transportation cost for cashiers. To address this problem, a heuristic algorithm was developed, along with a tight lower bound, and it was demonstrated that the heuristic algorithm performs well for practical instances of the problem.
APPLIED AND COMPUTATIONAL MATHEMATICS
(2022)
Article
Engineering, Multidisciplinary
Xiaoguang Bao, Guojun Wang, Lei Xu, Zhaocai Wang
Summary: The MMCTSP is a generalized variant of the classical TSP problem that aims to minimize the weight of the maximum weight tour. A two-stage solution method based on a genetic algorithm is proposed to solve this problem, where the first stage determines the visiting order within each cluster and the second stage determines the assignment of clusters to salesmen. Experimental results demonstrate that the algorithm can achieve better solution results for various scale instances and exhibit good solution performance.
Article
Management
Guido Pantuza, Mauricio C. de Souza
Summary: This study focuses on the prize collecting traveling salesman problem, proposing new formulations and comparing them with adaptations of strong formulations. By using a Lagrangian relaxation approach with heuristic schemes, the study successfully obtains optimal or near-optimal solutions.
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
(2022)
Correction
Management
Raquel Bernardino, Ana Paias
Summary: This corrigendum corrects the propositions and establishes new relations between the proposed models in the original article.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Artificial Intelligence
Kasi Viswanath Dasari, Alok Singh
Summary: In this paper, two multi-start heuristic approaches are proposed to solve the clustered traveling salesman problem with d-relaxed priority rule (CTSP-d). The first approach is a hyper-heuristic approach that makes use of two hyper-heuristic approaches and five elementary problem-specific heuristics. The second approach is a multi-start iterated local search approach with variable neighborhood descent. Experimental results show that the proposed approaches generate high-quality solutions in low computational times compared to the state-of-the-art approaches.
EXPERT SYSTEMS WITH APPLICATIONS
(2023)
Article
Computer Science, Artificial Intelligence
Jindriska Deckerova, Jan Faigl, Vit Kratky
Summary: This paper proposes a solution to the non-Euclidean variant of the Traveling Salesman Problem with Neighborhoods on a Sphere (TSPNS). By exploiting a non-zero tolerance on the light direction and defining the sites as regions on a sphere, the solution cost is significantly reduced. A practical heuristic solution based on the unsupervised learning of the Growing Self-Organizing Array (GSOA) quickly finds an initial solution with competitive quality.
EXPERT SYSTEMS WITH APPLICATIONS
(2022)
Article
Computer Science, Artificial Intelligence
Mesut Gunduz, Murat Aslan
Summary: Jaya algorithm is a newly proposed stochastic population-based metaheuristic optimization algorithm that improves intensification and diversification of population by utilizing best and worst solutions. With discrete modifications, the algorithm, called DJAYA, has shown competitive performance in solving various discrete optimization problems like the symmetric traveling salesman problem.
APPLIED SOFT COMPUTING
(2021)
Article
Computer Science, Information Systems
Xiaofeng Gao, Jiahao Fan, Fan Wu, Guihai Chen
Summary: This paper investigates the cooperative sweep coverage problem with multiple mobile sensors and the multi-sink sweep coverage problem. Two constant-factor approximations, CoCycle and SinkCycle, are proposed to minimize the maximum sweep period for these two problems, with approximation ratios of 4 and 6, respectively. Additionally, optimal algorithms for the CSC problem and useful insights regarding the MSSC problem are provided. Numerical experiments are conducted to validate the effectiveness and efficiency of the designs.
IEEE TRANSACTIONS ON MOBILE COMPUTING
(2022)
Article
Computer Science, Interdisciplinary Applications
Yuchen Luo, Bruce Golden, Stefan Poikonen, Rui Zhang
Summary: In this article, the author introduces a problem called TSPC, which aims to find a path that is both short and close to the center. To address this problem, the author proposes a new metric and the concept of triangular paths.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Economics
Nikola Besinovic, Rob M. P. Goverde, Egidio Quaglietta, Roberto Roberti
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
(2016)
Article
Transportation Science & Technology
Rob M. P. Goverde, Nikola Besinovic, Anne Binder, Valentina Cacchiani, Egidio Quaglietta, Roberto Roberti, Paolo Toth
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
(2016)
Article
Economics
R. Roberti, M. Wen
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW
(2016)
Article
Construction & Building Technology
Rui Li, Roberto Roberti
JOURNAL OF CONSTRUCTION ENGINEERING AND MANAGEMENT
(2017)
Article
Construction & Building Technology
Rui Li, Roberto Roberti
JOURNAL OF CONSTRUCTION ENGINEERING AND MANAGEMENT
(2017)
Article
Economics
Joao Paiva Fonseca, Evelien van der Hurk, Roberto Roberti, Allan Larsen
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
(2018)
Article
Operations Research & Management Science
Aristide Mingozzi, Roerto Roerti
TRANSPORTATION SCIENCE
(2018)
Article
Operations Research & Management Science
R. Roberti, D. Pacino
TRANSPORTATION SCIENCE
(2018)
Article
Operations Research & Management Science
Dominik Goeke, Roberto Roberti, Michael Schneider
TRANSPORTATION SCIENCE
(2019)
Article
Management
Estele Glize, Roberto Roberti, Nicolas Jozefowiez, Sandra Ulrich Ngueveu
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2020)
Article
Management
Rosario Paradiso, Roberto Roberti, Demetrio Lagana, Wout Dullaert
OPERATIONS RESEARCH
(2020)
Article
Operations Research & Management Science
Christos Orlis, Nicola Bianchessi, Roberto Roberti, Wout Dullaert
TRANSPORTATION SCIENCE
(2020)
Article
Management
Andrea Chiussi, Christos Orlis, Roberto Roberti, Wout Dullaert
Summary: This study addresses the ATM cash replenishment problem in the Netherlands, involving population coverage requirements, and proposes a vehicle tour problem with minimum coverage requirements. Testing on real-life and synthetic instances reveals the impact of different PCRs on ATM replenishment costs and significant cost differences among different major cities.
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
(2022)
Article
Operations Research & Management Science
Roberto Roberti, Mario Ruthmair
Summary: Efficient handling of last-mile deliveries is becoming increasingly crucial in modern society. By combining trucks and drones, synchronization of flows through a compact mixed-integer linear program and dynamic programming recursions can significantly improve delivery efficiency. This approach outperforms state-of-the-art methods and shows promising results for optimizing last-mile deliveries with the use of drones.
TRANSPORTATION SCIENCE
(2021)
Article
Transportation Science & Technology
Sara Cavani, Manuel Iori, Roberto Roberti
Summary: This paper focuses on delivery systems with a single traditional vehicle and multiple drones working together. A compact Mixed-Integer Linear Programming (MILP) model is proposed for the Traveling Salesman Problem with Multiple Drones (TSP-MD), along with families of valid inequalities. An exact decomposition approach based on the compact MILP and a branch-and-cut algorithm can solve instances with up to 24 customers to proven optimality, surpassing existing methods.
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
(2021)