TSP Race: Minimizing completion time in time-sensitive applications


ÇAVDAR B., Sokol J.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.244, no.1, pp.47-54, 2015 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 244 Issue: 1
  • Publication Date: 2015
  • Doi Number: 10.1016/j.ejor.2014.12.022
  • Journal Name: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.47-54

Abstract

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. (C) 2014 Elsevier B.V. All rights reserved.