Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On inverse traveling salesman problems

  • Research Paper
  • Published:
4OR Aims and scope Submit manuscript

Abstract

The inverse traveling salesman problem belongs to the class of “inverse combinatorial optimization” problems. In an inverse combinatorial optimization problem, we are given a feasible solution for an instance of a particular combinatorial optimization problem, and the task is to adjust the instance parameters as little as possible so that the given solution becomes optimal in the new instance. In this paper, we consider a variant of the inverse traveling salesman problem, denoted by ITSP W,A , by taking into account a set W of admissible weight systems and a specific algorithm. We are given an edge-weighted complete graph (an instance of TSP), a Hamiltonian tour (a feasible solution of TSP) and a specific algorithm solving TSP. Then, ITSP W,A , is the problem to find a new weight system in W which minimizes the difference from the original weight system so that the given tour can be selected by the algorithm as a solution. We consider the cases \({W \in \{\mathbb{R}^{+m}, \{1, 2\}^m , \Delta\}}\) where Δ denotes the set of edge weight systems satisfying the triangular inequality and m is the number of edges. As for algorithms, we consider a local search algorithm 2-opt, a greedy algorithm closest neighbor and any optimal algorithm. We devise both complexity and approximation results. We also deal with the inverse traveling salesman problem on a line for which we modify the positions of vertices instead of edge weights. We handle the cases \({W \in \{\mathbb{R}^{+n}, \mathbb{N}^n\}}\) where n is the number of vertices.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ahuja R, Orlin J (2000) A faster algorithm for the inverse spanning tree problem. J Algorithms 34(1): 177–193

    Article  Google Scholar 

  • Ahuja R, Orlin J (2001) Inverse optimization. Oper Res 49(5): 771–783

    Article  Google Scholar 

  • Angelov S, Harb B, Kannan S, Wang LS (2006) Weighted isotonic regression under the l1 norm. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 783–791

  • Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccame-La A, Protasi M (1999) Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer, Berlin

    Google Scholar 

  • Burton D, Toint P (1992) On an instance of the inverse shortest paths problem. Math Programm 53: 45–61

    Article  Google Scholar 

  • Burton D, Toint P (1994) On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Math Programm 63: 1–22

    Article  Google Scholar 

  • Carr SC, Lovejoy WS (1997) The inverse newsvendor problem: choosing an optimal demand portfolio for capacitated resources. Technical report, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI

  • Chakravarti N (1989) Isotonic median regression; a linear programming approach. Math Oper Res 14(2): 303–308

    Article  Google Scholar 

  • Chung Y, Culus JF, Demange M (2008) Inverse booking problems. In: Proceedings of the 2d workshop on algorithms and computation, WALCOM 2008, Lecture Notes in Computer Science, vol 4921, pp 180–187

  • Chung Y, Demange M (2008) The 0-1 inverse maximum stable set problem. Discret Appl Math 156(13): 2501–2516

    Article  Google Scholar 

  • Ciura E, Deaconu A (2007) Inverse minimum flow problem. J Appl Math Comput 23(1-2): 193–203

    Article  Google Scholar 

  • Demange M, Ekim T, de Werra D (2009) A tutorial on the use of graph coloring for some problems in robotics. Eur J Oper Res 192(1): 41–55

    Article  Google Scholar 

  • Demange M, Monnot J (2010) An introduction to inverse combinatorial problems. In: Paradigms of combinatorial optimization (problems and new approaches). ISTE-WILEY, London-Hoboken (UK-USA), Vangelis Th., Paschos, pp 547–586

  • Dembo R, Merkoulovitch L, Rosen D (1998) Images from a portfolio. Algorithmics research working paper, Algorithmics, Inc., Canada

  • Dial B (1997) Minimum-revenue congestion pricing, Part 1: a fast algorithm for the single-origin case. Technical report, The Volpe National Transportation Systems Center, Kendall Square, Cambridge, MA

  • Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1): 439–485

    Article  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability—a guide to the theory of NP-completeness. Freeman, San Francisco

    Google Scholar 

  • Heuberger C (2004) Inverse combinatorial optimization: a survey on problems, methods, and results. J Comb Optim 8(3): 329–361

    Article  Google Scholar 

  • Karakostas G (2005) A better approximation ratio for the vertex cover problem. In: Proceedings of the 32nd international colloquium on automata, languages and programming, ICALP, Lecture Notes in Computer Science, vol 3580, pp 1043–1050

  • Khanna S, Motwani R, Sudan M, Vazirani V (1998) On syntactic versus computational views of approximability. SIAM J Comput 28(1): 164–191

    Article  Google Scholar 

  • Nolet G (1987) Seismic tomography. Reidel, Dordrecht

    Google Scholar 

  • Papadimitriou C (1994) Computational complexity. Addison-Wesley, New York

    Google Scholar 

  • Papadimitriou CH, Steiglitz K (1976) Some complexity results for the traveling salesman problem. In: STOC’76, pp 1–9

  • Robertson T, Wright F (1980) Algorithms in order restricted statistical inference and the cauchy mean value property. Ann Stat 8: 645–651

    Article  Google Scholar 

  • Tarantola A (1987) Inverse problem theory: methods for data fitting and model parameter estimation. Elsevier, Amsterdam

    Google Scholar 

  • Xu S, Zhang J (1995) An inverse problem of the weighted shortest path problem. Jpn J Ind Appl Math 12(1): 47–59

    Article  Google Scholar 

  • Ye Y (1991) An O(n 3 L) potential reduction algorithm for linear programming. Math Programm 50: 239–258

    Article  Google Scholar 

  • Zhang J, Liu Z (2002) A general model of some inverse combinatorial optimization problems and its solution method under l-norm. J Comb Optim 6(2): 207–227

    Article  Google Scholar 

  • Zhang J, Yang X, Cai M (1999) The complexity analysis of the inverse center location problem. J Glob Optim 15(2): 213–218

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Business, Yonsei University, Yonsei-ro 50, Seodaemun-gu, Seoul, Republic of Korea

    Yerim Chung

  2. ESSEC Business School, Paris, France

    Marc Demange

Authors
  1. Yerim Chung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc Demange
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yerim Chung.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chung, Y., Demange, M. On inverse traveling salesman problems. 4OR-Q J Oper Res 10, 193–209 (2012). https://doi.org/10.1007/s10288-011-0194-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-011-0194-4

Keywords

MSC classification (2000)

Search

Navigation