petek, 17. maj 2024 Zorica STANIMIROVIĆ: A GVNS-based solution approach to the Uncapacitated Single Allocation p-hub Maximal Covering Problem

V ponedeljek, 20. maja 2024, bo ob 16.00 uri izvedeno
predavanje v okviru PONEDELJKOVEGA SEMINARJA RAČUNALNIŠTVA IN INFORMATIKE
Oddelkov za Informacijske znanosti in tehnologije UP FAMNIT in UP IAM.

ČAS/PROSTOR: 20. maj 2024 ob 16.00 v FAMNIT-VP2.

-----------------------------------------------------
PREDAVATELJICA: Zorica STANIMIROVIĆ
-----------------------------------------------------

Zorica Stanimirović PhD, is a Full Professor at the Department for Numerical Mathematics and Optimization, Faculty of Mathematics, University of Belgrade and Coordinator for International Cooperation of the same institution. She graduated from the Faculty of Mathematics in 2000, received a master's degree in 2004, and PhD in 2007 at the same institution. She has been the local coordinator for several international projects and a member of program or organizational boards of several national and international conferences. From 2010 to 2015, she was Vice-Dean for Science and Research at the Faculty of Mathematics. Her research areas include Mathematical Modeling, Combinatorial Optimization, Metaheuristics, and Hybrid Optimization Methods. Up to now, she has published over 120 publications that have been cited 1182 times, her h-index is 19 and her i10 index is 32. More information and a list of publications are available at http://www.matf.bg.ac.rs/p/zoricast/pocetna/.

-------------------------------------------------------------------------------------------------------------------------------------------------------------
NASLOV: A GVNS-based solution approach to the Uncapacitated Single Allocation p-hub Maximal Covering Problem
-------------------------------------------------------------------------------------------------------------------------------------------------------------

POVZETEK:

Hub covering problems represent extensions of classical covering location problems and they are widely studied in the literature, due to their theoretical and practical importance in location science. This study considers the Uncapacitated Single Allocation p-hub Maximal Covering Problem (USApHMCP) with binary coverage criterion. The USApHMCP considers a complete symmetric graph G=(N,E), where N represents a set of nodes, while E denotes a set of edges. Transportation costs per unit of flow and the flow demand for each origin-destination (O-D) pair i-j are given (i,j ϵ N). The goal of USApHMCP is to choose locations of p hubs from the set H ⊆ N, and to allocate non-hub nodes to hubs, such that the total covered flow between O-D pairs is maximized. The flow between an O-D pair is considered "covered" if the transportation costs are within the given maximum service distance (coverage radius). Each non-hub node is assigned to exactly one hub and the incoming and outgoing flows are sent only through that hub (single allocation scheme). A mixed integer formulation of the USApHMCP is presented and used within the framework of CPLEX solver on hub instances from the literature. As USApHMCP belongs to the class of NP-hard optimization problems, a solution approach based on General Variable Neighborhood Search (GVNS) heuristic is developed to tackle instances of larger problem dimensions. Two variants of GVNS heuristics are proposed, which use different procedures in the solution improvement phase: Sequential Variable Neighborhood Descent and Nested Variable Neighborhood Descent. The impact of these two procedures on overall GVNS performance is investigated through extensive computational experiments on standard hub instances from the literature. The obtained results indicate the efficiency of both GVNS variants, however, the one with Nested Variable Neighborhood Descent procedure was more successful with respect to both solution quality and running times. The results of GVNS on large-scale problem instances are also presented, showing the potential of GVNS when solving USApHMCP on realistic-size hub networks.

Seminar bo potekal v angleškem jeziku v FAMNIT-VP2 s pričetkom ob 16:00 uri.

Vabljeni.