Solving a routing problem with the aid of an independent computations scheme

A. G. Chentsov ; A. M. Grigoryev ; A. A. Chentsov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 1, pp. 60-74

Résumé

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.

Détail

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