| 树网络上的旅行售货员位置问题的一多项式算法 |
| |
| 引用本文： | 吴龙君,杨承恩.树网络上的旅行售货员位置问题的一多项式算法[J].数值计算与计算机应用,1993(1). |
| |
| 作者姓名： | 吴龙君 杨承恩 |
| |
| 作者单位： | 长沙铁道学院
(吴龙君)，长沙铁道学院(杨承恩) |
| |
| 摘 要： | 一、引 言 网络上的旅行售货员位置问题,广泛存在于服务性行业中.由于该问题是异常困难的(要求同时求解TSP与相应的位置问题),至今研究它的人还很少.1986年Berman等人提出了一O(n)算法(n为网络的顶点数),可以求出树网络上旅行售货员的最优位置.但由于问题的目标函数是2~n—1项的和,故不能在多项式时间内直接计算出最优值.本文提出另一O(n~3)的多项式算法,可以求出树网络上的旅行售货员的最优位置及对应的目标函数的值.若限定售货员的位置在网络的顶点上,那么新算法还可求出问题的任意阶最优解.新算法与Berman等人的算法结合起来,计算的复杂性为O(n~2). 旅行售货员位置问题可叙述如下:令T(V,L)是一无向网络(本文认为它是一树网络,|V|=n),每一个顶点代表一顾客,L是边集,h_i表示顾客i要求服务的概率.在每天开始,要求服务的顾客均记入表格R,E代表所有非空表格构成的集合,显然
|
| 本文献已被 CNKI 等数据库收录！ |
|
