A distribution-free TSP tour length estimation model for random graphs

Date

2015-06-01

Author

Çavdar, Bahar
Sokol, Joel

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

82
views

0
downloads

Traveling Salesman Problem (TSP) tour length estimations can be used when it is not necessary to know an exact tour, e.g., when using certain heuristics to solve location-routing problems. The best estimation models in the TSP literature focus on random instances where the node dispersion is known; those that do not require knowledge of node dispersion are either less accurate or slower. In this paper, we develop a new regression-based tour length estimation model that is distribution-free, accurate, and fast, with a small standard deviation of the estimation errors. When the distribution of the node coordinates is known, it provides a close estimate of the well-known asymptotic tour length estimation formula of Beardwood et al. (1959); more importantly, when the distribution is unknown or non-integrable so Beardwood et al.'s estimation cannot be used, our model still provides good, fast tour length estimates.

Subject Keywords

TSP, Tour length estimation

URI

https://hdl.handle.net/11511/51665

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/j.ejor.2014.12.020

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A Concept Filtering Approach for Diverse Density to Discover Subgoals in Reinforcement Learning DEMİR, ALPER; Cilden, Erkin; Polat, Faruk (2017-11-08) In the reinforcement learning context, subgoal discovery methods aim to find bottlenecks in problem state space so that the problem can naturally be decomposed into smaller subproblems. In this paper, we propose a concept filtering method that extends an existing subgoal discovery method, namely diverse density, to be used for both fully and partially observable RL problems. The proposed method is successful in discovering useful subgoals with the help of multiple instance learning. Compared to the original...
A Hierarchical Partitioning Strategy for an Efficient Parallelization of the Multilevel Fast Multipole Algorithm Ergül, Özgür Salih (Institute of Electrical and Electronics Engineers (IEEE), 2009-06-01) We present a novel hierarchical partitioning strategy for the efficient parallelization of the multilevel fast multipole algorithm (MLFMA) on distributed-memory architectures to solve large-scale problems in electromagnetics. Unlike previous parallelization techniques, the tree structure of MLFMA is distributed among processors by partitioning both clusters and samples of fields at each level. Due to the improved load-balancing, the hierarchical strategy offers a higher parallelization efficiency than previ...
An Adaptive Unscented Kalman Filter For Tightly Coupled INS/GPS Integration Akca, Tamer; Demirekler, Mübeccel (2012-04-26) In order to overcome the various disadvantages of standalone INS and GPS, these systems are integrated using nonlinear estimation techniques. The standard and most widely used estimation algorithm for the INS/GPS integration is Extended Kalman Filter (EKF) which makes a first order approximation for the nonlinearity involved. Unscented Kalman Filter (UKF) approaches this problem by carefully selecting deterministic sigma points from Gaussian distributions and propagating these points through the nonlinear f...
A probabilistic multiple criteria sorting approach based on distance functions ÇELİK, BİLGE; Karasakal, Esra; İyigün, Cem (2015-05-01) In this paper, a new probabilistic distance based sorting (PDIS) method is developed for multiple criteria sorting problems. The distance to the ideal point is used as a criteria disaggregation function to determine the values of alternatives. These values are used to sort alternatives into the predefined classes. The method also calculates probabilities that each alternative belong to the predefined classes in order to handle alternative optimal solutions. It is applied to five data sets and its performanc...
A Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery Using Depot Removal and Insertion Moves Cinar, Volkan; ÖNCAN, TEMEL; Süral, Haldun (2010-04-09) In this work, we consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), which is an extension of the well-known NP-hard Traveling Salesman Problem. We propose a Genetic Algorithm (GA) based on a specially tailored tour improvement procedure for the TSPPD. Computational experiments are reported on the test instances taken from the literature. The experimental results suggest that the proposed GA yields a promising performance in terms of both accuracy and efficiency compared to existing al...

Citation Formats

B. Çavdar and J. Sokol, “A distribution-free TSP tour length estimation model for random graphs,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 588–598, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/51665.