Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a nece...Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p-median problem on block graphs, developing algorithms and showing that these problems can be solved in O(n log n) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.展开更多
We view a facility system as a kind of supply chain and model it as a connected graph in which the nodes represent suppliers, distribution centers or customers and the edges represent the paths of goods or information...We view a facility system as a kind of supply chain and model it as a connected graph in which the nodes represent suppliers, distribution centers or customers and the edges represent the paths of goods or information. The efficiency, and hence the reliability, of a facility system is to a large degree adversely affected by the edge failures in the network. In this paper, we consider facility systems' reliability analysis based on the classical p-median problem when subject to edge failures. We formulate two models based on deterministic case and stochastic case to measure the loss in efficiency due to edge failures and give computational results and reliability envelopes for a specific example.展开更多
The gravity p-median model is an important improvement to the widely-used p-median model. However, there is still a debate on its validity in empirical applications. Previous studies even doubt the significance of the...The gravity p-median model is an important improvement to the widely-used p-median model. However, there is still a debate on its validity in empirical applications. Previous studies even doubt the significance of the gravity p-median model. Using a case study of tertiary hospitals in Shenzhen, China, this study re-examines the difference between the gravity p-median model with the p-median model, by decomposing the difference between the two models into gravity rule and variant attraction. This study also proposes a modified gravity p-median model by incorporating a distance threshold. The empirical results support the validity of the gravity p-median model, and also reveal that only when the attractions of candidate facility locations are variable will the gravity p-median model lead to different results with the p-median model. The difference between the modified gravity p-median model and the gravity p-median model is also examined. Moreover, the impacts of the distance-decay parameter and distance threshold on solutions are investigated. Results indicate that a larger distance-decay parameter tends to result in a more dispersed distribution of optimal facilities and a smaller average travel time, and a smaller distance threshold can better promote the spatial equity of facilities. The proposed method can also be applied in studies of other types of facilities or in other areas.展开更多
This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a...This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network.We call this problem as the integer inverse undesirable p-median location model.Exact combinatorial algorithms with O(p2n logn)and O(p2(n logn+n log nmax))running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms,respectively.Furthermore,it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in O(p-n log n)time.展开更多
文摘Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p-median problem on block graphs, developing algorithms and showing that these problems can be solved in O(n log n) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.
文摘We view a facility system as a kind of supply chain and model it as a connected graph in which the nodes represent suppliers, distribution centers or customers and the edges represent the paths of goods or information. The efficiency, and hence the reliability, of a facility system is to a large degree adversely affected by the edge failures in the network. In this paper, we consider facility systems' reliability analysis based on the classical p-median problem when subject to edge failures. We formulate two models based on deterministic case and stochastic case to measure the loss in efficiency due to edge failures and give computational results and reliability envelopes for a specific example.
基金Supported by the Urban China Initiative (UCI) through the UCI grant 2017
文摘The gravity p-median model is an important improvement to the widely-used p-median model. However, there is still a debate on its validity in empirical applications. Previous studies even doubt the significance of the gravity p-median model. Using a case study of tertiary hospitals in Shenzhen, China, this study re-examines the difference between the gravity p-median model with the p-median model, by decomposing the difference between the two models into gravity rule and variant attraction. This study also proposes a modified gravity p-median model by incorporating a distance threshold. The empirical results support the validity of the gravity p-median model, and also reveal that only when the attractions of candidate facility locations are variable will the gravity p-median model lead to different results with the p-median model. The difference between the modified gravity p-median model and the gravity p-median model is also examined. Moreover, the impacts of the distance-decay parameter and distance threshold on solutions are investigated. Results indicate that a larger distance-decay parameter tends to result in a more dispersed distribution of optimal facilities and a smaller average travel time, and a smaller distance threshold can better promote the spatial equity of facilities. The proposed method can also be applied in studies of other types of facilities or in other areas.
文摘This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network.We call this problem as the integer inverse undesirable p-median location model.Exact combinatorial algorithms with O(p2n logn)and O(p2(n logn+n log nmax))running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms,respectively.Furthermore,it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in O(p-n log n)time.
