Forthcoming seminars
Seminar calendar
List of seminars
Archive by years
Register a seminar

Forthcoming seminars

You may need the following programs to see the files

Seminar of Control System Department
December 18, 2014, Ekaterinburg, ul. S Kovalevskoi, 16, room 322

A model of źnonadditive╗ routing problem where the costs depend on the set of pending tasks

A. G. Chentsov, Ya. V. Salii

Number of views:
This page:62

Abstract: We consider a generalization of the bottleneck (minimax) routing problem. The problem is to successively visit a number of megalopolises, complicated by precedence constraints imposed on the order of megalopolises visited and the fact that the cost functions (of movement between megalopolises and of interior tasks) may explicitly depend on the list of tasks that are not completed at the present time. The process of movement is considered to be a sequence of steps, which include the exterior movement to the respective megalopolis and the following completion of (essentially interior) jobs connected with the megalopolis. The quality of the whole process is represented by the maximum cost of steps it consists of; the problem is to minimize the mentioned criterion (which yields a minimax problem, usually referred to as a “bottleneck problem”). Optimal solutions, in the form of a route-track pair (a track, or trajectory, conforms to a specific instance of a tour over the megalopolises, which are numbered in accordance with the route; the latter is defined by the transposition of indices), are constructed through a “nonstandard” variant of the dynamic programming method, which allows to avoid the process of constructing all the values of the Bellman function whenever precedence constraints are present.

SHARE: FaceBook Twitter Livejournal
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019