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

A graph clustering based decomposition approach for large scale p-median problems

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

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

Авторы: Masone A., Sforza A., Sterle C., Vasilyev I.

Журнал: International Journal of Artificial Intelligence

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

Том: 16

Номера страниц: 116-129

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

Номер: 1

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

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

Аннотация: The p-median problem (PMP) is the well known network optimization problem of discrete location theory. In many real applications PMPs is defined on very large scale networks, for which ad-hoc exact and/or heuristic methods have to be developed. To this aim, in this work we propose a heuristic decomposition approach which exploits the decomposition of the network into disconnected components obtained by a graph clustering algorithm. Then, in each component several PMPs are solved for suitable ranges of p by a Lagrangian dual and simulated annealing based algorithm. The solution of the whole initial problem is obtained combining all the PMPs solutions through a multi-choice knapsack model. The proposed approach is tested using several graph clustering algorithms and compared with the results of the state-of-the-art heuristic methods.

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

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

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

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

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

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