Minisum location of a travelling salesman on simple networks
type: Item
instance of: scholarly article
title: Minisum location of a travelling salesman on simple networks
zbMATH Open document ID: 0652.90096
DOI: 10.1016/0377-2217(88)90430-4
published in: European Journal of Operational Research
publication date: 1988-01-01T00:00:00Z
review text: 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.
reviewed by: G.Merkel
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4064788
zbMATH Keywords: minisum location
zbMATH Keywords: optimal home location
zbMATH Keywords: expected distance trevelled
zbMATH Keywords: unicycle networks
zbMATH Keywords: 1-tree networks
zbMATH Keywords: cactus networks
author: Oded Berman
author: David Simchi-Levi
MaRDI profile type: Publication
full work available at URL: 0377-2217(88)90430-4
OpenAlex ID: W1985890841
cites work: Minisum location of a traveling salesman
cites work: Block-vertex duality and the one-median problem
cites work: Q3316922
description: scientific article; zbMATH DE number 4064788