Premium
Sales‐delivery man problems on treelike networks
Author(s) -
Averbakh Igor,
Berman Oded
Publication year - 1995
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.3230250204
Subject(s) - computer science , routing (electronic design automation) , service (business) , time complexity , tree (set theory) , situated , computer network , mathematical optimization , theoretical computer science , distributed computing , mathematics , combinatorics , algorithm , artificial intelligence , business , marketing
Suppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location‐routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O( n log n ) or O( n ). Multiserver variants of the problem on a tree are proved to be NP‐complete. Some modifications of the problem are also investigated.