TSP Race: Minimizing completion time in time-sensitive applications

Date

2015-07-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

273
views

0
downloads

In this paper, we present an approach for parallelizing computation and implementation time for problems where the objective is to complete the solution as soon after receiving the problem instance as possible. We demonstrate the approach on the TSP. We define the TSP race problem, present a computation-implementation parallelized (CIP) approach for solving it, and demonstrate CIP's effectiveness on TSP Race instances. We also demonstrate a method for determining a priori when CIP will be effective. Although in this paper we focus on TSP, our general CIP approach can be effective on other problems and applications with similar time sensitivity.

Subject Keywords

Computation-implementation parallelization, TSP race, TSP, Heuristic

URI

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

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

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

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Multi-objective integer programming: A general approach for generating all non-dominated solutions Oezlen, Melih; Azizoğlu, Meral (Elsevier BV, 2009-11-16) In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical epsilon-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical epsilon-constraint method on the bi-objective integer programming problem for the sake of comple...
Feedback motion planning of unmanned underwater vehicles via random sequential composition Ege, Emr; Orguner, Umut; Department of Electrical and Electronics Engineering (2019) In this thesis, we propose a new motion planning method to robustly and computationally efficiently solve (probabilistic) coverage, path planning, and navigation problems for unmanned underwater vehicles (UUVs). Our approach is based on synthesizing two existing methodologies: sequential decomposition of dynamic behaviors and rapidly exploring random trees. The main motivation for this integrated solution is a robust feed-back based and computationally feasible motion planning and navigation algorithm that ...
Continuous optimization approaches for clustering via minimum sum of squares Akteke-Ozturk, Basak; Weber, Gerhard Wilhelm; Kropat, Erik (2008-05-23) In this paper, we survey the usage of semidefinite programming (SDP), and nonsmooth optimization approaches for solving the minimum sum of squares problem which is of fundamental importance in clustering. We point out that the main clustering idea of support vector clustering (SVC) method could be interpreted as a minimum sum of squares problem and explain the derivation of semidefinite programming and a nonsmooth optimization formulation for the minimum sum of squares problem. We compare the numerical resu...
Residual based Adaptive Unscented Kalman filter for satellite attitude estimation Söken, Halil Ersin (2012-12-01) Determining the process noise covariance matrix in Kalman filtering applications is a difficult task especially for estimation problems of the high-dimensional states where states like biases or system parameters are included. This study introduces a simplistic residual based adaptation method for the Unscented Kalman Filter (UKF), which is used for small satellite attitude estimation. For a satellite with gyros and magnetometers onboard, the proposed adaptive UKF algorithm estimates the attitude as well as...
Signaling Games for Log-Concave Distributions: Number of Bins and Properties of Equilibria Kazikli, Ertan; Sarıtaş, Serkan; GEZİCİ, Sinan; Linder, Tamas; Yuksel, Serdar (2022-03-01) We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources ...

Citation Formats

B. Çavdar and J. Sokol, “TSP Race: Minimizing completion time in time-sensitive applications,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 47–54, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57128.