Routing under constraints: Problem of visit to megalopolises / Chentsov A. G.,Chentsov P. A. // AUTOMATION AND REMOTE CONTROL. - 2016. - V. 77, l. 11. - P. 1957-1974.

ISSN/EISSN:

0005-1179 / 1608-3032

Type:

Article

Abstract:

Consideration was given to the problems of routing transfers under conditions of precedence and dynamic constraints including the dependence of the list of jobs both already completed by the instant of transfer or, on the contrary, not yet completed. The transfer costs also can be dependent on the list of jobs. The megalopolises (nonempty finite sets) are the objects of visits, which corresponds to the possible multiple-choice of transfers. The widely understood dynamic programming in a realization not requiring (under the precedence conditions) construction of the entire array of the Bellman function values is used as the basic method of study. The procedure of constructing a ``complete{''} solution including determination of the optimal solution route and track (trajectory) and the procedure determining the problem value (global extremum) can be used separately to test the heuristic algorithms. An efficient heuristic algorithm was constructed to solve the routing problems of great dimension complicated by the constraints typical of the sheet cutting on the machines with computerized numerical control. For moderate problems, the results obtained were compared with the optimal result provided by the dynamic programming.

Author keywords:

TRAVELING SALESMAN PROBLEM; OPTIMIZATION

DOI:

10.1134/S0005117916110060

Web of Science ID:

ISI:000387924000006

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	NOV
Publisher	MAIK NAUKA/INTERPERIODICA/SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013-1578 USA
Language	English
EISSN	1608-3032
Keywords-Plus	TRAVELING SALESMAN PROBLEM; OPTIMIZATION
Research-Areas	Automation \& Control Systems; Instruments \& Instrumentation
Web-of-Science-Categories	Automation \& Control Systems; Instruments \& Instrumentation
Author-Email	chentsov@imm.uran.ru chentsov.p@uran.ru
Funding-Acknowledgement	Decree of the Government of Russian Federation {[}211, 02.A03.21.0006]; Russian Foundation for Basic Research {[}16-01-00649]
Funding-Text	This work was supported by the Decree no. 211 of the Government of Russian Federation, contract no. 02.A03.21.0006, and the Russian Foundation for Basic Research, project no. 16-01-00649.
Number-of-Cited-References	28
Usage-Count-Last-180-days	1
Usage-Count-Since-2013	4
Journal-ISO	Autom. Remote Control
Doc-Delivery-Number	EC2FB