حل مسئله مرکز فازی پی-توپی توسط الگوریتم ژنتیک ترکیب جستجوی محلی

The p-hub center problem has extensive applications in various real-world fields such as transportation and telecommunication systems. This paper presents a new risk aversion p-hub center problem with fuzzy travel times, in which value-at-risk (VaR) criterion is adopted in the formulation of objection function. For trapezoidal and normal fuzzy travel times, we first turn the original VaR p-hub center problem into its equivalent parametric mixed-integer programming problem, then develop a hybrid algorithm by incorporating genetic algorithm and local search (GALS) to solve the parametric mixed-integer programming problem. In our designed GALS, the GA is used to perform global search, while LS strategy is applied to each generated individual (or chromosome) of the population. Finally, we conduct two sets of numerical experiments and discuss the experimental results obtained by general-purpose LINGO solver, standard GA and GALS. The computational results show that the GALS achieves the better performance than LINGO solver and standard GA.

Hub-and-spoke systems are used in the design of networks for passenger airlines, express package delivery systems, communication, and other types of transportation networks. Hubs are centralized facilities in these networks whose functions are to consolidate, switch and sort, and allow for the replacement of direct connections between all nodes with fewer and indirect connections. A hub-and-spoke location problem can be generically defined as a hub location problem in which the location of hubs and the assignment of the spokes (non-hub nodes) to the hubs must be determined. Surveys on various different hub location problems, as well as classification schemes can be found in Campbell et al. [6], and O’Kelly and Miller [19]. In this paper, we concentrate on the p-hub center problem, which can be used to design a hub-and-spoke network. The p-hub center problem is a combinatorial optimization problem which aims to locate p hubs in a network and to allocate the spokes to hubs so that the maximum travel time (cost, distance, etc.) between any origin–destination (o–d) pair is minimized. Campbell [5] first introduced the p-hub center problem, and formulated it as a quadratic program. Several linearizations of quadratic programs were proposed by Kara and Tansel [13], who also provided an NP-completeness proof for single allocation case. On the basis of the concept radius of hubs, Ernst et al. [9] proposed a mixed-integer linear programming for the single and multiple allocation p-hub center problem, which is a subproblem of the p-hub center problem. Campbell et al. [4] also studied the allocation subproblem and provided integer programming formulations for both uncapacitated and capacitated cases. A single-relocation heuristic algorithm with tabu search is developed for the p-hub center problem considering flow volumes in Pamuk and Sepil [22], where extensive numerical experiments were also carried out. The interested reader may refer to the survey of the deterministic p-hub center problem in Alumur and Kara [2]. In hub-and-spoke systems, there are many uncertain factors which can affect the location decisions processes such as demands, costs, time and other parameters. The significance of uncertainty has prompted some researchers to address stochastic parameters in hub location problems. For example, Yang [26] presented a stochastic model for air freight hub location and flight route planning under seasonal demand variations, who modeled the problem as a two-stage stochastic program with recourse, in which the location of hub facilities is considered as a first-stage decision and the planning of flight routes as a second-stage decision; Contreras et al. [8] studied stochastic uncapacitated hub location problem in which uncertainty is associated to demands and transportation costs, and describe a Monte Carlo simulation-based algorithm that integrates a sample average approximation scheme with a Benders decomposition algorithm to solve the problem. As travel time is typically uncertain in reality, Sim et al. [23] first attempted to tackle p-hub center problem with stochastic time and service-level constraints involving mutually independent normal distributions; Yang et al. [25] studied the p-hub center problem with discrete random travel time, which seeks to configure a network to minimize efficient time point. Marianov and Serra [17] focused on randomness at the hub nodes by representing hub airports as M/D/c queues and limiting through chance constraints the number of airplanes that can queue at an airport. The aim of this work is to optimize a p-hub center problem in fuzzy environments. The fuzziness is associated with the travel times that are sensitive to traffic conditions. To the best of our knowledge this case has not yet been examined in the literature. In fact, in real world problems, decision makers may encounter a fuzzy environment in a hub-and-spoke system. In such a case, we may rely on the experts’ experience or the decision-makers’ subjective judgement to estimate these uncertain parameters. In the present paper, we consider a new class of fuzzy p-hub center problems. Specifically, the p-hub center problem with fuzzy coefficients is formulated as a fuzzy VaR programming model. Its essential idea is to optimize the critical value of the total fuzzy objective with prescribed credibility level subject to some constraints. The crisp equivalents are also discussed when the fuzzy travel times are characterized by trapezoidal or normal fuzzy variables. The equivalent parametric mixed-integer problems are NP-hard, so we have to rely on heuristic solution approaches to finding its approximate optimal solution when the size of a problem becomes large. GA has become a popular method of solving hard combinatorial optimization problems, it is a stochastic search procedure based on the mechanics of natural selection, genetics and evolution [12]. Since Holland [12], GA has been well discussed and summarized in numerous literature such as Gen and Cheng [10], Goldberg [11], and Liu [14]. Sequential as well as parallel GA have been successfully applied to a variety of problems in operations research, and several applications are found in Cadenas et al. [3], Chen [7], and Montana and Hussain [18]. On the other hand, LS has been a generally applicable approach that can be used to find approximate optimal solutions to hard optimization problems. The basic idea is to start from an initial solution and to search for successive improvements by examining neighboring solutions. In the literature, a large variety of LS algorithms has been proposed, each aiming at different remedies to the risk of getting stuck in poor local optima. At present, there is a proliferation of LS algorithms or, as they are often called, metaheuristics [20]. Since all of these methods apply some kind of neighborhood search techniques, we will simply call them LS algorithms, following the early textbook treatment by Papadimitriou and Steiglitz [21] and the book edited by Aarts and Lenstra [1]. Simple GA is difficult to apply directly and successfully into many difficult-to-solve optimization problem. In addition, GA is not well-suited for fine-turning structures which are very close to optimal solutions. Thus, various non-standard implementations have been created for particular problem. In this new perspective, it is essential to incorporate conventional heuristics into GAs to construct a more competitive algorithm. On the other hand, the approximate optimal solution found by a local search algorithm may depend on the initial solution used. However, a multi-start scheme may overcome this problem. As a further refinement, the effectiveness of multi-start iterative approach may be improved by using the information available from the solution obtained in the individual cycles. Since the complementary properties of GA and LS can mutually compensate their respective weakness, the hybrid approach performs well. Following this line, we propose an efficient hybrid algorithm based on the combination of global and local search techniques. The proposed approach keeps the feasibility of individuals by using specific representation and modified genetic operators [24]. Computational results are presented to demonstrate that the proposed approach is reasonable and effective. The rest of this paper is organized as follows. In Section 2, we formulate a new class of fuzzy p-hub center problems with VaR criteria. The crisp equivalents for common fuzzy variables are discussed in Section 3. Section 4 designs a GALS solution approach by incorporating GA and LS. Computational results are reported in Section 5 by using the proposed algorithm. Finally, Section 6 covers the conclusions.

In this paper, we have developed a new fuzzy p-hub center problem with VaR criterion, where the travel times are characterized by fuzzy variables with known possibility distributions. The major new results include the following several aspects: (i) A new fuzzy p-hub center problem has been developed, where we adopted the VaR criterion in the objective. For common fuzzy travel times, the proposed p-hub center problems are equivalent to parametric mixed-integer programming models. (ii) According to the structural characteristics of the equivalent parametric mixed-integer programming problems, we designed a GALS algorithm to solve them. Our objective was to exploit the features of GALS algorithm in finding the location of hubs, and the assignment of non-hub to the hubs. (iii) Two sets of numerical experiments based on 25 city nodes and URAND data sets were carried out to test the performance of the proposed GALS heuristic algorithm. (iv) We also compared the designed GALS algorithm with general-purpose LINGO solver and standard GA, and the computational results showed that the GALS achieves better performance than LINGO solver and standard GA.