Minimax models for capacitated p -center problem in uncertain environment
- PDF / 381,960 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 185 Views
Minimax models for capacitated p-center problem in uncertain environment Bo Zhang1 · Jin Peng2
· Shengguo Li2
Accepted: 24 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The capacitated p-center problem is concerned with how to select p locations for facility centers and assign demand points to them such that the maximum distance between a demand point and its nearest center is minimized. This paper focuses on the capacitated p-center problem in an uncertain environment, in which demands and distances are regarded as uncertain variables. Consequently, two minimax models with uncertain parameters are formulated, and their crisp equivalences are investigated. Additionally, a hybrid algorithm based on the 99-method, a genetic algorithm and a tabu search algorithm is designed to solve the models. Finally, some numerical examples are presented to unveil the applications of the models and algorithm. Keywords Uncertain programming · Minimax model · P-center problem · Discrete location · Uncertainty theory
1 Introduction One of the most famous problems in locating facilities is the p-center problem. In the location literature, the p-center model is referred to as minimax model since it minimizes the maximum distance between each demand point and its nearest facility. The objective of the problem is to select p centers such that the maximum distance of a noncenter to its nearest center is minimized. The p-center problem can be either
B
Jin Peng [email protected] Bo Zhang [email protected] Shengguo Li [email protected]
1
School of Statistics and Mathematics, Zhongnan University of Economics and Law, Hubei 430073, China
2
Institute of Uncertain Systems, Huanggang Normal University, Hubei 438000, China
123
B. Zhang et al.
continuous or discrete. Facilities can be located anywhere in space in the continuous p-center problem, while they must be located within a given set of potential locations in the discrete p-center problem. Since the center problem was first proposed by Sylvester (1857) more than 150 years ago, the p-center model and its extensions have been investigated to model the placement of emergency facilities such as fire stations, hospitals and other public facilities. Specifically, Garfinkel et al. (1977) modeled the p-center problem using integer programming and discussed some properties of the problem. Furthermore, Albareda-Sambola et al. (2019) introduced an extension of the p-center problem with stratified demand. Du et al. (2020) developed a two-stage robust model for a reliable p-center problem. In the capacitated p-center problem, the quantity of demand for each demand point is considered. Namely, the total demand of demand points assigned to a certain facility cannot exceed the facility’s capacity. To begin, a polynomial time approximation algorithm for the particular case in which all the demands are the same was designed by Barilan et al. (1993). Moreover, Jaeger and Goldberg (1994) developed a polynomial exact algorithm for tree networks
Data Loading...
