Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке: https://scidar.kg.ac.rs/handle/123456789/11385
Назив: Novel formulations and VNS-based heuristics for single and multiple allocation p-hub maximal covering problems
Аутори: Stančić, Olivera
Miskovic M.
Stanimirovic Z.
Todosijević R.
Датум издавања: 2017
Сажетак: © 2017, Springer Science+Business Media New York. This paper deals with uncapacitated single and multiple allocation p-hub maximal covering problems (USApHMCP and UMApHMCP) with binary and partial covering criteria. We present new mixed-integer programming formulations of the considered problems, which are valid for both binary and partial coverage cases. The efficiency of the proposed formulations is evaluated through computational experiments on smaller-size instances, and compared with the state-of-the art models from the literature. The obtained results indicate that the new UMApHMCP formulation outperforms the existing one for both coverage criteria in the sense of solutions’ quality and running times. In order to solve instances of larger problem dimension, we develop two heuristic methods based on variable neighborhood search: general VNS (GVNS) for USApHMCP and basic VNS (BVNS) for UMApHMCP. The proposed GVNS and BVNS involve the same shaking procedure in order to hopefully escape local minima traps, while local search phases in GVNS and BVNS use different neighborhood structures in accordance with applied allocation schemes. Computational experiments conducted on smaller-size instances showed that both GVNS and BVNS almost instantly reach all known optimal solutions. In addition, the proposed GVNS and BVNS showed to be very efficient when solving large and large-scale hub instances with up to 1000 nodes, which were not previously considered as test instances for the considered problems. Both GVNS and BVNS provided best solutions on challenging USApHMCP and UMApHMCP instances for both coverage cases in short running times, which indicates their potential to be applied to similar problems.
URI: https://scidar.kg.ac.rs/handle/123456789/11385
Тип: article
DOI: 10.1007/s10479-017-2508-1
ISSN: 0254-5330
SCOPUS: 2-s2.0-85019031703
Налази се у колекцијама:Faculty of Economics, Kragujevac

Број прегледа

488

Број преузимања

9

Датотеке у овој ставци:
Датотека Опис ВеличинаФормат 
PaperMissing.pdf
  Ограничен приступ
29.86 kBAdobe PDFСличица
Погледајте


Ставке на SCIDAR-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.