The dynamic programming method in the generalized traveling salesman problem

被引：23

作者：

Chentsov, AG

Korotayeva, LN

机构：

[1] Inst. of Mathematics and Mechanics, Urals Scientific Center, 620066 Ekaterinburg, S. Kovalevskaja str.

来源：

MATHEMATICAL AND COMPUTER MODELLING | 1997年 / 25卷 / 01期

关键词：

dynamic programming; traveling salesman problem; bottle-neck problem; route optimization; diversion of sets system;

D O I：

10.1016/S0895-7177(96)00187-2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A procedure of the dynamic programming (DP)for the discrete-continuous problem of a route optimization is considered. It is possible to consider this procedure as a dynamic method of optimization of the towns choice in the well-known traveling salesman problem. In the considered version of DP, elements of a dynamic optimization are used. Two variants of the function of the aggregations of losses are investigated: (1) the additive functions; (2) the function characterizing the aggregation of lasses in the bottle-neck problem.

引用

页码：93 / 105

页数：13

共 8 条

[1] DYNAMIC PROGRAMMING TREATMENT OF TRAVELLING SALESMAN PROBLEM [J].

BELLMAN, R .

JOURNAL OF THE ACM, 1962, 9 (01) :61-&

[2]

Bellman R., 1965, Dynamic programming and modern control theory, VVolume 81

[3]

BUSLAYEVA LT, 1991, MAT MODELIROVANIE, V3, P103

[4]

CHENTSOV AG, 1993, COMPUT MATHS MATH PH, V33, P443

[5]

CHENTSOV AG, 1989, ZH VYCHISL MAT MAT F, V29, P1107

[6]

CHENTSOV AG, 1995, COMPUT MATHS MATH PH, V35, P853

[7] A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS [J].

HELD, M ;

KARP, RM .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (01) :196-210

[8]

MINOUX M, 1989, PROGRAMMING MATH THE

← 1 →