摘要
一、引 言 网络上的旅行售货员位置问题,广泛存在于服务性行业中.由于该问题是异常困难的(要求同时求解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代表所有非空表格构成的集合。
An O(n^3) algorithm for the travelling salesman location problem on trees, which is dif-ferent from the one developed by Berman and Simchi-Levi, is presented. An optimal solutionand the optimum value can be found by the algorithm simultaneously. In addition, the 1st, 2nd.3rd,…n-th optimal solutions can be determined when the salesman is located at vertices ofthe tree.
出处
《数值计算与计算机应用》
CSCD
北大核心
1993年第1期11-21,共11页
Journal on Numerical Methods and Computer Applications
