Страница публикации

Алгоритмы построения оптимального покрытия плоских фигур в динамической метрике

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Лебедев П.Д., Лемперт А.А., Казаков А.Л.

Журнал: Известия Института математики и информатики Удмуртского гос. университета

Язык публикации: russian

Том: 60

Номера страниц: 58-72

Количество страниц: 15

Год публикации: 2022

Отчетный год: 2022

Переводная версия: {"id":6166,"authors":"Kazakov A.L., Lempert A.A.","authors_count":2,"title":"On the route construction in changing environments using solutions of the eikonal equation","journal":"Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta","year":2021,"reportYear":2021,"volume":"58","number":"","month":null,"url":"","pages":"59\u201372","address":"","type":"\u0422\u0435\u043a\u0441\u0442","publisher":"","edition":"","language":"english","classification":"\u0421\u0442\u0430\u0442\u044c\u0438 \u0432 \u0437\u0430\u0440\u0443\u0431\u0435\u0436\u043d\u044b\u0445 \u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043d\u044b\u0445 \u0436\u0443\u0440\u043d\u0430\u043b\u0430\u0445","annotation":"The article deals with the vehicle routing problem in an environment with dynamically changing properties. The problem is relevant in current conditions when the delivery cost has a steady upward trend and is often comparable to the cost of the product itself. A central feature of the study is that the optimality criterion is the minimum delivery time, but not the distance traveled. The optical-geometric approach developed by the authors, based on the analogy between the propagation of light in an optically inhomogeneous medium and the minimization of the integral functional, is used as a research tool. We use exact and approximate solutions of the eikonal equations to describe wave fronts. Two original numerical algorithms for route construction are proposed and implemented as software. A computational experiment is performed that justified the effectiveness of the proposed model-algorithmic tools.","published_at":null,"doi":"10.35634\/2226-3594-2021-58-04","is_to_print":0,"is_special":0,"is_wos":1,"is_scopus":0,"is_risc":0,"is_editable":0,"publication_type_id":1,"added_by_rb_user_id":null,"notes":"","created_at":"2021-12-07 03:59:52","updated_at":"2021-12-07 03:59:52","translated_id":null,"quartile":"Q5","series":"","is_vak":0,"conference":null,"is_public_pdf":0,"eid":null,"wosid":null,"quartile_scopus":null,"report_type":null,"speaker":0,"is_wl":0,"quartile_wl":null,"count_pages":14,"date_event_start":null,"date_event_end":null,"location_event":null,"lvl_event":null,"link_event":null,"title_event":null,"is_affiliation_idstu":null,"is_expert_opinion":null,"quartile_vak":null,"id_author_reference":null,"is_cr":null,"quartile_cr":null,"registration_number":null}

DOI: 10.35634/2226-3594-2022-60-04

Аннотация: Рассматривается задача о построении наиболее эффективного (тончайшего) покрытия выпуклого множества на плоскости набором однотипных элементов. В качестве меры удаленности двух точек множества выступает наименьшее время, за которое можно попасть из одной точки в другую, и границей каждого покрывающего круга является изохрона. Подобные задачи возникают в приложениях, в частности, в системах гидролокации и подводного наблюдения. Для решения задач покрытия такими кругами и шарами ранее нами были предложены алгоритмы, основанные как на вариационных принципах, так и на основе геометрических методов. Целью настоящей статьи является построение покрытий в случае, когда характеристики среды изменяются во времени. Для решения указанной задачи предложен вычислительный алгоритм, основанный на теории волновых фронтов. Доказано утверждение о свойствах метода. Выполнены иллюстрирующие расчеты.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет