文献类型：期刊文献

英文题名：The probabilistic uncapacitated open vehicle routing location problem

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

机构：[1]Univ Toronto Scarborough, Dept Management, 1265 Mil Trail, Toronto, ON M1C 1A4, Canada;[2]Univ Toronto, Rotman Sch Management, 105 St George St, Toronto, ON M5S 3E6, Canada;[3]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2023

卷号：82

期号：1

起止页码：68

外文期刊名：NETWORKS

收录：;EI(收录号：20231513879121);WOS:【SCI-EXPANDED(收录号:WOS:000963345800001)】；

基金：ACKNOWLEDGEMENTS The research of Igor Averbakh was supported by the Discovery grant RGPIN-2018-05066 from the Natural Sciences and Engineering Research Council of Canada (NSERC). The research of Wei Yu was supported by grant 11301184 from the National Natural Science Foundation of China and by the China Scholarship Council.

语种：英文

外文关键词：approximation algorithm; location; open vehicle routing; probabilistic location-routing; traveling salesman location problem

摘要：Suppose that m$$ m $$ mobile service units are located at a base station (depot) in a transportation network with n$$ n $$ nodes. On any day, the nodes of the network may generate calls for service independently with known probabilities. The calls are centrally allocated to the service units who then visit the allocated customers on shortest open tours, that is, for each service unit, the way back to the depot from the last served customer is not counted towards the length of the tour. It is required to find an optimal location for the depot to minimize the expected travel distance. We obtain bounds on the approximation ratios for two simple and fast heuristics for the problem on a general network. For the problem on a tree, we present an O(nm+1)$$ O\left({n}<^>{m+1}\right) $$ exact algorithm.