文献类型：期刊文献

英文题名：Multi-depot traveling salesmen location problems on networks with special structure

作者：Averbakh, Igor[1];Yu, Wei[2]

机构：[1]Univ Toronto Scarborough, Dept Management, 1265 Mil Trail, Scarborough, ON M1C 1A4, Canada;[2]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2020

卷号：286

期号：1-2

起止页码：635

外文期刊名：ANNALS OF OPERATIONS RESEARCH

收录：;WOS:【SSCI(收录号:WOS:000511564300027)，SCI-EXPANDED(收录号:WOS:000511564300027)】；

语种：英文

外文关键词：Traveling salesmen location problem; Probabilistic location-routing; Network algorithms

摘要：Suppose that on any day, calls for service are generated by nodes of a transportation network independently with known probabilities. The calls are allocated to p service units that visit the allocated customers on shortest closed tours. That is, each service unit performs an optimal traveling salesman tour on its set of allocated calls (customers). We need to find optimal locations for the service units to minimize the expected travel distance. For this problem on a path, we present an O(n4)\documentclass[12pt] algorithm, where n is the number of nodes of the network. We also present an O(n5)\documentclass[12pt] algorithm for the problem on a tree with p=2\documentclass[12pt]