Article
Management
Alaleh Maskooki, Markku Kallio
Summary: This article discusses a variant of the moving target traveling salesman problem where the number and locations of targets vary with time and random trajectories. The aim is to maximize the number of visits to different targets and minimize the total travel distance. A two-stage stochastic programming model is developed using a linear value function for finding supported Pareto-efficient solutions. An iterative randomized dynamic programming (RDP) algorithm is proposed, which converges to a global optimum with probability one. The RDP algorithm involves backward and forward recursion stages, as well as options for improving any given schedule.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Management
Andrea Di Placido, Claudia Archetti, Carmine Cerrone, Bruce Golden
Summary: This paper studies the generalized close enough traveling salesman problem (GCETSP), which involves associating each customer with a set of disks of different radii. The goal is to determine the route that maximizes the difference between the total collected prize and the route length. The proposed genetic algorithm (GA) shows promising results in finding high-quality solutions with a short computing time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Computer Science, Information Systems
Joanna Ochelska-Mierzejewska, Aneta Poniszewska-Maranda, Witold Maranda
Summary: The TSP involves finding the shortest path connecting all cities, while the VRP focuses on defining routes for vehicles in logistics transportation. Optimizing the VRP can reduce total costs, with economic benefits in more open markets.
Article
Computer Science, Artificial Intelligence
Rahul Jain, Kushal Pal Singh, Arvind Meena, Kun Bihari Rana, Makkhan Lal Meena, Govind Sharan Dangayach, Xiao-Zhi Gao
Summary: In the era of technological development, finding precise solutions to complex problems becomes more important. This study proposes a new method to improve the convergence rate by incorporating a unique feature called 'sub-tour division', which shows higher accuracy and robustness in solving the traveling salesman problem.
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
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
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
Transportation Science & Technology
Zhihao Luo, Mark Poon, Zhenzhen Zhang, Zhong Liu, Andrew Lim
Summary: This study focuses on the multi-visit traveling salesman problem with multi-drones, proposing a multi-start tabu search algorithm and validating its accuracy and efficiency on small-scale instances. The results demonstrate a significant cost reduction under certain conditions.
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
(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
Mathematics, Applied
Jacek Graczyk, Nicolae Mihalache
Summary: We provide two optimal lower bounds for solving the analytical traveling salesman problem using Jones' beta-numbers. We establish a linear lower bound for the length of every connecting curve in the general case, with the four corners Cantor set demonstrating its achievability. For connected compact sets, we prove an exponential lower bound for their length, which is shown to be optimal based on the work of Bishop and Jones. Finally, we bridge the connected and disconnected cases by considering the multiplicity of orthogonal projections, and briefly discuss applications to other areas of mathematics.
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS
(2022)
Article
Operations Research & Management Science
Moise Blanchard, Alexandre Jacquillat, Patrick Jaillet
Summary: This paper provides constant-factor probabilistic approximations for both the k-traveling salesman problem (k-TSP) and traveling repairman problem (TRP). The optimal length of the k-TSP path grows at a rate of Θ(k/nk/(2(k-1))), and the optimal TRP latency grows at a rate of Θ(n√). The proof for both problems provides constant-factor approximation schemes and discusses practical implications in transportation and logistics systems. The paper also proposes dedicated notions of fairness for k-TSP and TRP, and algorithms to balance efficiency and fairness.
MATHEMATICS OF OPERATIONS RESEARCH
(2023)
Article
Engineering, Civil
Xianghu Meng, Jun Li, MengChu Zhou, Xianzhong Dai
Summary: This study introduces a colored traveling salesman problem with edge weights among cities changing over time, applicable to dynamic routing in logistic distribution systems. Through a specific algorithm, solution quality and adaptability to environmental changes are improved.
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS
(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
Operations Research & Management Science
Samuel C. Gutekunst, David P. Williamson
Summary: This paper examines semidefinite programming relaxations of the traveling salesman problem, pointing out the limitations of an SDP method based on permutation matrices and symmetry reduction. The study also highlights the strong performance of subtour linear programming on example instances, serving as a natural litmus test for future SDP relaxations of the TSP.
MATHEMATICS OF OPERATIONS RESEARCH
(2022)
Article
Computer Science, Artificial Intelligence
Panli Zhang, Jiquan Wang, Zhanwei Tian, Shengzhi Sun, Jianting Li, Jingnan Yang
Summary: In this paper, a genetic algorithm with jumping gene and heuristic operators (GA-JGHO) is proposed to solve the traveling salesman problem. By improving the selection method of the combined fitness function, introducing a bidirectional heuristic crossover operator, designing a combination mutation operator, introducing a jumping gene operator, and adding a unique operator, as well as integrating a local search operator, GA-JGHO performs better in quality stability, accuracy, and convergence speed.
APPLIED SOFT COMPUTING
(2022)
Review
Management
Vinicius N. Motta, Miguel F. Anjos, Michel Gendreau
Summary: This survey presents a review of optimization approaches for the integration of demand response in power systems planning and highlights important future research directions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Philipp Schulze, Armin Scholl, Rico Walter
Summary: This paper proposes an improved branch-and-bound algorithm, R-SALSA, for solving the simple assembly line balancing problem, which performs well in balancing workloads and providing initial solutions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Roshan Mahes, Michel Mandjes, Marko Boon, Peter Taylor
Summary: This paper discusses appointment scheduling and presents a phase-type-based approach to handle variations in service times. Numerical experiments with dynamic scheduling demonstrate the benefits of rescheduling.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Oleg S. Pianykh, Sebastian Perez, Chengzhao Richard Zhang
Summary: Efficient scheduling is crucial for optimizing resource allocation and system performance. This study focuses on critical utilization and efficient scheduling in discrete scheduling systems, and compares the results with classical queueing theory.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Review
Management
Hamed Jahani, Babak Abbasi, Jiuh-Biing Sheu, Walid Klibi
Summary: Supply chain network design is a large and growing area of research. This study comprehensively surveys and analyzes articles published from 2008 to 2021 to detect and report financial perspectives in SCND models. The study also identifies research gaps and offers future research directions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Patrick Healy, Nicolas Jozefowiez, Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka
Summary: The Connected Max-k-Cut Problem is an extension of the well-known Max-Cut Problem, where the objective is to partition a graph into k connected subgraphs by maximizing the cost of inter-partition edges. The researchers propose a new integer linear program and a branch-and-cut algorithm for this problem, and also use graph isomorphism to structure the instances and facilitate their resolution. Extensive computational experiments show that, if k > 2, their approach outperforms existing algorithms in terms of quality.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Victor J. Espana, Juan Aparicio, Xavier Barber, Miriam Esteve
Summary: This paper introduces a new methodology based on the machine learning technique MARS for estimating production functions that satisfy classical production theory axioms. The new approach overcomes the overfitting problem of DEA through generalized cross-validation and demonstrates better performance in reducing mean squared error and bias compared to DEA and C2NLS methods.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Stefano Nasini, Rabia Nessah
Summary: In this paper, the authors investigate the impact of time flexibility in job scheduling, showing that it can significantly affect operators' ability to solve the problem efficiently. They propose a new methodology based on convex quadratic programming approaches that allows for optimal solutions in large-scale instances.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Zhiqiang Liao, Sheng Dai, Timo Kuosmanen
Summary: Nonparametric regression subject to convexity or concavity constraints is gaining popularity in various fields. The conventional convex regression method often suffers from overfitting and outliers. This paper proposes the convex support vector regression method to address these issues and demonstrates its advantages in prediction accuracy and robustness through numerical experiments.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Kuo-Hao Chang, Ying-Zheng Wu, Wen-Ray Su, Lee-Yaw Lin
Summary: The damage and destruction caused by earthquakes necessitates the evacuation of affected populations. Simulation models, such as the Stochastic Pedestrian Cell Transmission Model (SPCTM), can be utilized to enhance disaster and evacuation management. The analysis of SPCTM provides insights for government officials to formulate effective evacuation strategies.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Qinghua Wu, Mu He, Jin-Kao Hao, Yongliang Lu
Summary: This paper studies a variant of the orienteering problem known as the clustered orienteering problem. In this problem, customers are grouped into clusters and a profit is associated with each cluster, collected only when all customers in the cluster are served. The proposed evolutionary algorithm, incorporating a backbone-based crossover operator and a destroy-and-repair mutation operator, outperforms existing algorithms on benchmark instances and sets new records on some instances. It also demonstrates scalability on large instances and has shown superiority over three state-of-the-art COP algorithms. The algorithm is also successfully applied to a dynamic version of the COP considering stochastic travel time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Bjorn Bokelmann, Stefan Lessmann
Summary: Estimating treatment effects is an important task for data analysts, and uplift models provide support for efficient allocation of treatments. However, evaluating uplift models is challenging due to variance issues. This paper theoretically analyzes the variance of uplift evaluation metrics, proposes variance reduction methods based on statistical adjustment, and demonstrates their benefits on simulated and real-world data.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Congzheng Liu, Wenqi Zhu
Summary: This paper proposes a feature-based non-parametric approach to minimizing the conditional value-at-risk in the newsvendor problem. The method is able to handle both linear and nonlinear profits without prior knowledge of the demand distribution. Results from numerical and real-life experiments demonstrate the robustness and effectiveness of the approach.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Laszlo Csato
Summary: This paper compares the performance of the eigenvalue method and the row geometric mean as two weighting procedures. Through numerical experiments, it is found that the priorities derived from the two eigenvectors in the eigenvalue method do not always agree, while the row geometric mean serves as a compromise between them.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Guowei Dou, Tsan-Ming Choi
Summary: This study investigates the impact of channel relationships between manufacturers on government policies and explores the effectiveness of positive incentives versus taxes in increasing social welfare. The findings suggest that competition may be more effective in improving sustainability and social welfare. Additionally, government incentives for green technology may not necessarily enhance sustainability.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)