본문 바로가기
  • Home

Partial Inverse Traveling Salesman Problems on the Line

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2019, 24(11), pp.119-126
  • DOI : 10.9708/jksci.2019.24.11.119
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : October 10, 2019
  • Accepted : November 5, 2019
  • Published : November 29, 2019

Chung Yerim 1 Park Myoungju 2

1연세대학교
2경희대학교

Accredited

ABSTRACT

The partial inverse optimization problem is an interesting variant of the inverse optimization problem in which the given instance of an optimization problem need to be modified so that a prescribed partial solution can constitute a part of an optimal solution in the modified instance. In this paper, we consider the traveling salesman problem defined on the line (TSP on the line) which has many applications such as item delivery systems, the collection of objects from storage shelves, and so on. It is worth studying the partial inverse TSP on the line, defined as follows. We are given n requests on the line, and a sequence of k requests that need to be served consecutively. Each request has a specific position on the real line and should be served by the server traveling on the line. The task is to modify as little as possible the position vector associated with n requests so that the prescribed sequence can constitute a part of the optimal solution (minimum Hamiltonian cycle) of TSP on the line. In this paper, we show that the partial inverse TSP on the line and its variant can be solved in polynomial time when the sever is equiped with a specific internal algorithm Forward Trip or with a general optimal algorithm.

Citation status

* References for papers published after 2022 are currently being built.