Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations
Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations
复制标题
网络上单个服务单元到非服务目的地的最优最小最大路径
作者：
O. Berman;G. Handler
在本文中，我们考虑寻找单个服务单元到“非服务”目的地的最优路径问题。研究了两类目标函数。一个目标函数是移动服务单元与网络中任何需求（节点）之间的最大距离（或加权距离）的最小化。第二个目标函数是移动服务单元与任何节点之间的距离（或加权距离）超过响应时间阈值（lambda）的总时间周期的最小化。对于这两个目标函数，我们给出了分别用0（n3）和0（n3 log n）初等运算计算的算法。
In this paper we consider the problem of finding an optimal path of a single service unit that travels toward a “nonservice” destination. Two types of objective functions are examined. One objective function is the minimization of the maximum distance (or weighted distance) between the moving service unit and any demand (node) of the network. The second objective function is the minimization of the total time period that the distance (or weighted distance) between the moving service unit and any node exceeds a response time threshold (lambda). For these two objective functions, we present algorithms which can be calculated, respectively, in 0( n 3 ) and 0( n 3 log n ) elementary operations.