Minisum location of a travelling salesman on simple networks (Q1107451)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minisum location of a travelling salesman on simple networks |
scientific article |
Statements
Minisum location of a travelling salesman on simple networks (English)
0 references
1988
0 references
The authors study the problem to find the optimal home location of a travelling salesman on simple networks. The number of customers and their location can change from day to day. A typical objective function is to minimize the expected distance trevelled. The authors regard (1) unicycle networks: connected networks where the degree of each node is two; (2) 1-tree networks: tree on the nodes 2,3,...,n together with two arcs incident with node 1; (3) simple networks (cactus networks): each link belongs to at most one cycle. The paper includes an O(n) algorithm for the problem on a unicycle network. From this algorithm an algorithm for a 1-tree network is developed. For a simple network that may include several cycles an algorithm for tree networks and an algorithm for unicycle networks are used.
0 references
minisum location
0 references
optimal home location
0 references
expected distance trevelled
0 references
unicycle networks
0 references
1-tree networks
0 references
cactus networks
0 references