Vestnik YuUrGU. Ser. Mat. Model. Progr., 2018, Volume 11, Issue 1, Pages 60–74
Solving a routing problem with the aid of an independent computations scheme
A. G. Chentsovab, A. M. Grigoryeva, A. A. Chentsova
a Krasovskii Institute of Mathematics and Mechanics UrB RAS, Ekaterinburg,
b Ural Federal University, Ekaterinburg, Russian Federation
This paper is devoted to the issues
in development and implementation of parallel algorithms for solving practical problems.
We consider a routing problem with constraints and complicated cost functions. The visited
objects are assumed to be clusters, or megalopolises (nonempty finite sets), and the visit to each one
entails certain tasks, which we call interior jobs. The order of visits is subject to precedence constraints.
The costs of movements depend on the set of pending tasks (not yet complete at the time of the movement), which
is also referred to as "sequence dependence", "position dependence", and "state dependence". Such dependence
arises, in particular, in routing problems concerning emergencies at nuclear power plants, similar to the Chernobyl
and Fukushima Daiichi incidents. For example, one could consider a disaster recovery problem concerned
with sequential dismantlement of radiation sources; in this case, the crew conducting the dismantlement
is exposed to the radiation from the sources that have not yet been dealt with. Hence the dependence
on pending tasks in the cost functions that measure the crew's radiation exposure. The
latter dependence reflects the "shutdown" operations for the corresponding radiation sources.
This paper sets forth an approach to a parallel solution for this problem, which was implemented and
run on the URAN supercomputer. The results of the computational experiment are presented.
dynamic programming; route; sequencing; precedence constraints; parallel computation.
|Russian Foundation for Basic Research
|This research was supported by Russian Foundation for Basic
Research (projects no. 17-08-01385, 18-07-00637).
PDF file (484 kB)
MSC: 49L20, 90C39
A. G. Chentsov, A. M. Grigoryev, A. A. Chentsov, “Solving a routing problem with the aid of an independent computations scheme”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 11:1 (2018), 60–74
Citation in format AMSBIB
\by A.~G.~Chentsov, A.~M.~Grigoryev, A.~A.~Chentsov
\paper Solving a routing problem with the aid of an independent computations scheme
\jour Vestnik YuUrGU. Ser. Mat. Model. Progr.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|