Search

This paper considers the uncapacitated r -allocation p -hub maximal covering problem (UrApHMCP), which represents a generalization of the well-known p -hub maximal covering problem, as it allows each non-hub node to send and receive flow via at most r hubs, r ≤ p . Two coverage criteria are considered in UrApHMCP — binary and, for the first time in the literature, partial coverage. Novel mathematical formulations of UrApHMCP for both coverage criteria are proposed. As the considered UrApHMCP is an NP-hard optimization problem, two efficient heuristic methods are proposed as solution approaches. The first one is a variant of General Variable Neighborhood Search (GVNS), and the second one is based on combining a Greedy Randomized Adaptive Search Procedure (GRASP) with Variable Neighborhood Descent (VND), resulting in a hybrid GRASP-VND method. Computational study is performed over the set of CAB and AP benchmark instances with up to 25 and 200 nodes, respectively, on TR instances including 81 nodes, as well as on the challenging USA423 and URAND hub instances with up 423 and 1000 nodes, respectively. Optimal or feasible solutions are obtained by CPLEX solver for instances with up to 50 nodes, while instances of larger dimensions are out of reach for CPLEX solver. On the other hand, both GVNS and GRASP-VND reach optimal solutions or improve lower bounds provided by CPLEX in short CPU times. In addition, both heuristics quickly return solutions on problem instances of large dimensions, thus indicating their potential to solve effectively large, realistic sized problem instances. The conducted non-parametric statistical tests confirm robustness of the proposed GVNS and GRASP-VND and demonstrate that the these two metaheuristics outperform other tested algorithms for UrApHMCP.

This paper deals with the uncapacitated r -allocation p-hub maximal covering problem (UrApHMCP) with binary coverage criterion. This problem consists of choosing p hub locations from a set of nodes so as to maximize the total demand covered while satisfying the r -allocation strategy. The applied binary coverage criterion ensures that the distance between any origin–destination pair through located hubs should be shorter than a predetermined distance. An integer linear programming model for the considered problem is introduced. As a solution method to UrApHMCP, a General Variable Neighborhood Search (GVNS) heuristic is proposed. A greedy procedure is used to construct an initial solution to GVNS. Neighborhood structures explored within the GVNS are defined by operators that change a set of chosen hubs and node to hub assignments. Variable Neighborhood Descent with sequential search strategy is used as an improvement procedure. The results of computational experiments on standard p-hub benchmark instances show the efficiency and effectiveness of the proposed GVNS when solving the considered problem.

Low price of raw materials in sugar industry and characteristics of production method lead to the specific transport organization problem. A new variant of Vehicle Scheduling Problem (VSP) that arises from transportation of sugar beet is considered. The problem is formulated as a Mixed Integer Quadratically Constraint Programming (MIQCP) model, which reflects the objective and specific constrains from practice. Computational experiments are conducted on real-life instances obtained from a sugar company in Serbia and the set of generated instances of larger dimensions. The proposed MIQCP model is used within the framework of Extended Lingo 15 solver, providing optimal solutions on small-size instances only. In order to find solutions on larger problem instances, a metaheuristic method based on Variable Neighborhood Search (VNS) is designed. Obtained computational results show that the proposed VNS quickly reaches all known optimal solutions on small-size instances. On larger problem instances, for which Lingo 15 solver could not find even a feasible solution, VNS provides best solutions in relatively short running times.

This study introduces a new problem for uncapacitated single allocation hub location in which pricing is taken into account. The objective is profit maximization by choosing the best hub and spoke topology and applying the optimal pricing, in the case of price-dependent demand. It is assumed that the source determining the number of hubs is endogenous. Two variants of the considered problem are addressed: deterministic and robust. For the initial non-linear model, we show how the deterministic variant can be reformulated as a mixed-integer linear program, excluding the price variables. In the robust counterpart case, the quantity of commodity flows between the pairs of customers is of stochastic nature. The goal of the robust variant is to design a hub and spoke network, together with the pricing structure, that would be immune to small perturbations of demand. Starting from the original model for the robust case, we have shown how to formulate an equivalent mixed-integer conic-quadratic program. In addition, we have proposed a 2-phase matheuristic approach for the robust variant. A computational study was conducted on the set of hub instances from the literature using the commercial state-of-the-art solver. The obtained computational results are thoroughly discussed, location patterns are analyzed and some managerial insights are provided. The experimental study also showed that the proposed matheuristic approach for the robust variant performs better compared to the commercial solver.

This study considers the Dynamic Minimum Cost Hybrid Berth Allocation Problem (DMCHBAP) with fixed handling times of vessels. The objective function to be minimized consists of three components: costs of positioning, waiting, and tardiness of completion for all vessels. A mathematical formulation of DMCHBAP, based on Mixed Integer Linear Programming (MILP), is proposed and used within the framework of commercial CPLEX 12.3 solver. As the speed of finding high-quality solutions is of crucial importance for an efficient and reliable decision support system in container terminal, two population-based metaheuristic approaches to DMCHBAP are proposed: combined Genetic Algorithm (cGA) and improvement-based Bee Colony Optimization (BCOi). Both cGA and BCOi are evaluated and compared against each other and against state-of-the-art solution methods for DMCHBAP on five sets of problem instances. The conducted computational experiments and statistical analysis indicate that population-based metaheuristic methods represent promising approaches for DMCHBAP and similar problems in maritime transportation.

This study considers the Dynamic Minimum Cost Hybrid BerthAllocation Problem (DMCHBAP) with fixed handling times of vessels.The objective function to be minimized consists of threecomponents: the costs of positioning, waiting, and tardiness ofcompletion for all vessels. Having in mind that the speed offinding high-quality solutions is of crucial importance fordesigning an efficient and reliable decision support system incontainer terminal, metaheuristic methods represent the naturalchoice to deal with DMCHBAP. Four variants of VariableNeighborhood Search (VNS) metaheuristic are designed for DMCHBAP.All four proposed VNS methods are evaluated on three classesof randomly generated instances with respect to solution quality and running times.The conducted computationalanalysis indicates that all four VNS-based methods representpromising solution approaches to DMCHBAP and similar problems inmaritime transportation. DOI: http://dx.doi.org/10.5755/j01.itc.47.3.20420

Graphical abstractDisplay Omitted HighlightsA well-known capacitated hub location problem CSAHLP is considered.We develop a hybrid of evolutionary algorithm and branch and bound (EA-BnB).Branch and bound is implemented by using parallelization techniques.The results of experimental study show reliability and efficiency of the EA-BnB.The EA-BnB achieved improvements regarding both solution quality and CPU time. In this study, we propose a hybrid optimization method, consisting of an evolutionary algorithm (EA) and a branch-and-bound method (BnB) for solving the capacitated single allocation hub location problem (CSAHLP). The EA is designed to explore the solution space and to select promising configurations of hubs (the location part of the problem). Hub configurations produced by the EA are further passed to the BnB search, which works with fixed hubs and allocates the non-hub nodes to located hubs (the allocation part of the problem). The BnB method is implemented using parallelization techniques, which results in short running times. The proposed hybrid algorithm, named EA-BnB, has been tested on the standard Australia Post (AP) hub data sets with up to 300 nodes. The results demonstrate the superiority of our hybrid approach over existing heuristic approaches from the existing literature. The EA-BnB method has reached all the known optimal solutions for AP hub data set and found new, significantly better, solutions on three AP instances with 100 and 200 nodes. Furthermore, the extreme efficiency of the implementation of this hybrid algorithm resulted in short running times, even for the largest AP test instances.

In this study, we propose a robust variant of a dynamic facility location problem that arises from optimizing the emergency service network of Police Special Forces Units (PSFUs) in the Republic of Serbia. We present for the first time a mathematical programming formulation of the problem under consideration. We further propose a Variable Neighborhood Search (VNS) method with an efficient local search procedure for solving real-life problem instances that remained out of reach of CPLEX solver. The results presented in this paper may help in optimizing the network of PSFUs and other security networks as well.

This study introduces the Multi-Type Maximal Covering Location Problem (MTMCLP) that arises from the design of emergency service networks, and represents a generalization of the well-known Maximal Covering Location Problem (MCLP). Differently from the basic MCLP, several types of incidents and emergency units are considered and hierarchy of emergency units of different types is assumed in the MTMCLP. The numbers of available emergency units of each type are limited to some constants. The objective of the MTMCLP is to choose locations for establishing emergency units of each type, such that the total number of covered incidents is maximized. In order to provide a decision maker with optimal solutions in an efficient manner, a two-phase optimization approach to the MTMCLP is designed. In the first phase, a variant of Reduced Variable Neighborhood Search (RVNS) is applied to quickly find a high-quality solution. The obtained RVNS solution is used as a good starting point for the Linear Programming method in the second phase, which returns the optimal solution to the MTMCLP. All constructive elements of the proposed two-phase method, denoted as RVNS-LP, are adapted to the characteristics of the considered problem. The RVNS-LP approach is evaluated on real-life instances obtained from two networks of police units in Montenegro and Serbia, and randomly generated test instances of larger dimensions. Experimental evaluation shows that the proposed RVNS-LP reached all optimal solutions on all real-life test instances in very short CPU time. On generated test instances, the RVNS-LP also returned optimal solutions in all cases, within short running times and significant time savings compared to CPLEX solver. The mathematical model and the proposed two-phase optimization method may be applicable in the design and management of various emergency-service networks.DOI: http://dx.doi.org/10.5755/j01.itc.46.1.13853

We consider the Multilevel Uncapacitated Facility Location Problem (MLUFLP) and propose a new efficient integer programming formulation of the problem that provides optimal solutions for the MLUFLP test instances unsolved to optimality up to now. Further, we design a parallel Memetic Algorithm (MA) with a new strategy for applying the local search improvement within the MA frame. The conducted computational experiments show that the proposed MA quickly reaches all known optimal and best known solutions from the literature and additionally improves several solutions for large-scale MLUFLP test problems.

Long-term health care facilities have gained an important role in today’s health care environments, due to the global trend of aging of human population. This paper considers the problem of network design in health-care systems, named the Long-Term Care Facility Location Problem (LTCFLP), which deals with determining locations for long-term care facilities among given potential sites. The objective is to minimize the maximal number of patients assigned to established facilities. We have developed an efficient hybrid method, based on combining the Evolutionary Approach (EA) with modified Variable Neighborhood Search method (VNS). The EA method is used in order to obtain a better initial solution that will enable the VNS to solve the LTCFLP more efficiently. The proposed hybrid algorithm is additionally enhanced by an exchange local search procedure. The algorithm is benchmarked on a data set from the literature with up to 80 potential candidate sites and on large-scale instances with up to 400 nodes. Presented computational results show that the proposed hybrid method quickly reaches all optimal solutions from the literature and in most cases outperforms existing heuristic methods for solving this problem.

In this study, we consider a variant of the Bilevel Uncapacitated Facility Location Problem (BLUFLP) in which the clients choose suppliers based on their own preferences. We propose three metaheuristic methods for solving this problem: Particle Swarm Optimization (PSO), Simulated Annealing (SA) and a combination of Reduced and Basic Variable Neighborhood Search Method (RVNS-VNS). The solution encoding and constructive elements of all three proposed algorithms are adapted to the problem under consideration. The results of computational tests on problem instances with up to 2000 clients and 2000 potential facility locations show good performance of all three proposed methods, even on large problem dimensions. Finally, the obtained results indicate that the proposed RVNS-VNS method outperforms the PSO and SA methods in the sense of solutions' quality and running times.

In this study we consider mathematical models that arise from the problem of establishing and optimally utilizing the network of Police Special Forces Units (PSFUs) in the Republic of Serbia. The goal is to locate certain number of PSFUs in the given network in order to minimize the maximal load of established emergency units. We have designed an efficient metaheuristic method, based on the combination of the Reduced Variable Neighborhood Search (RVNS) and the basic Variable Neighborhood Search (VNS). The proposed approach, named RVNS-VNS, involves two efficient improvement procedures: Local Search Deletion and Steepest-descent Hill Climbing, which help the algorithm converge to high-quality solutions. Computational experiments show that the proposed RVNS-VNS method quickly reaches all known optimal solutions. Furthermore, it provides solutions for the instances that CPLEX solver was unable to obtain.

This paper addresses the capacitated hub location problem (CHLP), which is a variant of the classical capacitated hub problem. What is presented is a modified mixed integer linear programming (MILP) formulation for the CHLP. This modified formulation includes fewer variables and constraints compared to the existing problem formulations in the literature. We propose two evolutionary algorithms (EAs) that use binary encoding and standard genetic operators adapted to the problem. The overall performance of both EA implementations is improved by a caching technique. In order to solve large-scale instances within reasonable time, the second EA also uses a newly designed heuristic to approximate the objective function value. The presented computational study indicates that the first EA reaches optimal solutions for all smaller and medium-size problem instances. The second EA obtains high-quality solutions for larger problem dimensions and provides solutions for large-scale instances that have not been addressed in the literature so far.

In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.

In this paper we describe a genetic algorithm (GA) for the uncapacitated multiple allocation p-hub center problem (UMApHCP). Binary coding is used and genetic operators adapted to the problem are constructed and implemented in our GA. Computational results are presented for the standard hub instances from the literature. It can be seen that proposed GA approach reaches all solutions that are proved to be optimal so far. The solutions are obtained in a reasonable amount of computational time, even for problem instances of higher dimensions.

In this study, we consider a variant of the Bilevel Uncapacitated Facility Location Problem (BLUFLP), in which the clients choose suppliers based on their own preferences. We propose and compare three metaheuristic approaches for solving this problem: Particle Swarm Optimization (PSO), Simulated Annealing (SA), and a combination of Reduced and Basic Variable Neighborhood Search Method (VNS). We used the representation of solutions and objective function calculation that are adequate for all three proposed methods. Additional strategy is implemented in order to provide significant time savings when evaluating small changes of solution's code in improvement parts. Constructive elements of each of the proposed algorithms are adapted to the problem under consideration. The results of broad computational tests on modified problem instances from the literature show good performance of all three proposed methods, even on large problem dimensions. However, the obtained results indicate that the proposed VNS-based has significantly better performance compared to SA and PSO approaches, especially when solving large-scale problem instances. Computational experiments on large scale benchmarks demonstrate that the VNS-based method is fast, competitive, and able to find high-quality solutions, even for large-scale problem instances with up to 2000 clients and 2000 potential facilities within reasonable CPU times.

Online social networks provide large amount of valuable data and may serve as research platforms for various social network analysis tools. In this study, we propose a mathematical model for efficient exploration of an online social network. The goal is to spend minimal amount of time searching for characteristics which define a sub-network of users sharing the same interest or having certain common property. We further develop an efficient hybrid method (HEA), based on the combination of an Evolutionary Algorithm (EA) with Local Search procedure (LS). The proposed mathematical model and hybrid method are benchmarked on real-size data set with up to 10 000 users in a considered social network. We provide optimal solutions obtained by CPLEX solver on problem instances with up to 100 users, while larger instances that were out of reach of the CPLEX were efficiently solved by the proposed hybrid method. Presented computational results show that the HEA approach quickly reaches all optimal solutions obtained by CPLEX solver and gives solutions for the largest considered instance in very short CPU time.

This paper deals with a two-stage uncapacitated facility location problem (TSUFLP), which has significant application in telecommunication sector. Given the set of demand points and the sets of possible locations for the first and second level concentrators (switches, multiplexors), the goal of the TSUFLP is to define the structure of two-level concentrator access network, such that the the total costs of establishing such a network are minimized. We consider two variants of the TSUFLP from the literature and propose an efficient memetic algorithm (MA) based on hybridization of the evolutionary approach and two local-search heuristics. A simulated annealing method, which is incorporated in the MA frame, additionally improves the efficiency of the proposed MA. The described MA approach is benchmarked on test instances of medium and large dimensions from the literature, which are adapted for the TSUFLP and involve from 50 to 500 user nodes. In order to test effectiveness of the MA, we further modify some large-scale instances from the literature, which include 1000 and 2000 demand points. Exhaustive computational experiments show that the proposed MA method quickly reaches all known optimal solutions, previously obtained by CPLEX solver or existing exact method from the literature, and also provides solutions on large-scale data set in short CPU times. Regarding both solution quality and running times, we conclude that the proposed MA represents a powerful metaheuristic method for solving the TSUFLP and other similar network problems. DOI: http://dx.doi.org/10.5755/j01.itc.42.2.1768

This study considers the well-known uncapacitated multiple allocation p-hub centre problem (UMApHCP) and introduces its robust variant (UMApHCP-R) by involving flow variations with unknown distributions. As a solution method to both UMApHCP and UMAPHCP-R, a hybrid metaheuristic algorithm (HMA) is proposed, which successfully combines particle swarm optimisation and a local search heuristic. Constructive elements of the HMA are adapted to the considered problems and its parameters are experimentally adjusted. Experimental results obtained for the UMApHCP show the superiority of the proposed HMA over the existing methods from the literature on standard hub instances in the sense of solution quality or running times. The results obtained by the HMA on large-scale hub instances with up to 900 nodes are also presented. The analysis of the HMA results for the UMApHCP-R on selected problem instances shows the impact of flow variations on the objective function value. [Received 11 September 2016; Revised 23 March 2017; Accepted 7 July 2017]

This paper deals with a variant of a discrete location problem of establishing long-term care facilities in a given network. The objective is to determine optimal locations for these facilities in order to minimize the maximum number of assigned patients to a single facility. We propose an efficient evolutionary approach (EA) for solving this problem, based on binary encoding, appropriate objective function and standard genetic operators. Unfeasible individuals in the population are corrected to be feasible, while applied EA strategies keep the feasibility of individuals and preserve the diversity of genetic material. The algorithm is benchmarked on a real-life test instance with 33 nodes and the obtained results are compared with the existing ones from the literature. The EA is additionally tested on new problem instances derived from the standard ORLIB AP hub data set with up to 400 potential locations. For the first time in the literature we report verified optimal solutions for most of the tested problem instances with up to 80 nodes obtained by the standard optimization tool CPLEX. Exhaustive computational experiments show that the EA approach quickly returns all optimal solutions for smaller problem instances, while large-scale instances are solved in a relatively short CPU time. The results obtained on the test problems of practical sizes clearly indicate the potential of the proposed evolutionary-based method for solving this problem and similar discrete location problems. DOI: http://dx.doi.org/10.5755/j01.itc.41.1.1115

In this paper the Capacitated Single Allocation p-Hub Median Problem (CSApHMP) is considered. This problem has a wide range of applications within the design of telecommunication and transportation systems. A heuristic method, based on a genetic algorithm (GA) approach, is proposed for solving the CSApHMP. The described algorithm uses binary encoding and modified genetic operators. The caching technique is also implemented in the GA in order to improve its effectiveness. Computational experiments demonstrate that the GA method quickly reaches optimal solutions for hub instances with up to 50 nodes. The algorithm is also benchmarked on large scale hub instances with up to 200 nodes that are not solved to optimality so far.

Hub location problems are widely used for network designing. Many variations of these problems can be found in the literature. In this paper we deal with the uncapacitated multiple allocation hub location problem (UMAHLP). We propose a genetic algorithm (GA) for solving UMAHLP that uses binary encoding and genetic operators adapted to the problem. Overall performance of GA implementation is improved by caching technique. We present the results of our computational experience on standard ORLIB instances with up to 200 nodes. The results show that GA approach quickly reaches all optimal solutions that are known so far and also gives results on some large-scale instances that were unsolved before.