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

19
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...
EMDD-RL: faster subgoal identification with diverse density in reinforcement learning Sunel, Saim; Polat, Faruk; Department of Computer Engineering (2021-1-15) Diverse Density (DD) algorithm is a well-known multiple instance learning method, also known to be effective to automatically identify sub-goals and improve Reinforcement Learning (RL). Expectation-Maximization Diverse Density (EMDD) improves DD in terms of both speed and accuracy. This study adapts EMDD to automatically identify subgoals for RL which is shown to perform significantly faster (3 to 10 times) than its predecessor, without sacrificing solution quality. The performance of the proposed method na...
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 ...
Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the follo...
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 ...

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.