KJCKorea
Journal Central

@article{ART002524908},
author={Chung Yerim and Park Myoungju},
title={Partial Inverse Traveling Salesman Problems on the Line},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2019},
volume={24},
number={11},
pages={119-126},
doi={10.9708/jksci.2019.24.11.119}

TY - JOUR
AU - Chung Yerim
AU - Park Myoungju
TI - Partial Inverse Traveling Salesman Problems on the Line
JO - Journal of The Korea Society of Computer and Information
PY - 2019
VL - 24
IS - 11
PB - The Korean Society Of Computer And Information
SP - 119
EP - 126
SN - 1598-849X
AB - 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.
KW - Inverse Optimization;Partial Inverse Problem;Traveling Salesman Problem;Poly-time Algorithm;TSP on the Line
DO - 10.9708/jksci.2019.24.11.119
ER -

Chung Yerim and Park Myoungju. (2019). Partial Inverse Traveling Salesman Problems on the Line. Journal of The Korea Society of Computer and Information, 24(11), 119-126.

Chung Yerim and Park Myoungju. 2019, "Partial Inverse Traveling Salesman Problems on the Line", Journal of The Korea Society of Computer and Information, vol.24, no.11 pp.119-126. Available from: doi:10.9708/jksci.2019.24.11.119

Chung Yerim, Park Myoungju "Partial Inverse Traveling Salesman Problems on the Line" Journal of The Korea Society of Computer and Information 24.11 pp.119-126 (2019) : 119.

Chung Yerim, Park Myoungju. Partial Inverse Traveling Salesman Problems on the Line. 2019; 24(11), 119-126. Available from: doi:10.9708/jksci.2019.24.11.119

Chung Yerim and Park Myoungju. "Partial Inverse Traveling Salesman Problems on the Line" Journal of The Korea Society of Computer and Information 24, no.11 (2019) : 119-126.doi: 10.9708/jksci.2019.24.11.119

Chung Yerim; Park Myoungju. Partial Inverse Traveling Salesman Problems on the Line. Journal of The Korea Society of Computer and Information, 24(11), 119-126. doi: 10.9708/jksci.2019.24.11.119

Chung Yerim; Park Myoungju. Partial Inverse Traveling Salesman Problems on the Line. Journal of The Korea Society of Computer and Information. 2019; 24(11) 119-126. doi: 10.9708/jksci.2019.24.11.119

Chung Yerim, Park Myoungju. Partial Inverse Traveling Salesman Problems on the Line. 2019; 24(11), 119-126. Available from: doi:10.9708/jksci.2019.24.11.119

Chung Yerim and Park Myoungju. "Partial Inverse Traveling Salesman Problems on the Line" Journal of The Korea Society of Computer and Information 24, no.11 (2019) : 119-126.doi: 10.9708/jksci.2019.24.11.119