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

An effective heuristic for large-scale fault-tolerant k-median problem

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

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

Авторы: Vasilyev I., Ushakov A.V., Maltugueva N., Sforza A.

Журнал: Soft Computing

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

Том: 23

Номера страниц: 2959-2967

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

Номер: 9

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

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

DOI: 10.1007/s00500-018-3562-6

Аннотация: We address a general fault-tolerant version of the k-median problem on a network. Unlike the original k-median, the objective is to find k nodes (medians or facilities) of a network, assign each non-median node (customer) to rj distinct medians, and each median nodes to rj- 1 other medians so as to minimize the overall assignment cost. The problem can be considered in context of the so-called reliable facility location, where facilities once located may be subject to failures. Hedging against possible disruptions, each customer is assigned to multiple distinct facilities. We propose a fast and effective heuristic rested upon consecutive searching for lower and upper bounds for the optimal value. The procedure for finding lower bounds is based on a Lagrangian relaxation and a specialized effective subgradient algorithm for solving the corresponding dual problem. The information on dual variables is then used by a core heuristic in order to determine a set of primal variables to be fixed. The effectiveness and efficiency of our approach are demonstrated in a computational experiment on large-scale problem instances taken from TSPLIB. We show that the proposed algorithm is able to fast find near-optimal solutions to problem instances with almost 625 million decision variables (on networks with up to 24978 vertices).

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

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

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

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

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

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

Публикация в печати: 1