Browsing Doctoral Dissertations by Author "Stančić, Olivera"
Now showing items 1-1 of 1
-
Stančić, Olivera (Beograd , 2018)[more][less]
Abstract: Hub Location Problems (HLP) represent an important class of optimiza- tion problems due to their numerous applications in many areas of real life. They often arise from practical situations that require routing of the flow from origin node (supplier) to the destination node (customer) under given conditions, such that the value of considered objective function is optimal. Hubs are special objects (nodes in the network) that represent centres for consolidation and flow collection between two selected locations - suppliers and customers. As transportation costs (per unit of flow) along the links that connect hub nodes are lower compared to other links in the network, directing the flow to hubs may lead to significant reductions of transportation cost in the network. The subject of this doctoral dissertation is one class of hub location problems, denoted as Hub Maximal Covering Problems (HMCPs) in the literature. The goal of HMCPs is to determine optimal locations for establishing certain number of hubs in order to maximize the total flow between all the covered origin-destination pairs, under the assumption of binary or partial covering. Three variants of the hub maximal covering problem are considered: uncapacitated single allocation p -hub maximal covering problem (USApHMCP), uncapacitated multiple allocation p -hub maximal covering problem (UMApHMCP) and uncapacitated r -allocation p -hub maximal covering problem (UrApHMCP). Note that the UrApHMCP has not been studied in the literature so far. All three considered problems are proven to be NP- hard. In case of USApHMCP, for the given set of hubs, the obtained sub-problem of optimal allocation of non-hub nodes by established hubs is also NP-hard. In this dissertation, new mathematical models for USApHMCP with binary and partial covering are proposed. The main advantage of the newly proposed models, in respect to existing ones from the literature, is the fact that small modifications of the new models enable their transformation to new models for p -hub maximal covering problems with different allocation schemes. More precisely, new models for UMApHMCP and UrApHMCP can be obtained from the newly proposed mod- els for USApHMCP in both coverage cases. All proposed models for USApHMCP and UMApHMCP are compared with the existing ones from the literature in the terms of efficiency within the framework of exact CPLEX 12.6 solver. Several hub data sets from the literature are used in numerical experiments when comparing the formulations. The obtained experimental results indicate that new models for UMApHMCP with both binary and partial coverage show the best performance in terms of solutions’ quality and execution times. For UrApHMCP and both coverage criteria, three mathematical models are proposed, and compared in terms of effi- ciency using the exact CPLEX 12.6 solver. It turns out that the exact solver finds optimal or feasible solutions only for small-size problem instances. Having in mind the complexity of all three problems under consideration and the results obtained by CPLEX 12.6 solver, the conclusion is that, in practice, exact methods can not provide solutions for large problem dimensions. For this reason, it was necessary to implement adequate heuristic or metaheuristic methods, in order to obtain high-quality solutions in short execution times, even in the case of large problem dimensions. Up to now, only simple but insufficiently effective heuris- tic methods for solving USApHMCP and UMApHMCP with binary coverage have been proposed in the literature, while the HMCP variants with partial coverage have not been previosly solved by using metaheuristic methods. As UrApHMCP with binary and partial coverage has not been previously considered in the litera- ture, no solution methods suggested for this problem existed up to now. Inspired by previous successful applications of variable neighborhood search method (VNS) to other hub location problems from the literature, this metaheuristic approach is applied to the considered HMCP problems. In this dissertation, several variants of VNS metaheuristic are designed and implemented: General Variable Neighborhood Search (GVNS) for USApHMCP, Basic Variable Neighborhood Search (BVNS) for UMApHMCP and a variant of General Variable Neighborhood Search (GVNS-R) for UrApHMCP. In the case of UrApHMCP, two additional metaheuristic meth- ods are proposed: Greedy Randomized Adaptive Search Procedure with Variable Neighborhood Descent (GRASP-VND) and Genetic Algorithm (GA). Constructive components of all proposed metaheuristics are adapted to the characteristics of the considered problems. Experimental study was conducted on the existing hub data sets from the lit- erature, which include instances with up to 1000 nodes in the network. The ob- tained results show that the proposed metaheuristics for the considered problems reach all known optimal solutions previously obtained by CPLEX 12.6 solver or establish new best-known solutions in significantly shorter CPU time compared to CPLEX 12.6. The proposed GVNS and BVNS metaheuristics quickly reach all known optimal solutions on small-size problem instances when solving USApHMCP and UMApHMCP, respectively. In the case of large-size problem instances, which have not been previously used for testing purposes for these problems, the proposed GVNS and BVNS return their best solutions in short execution times. The results obtained by the proposed GVNS-R and GRASP-VND for UrApHMCP on large-size problem instances indicate their effectiveness in both coverage cases. The proposed GA method showed to be successful only for UrApHMCP in binary covering, on instances up to 200 nodes. The variants of hub maximal covering problems considered in this dissertation are important from both theoretical and practical points of view. The new mathe- matical models proposed in this dissertation for the considered variants of HMCP, represent a scientific contribution to the theory of hub location problems, mathemat- ical modeling and optimization. Designed and implemented metaheuristic methods for solving the studied variants of HMCP are the scientific contribution to the field of optimization methods for solving location problems, as well as the development of software. The considered variants of HMCP have numerous applications in the optimization of telecommunication and transport systems, air passenger and goods transport, emergency services, postal and other delivery systems, so that the results obtained in this doctoral dissertation can be applied in practice, partially or com- pletely. URI: http://hdl.handle.net/123456789/4750 Files in this item: 1
StancicOliveradisertacija.pdf ( 1.688Mb )
Now showing items 1-1 of 1