Premium
Minisum location of a traveling salesman
Author(s) -
Berman O.,
Levi D. Simchi
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160302
Subject(s) - travelling salesman problem , service (business) , computer science , node (physics) , mathematical optimization , tree (set theory) , sensitivity (control systems) , traveling purchaser problem , combinatorics , mathematics , bottleneck traveling salesman problem , engineering , economy , structural engineering , electronic engineering , economics
In this article we deal with the problem of locating on a network a service unit that must visit all the calls that are registered in a service list. Each node can generate a call with a given probability and the service list contains the first b calls that have arrived b ≤ n ( n is the number of nodes). In our problem the optimal location minimizes the expected length of a traveling salesman tour (TST) traveled. For the problem (which requires 2 n calculations of probabilities), we develop an O(n) Algorithm when b = n . for a tree, and study the sensitivity of this optimal solution when b < n .