RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik YuUrGU. Ser. Mat. Model. Progr.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik YuUrGU. Ser. Mat. Model. Progr., 2018, Volume 11, Issue 1, Pages 60–74 (Mi vyuru418)  

Mathematical Modelling

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, Russian Federation
b Ural Federal University, Ekaterinburg, Russian Federation

Abstract: 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.

Keywords: dynamic programming; route; sequencing; precedence constraints; parallel computation.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-07-00637
17-08-01385_a
This research was supported by Russian Foundation for Basic Research (projects no. 17-08-01385, 18-07-00637).


DOI: https://doi.org/10.14529/mmp180106

Full text: PDF file (484 kB)
References: PDF file   HTML file

UDC: 519.6
MSC: 49L20, 90C39
Received: 23.11.2017
Language:

Citation: 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
\Bibitem{CheGriChe18}
\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.
\yr 2018
\vol 11
\issue 1
\pages 60--74
\mathnet{http://mi.mathnet.ru/vyuru418}
\crossref{https://doi.org/10.14529/mmp180106}
\elib{http://elibrary.ru/item.asp?id=32711849}


Linking options:
  • http://mi.mathnet.ru/eng/vyuru418
  • http://mi.mathnet.ru/eng/vyuru/v11/i1/p60

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:92
    Full text:25
    References:13

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019