Page 23 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 23
sitivity analysis for p-median problems
Ágnes Vida Boglárka G.-Tóth
Institute of Informatics Institute of Informatics
University of Szeged University of Szeged
Vida.Agnes.1@stud.u-szeged.hu boglarka@inf.u-szeged.hu
ABSTRACT 1. INTRODUCTION
Network location problems are commonly associated with Locating facilities is a common problem when we want to
real world situations such as locating a new facility in a work with networks such as communication networks or traf-
city or setting up a new server in a computer network. In fic flows. In order to work with these networks in a math-
these real world situations changes can come up quite often, ematical aspect, we use an abstract model, a finite (often
such as a closed road because of an accident, or a broken weighted, non-oriented) graph G which has a set of vertices
connection in the network. These kind of problems give the (V ) and connecting edges (E ⊆ {V, V }). Weights are com-
motivation of this paper. Our aim was to inspect, how an monly attached to the edges, which represent the cost of the
existing network operates, when something has changed and transportation or the length of the road. Network locating
how sensitive a p-median solution is to the same changes. problems include several different questions, such as abso-
During our research we concentrated on deleting edges and lute center and median problems or p-center and p-median
solving p-median problem. In the p-median problem we try problems. For a good introduction in facility location prob-
to locate p facilities so the sum of the distances between lems on networks, see [2].
the facilities and the demand points is minimal. During the
sensitivity analysis we deleted different amounts of the edges In this paper we will concentrate on the p-median problem.
and we also tested the problem by locating 1, 2 or 3 medians The aim of the p-median problem is to find the optimal
to get a complex picture about the computational results. placement of p facilities on the network. The optimal lo-
During our work, we concentrated on how the solution and cation of the medians means that the sum of the distances
the location of the medians change. To get a complex picture between the vertices and the closest facility is minimal. To
about the results we used two different graphs. After the find the optimal location of the facilities, we must complete
tests we saw, that according to the shape of the graph, the the following constraints: one demand point can be assigned
number of the changes can be quite different. On the one to only one facility and maximum one facility can be placed
hand, when we worked with a graph which is easy to cut, at one vertex. We also have to provide that exactly p me-
the changes of the solution was unstable, and relatively big, dians are located. To understand the p-median problem we
while with a well-balanced graph, the changes were not that studied the article by Hakimi [3].
significant. On the other hand, the location of the facilities
did not change too much with either graph. During our research we always worked with non-oriented
n-vertex graphs with edge weights, which can also be rep-
Categories and Subject Descriptors resented with a square matrix, called weight matrix. Since
we are working on a graph, distance is always understood
G.2.2 [Mathematics of Computing]: Graph TheoryNet- as shortest path on the graph. From the weight matrix we
work problems; G.1.6 [Mathematics of Computing]: Op- need to determine the distance matrix with some methods
timization computing shortest paths on a graph.
General Terms The aim of this paper is to find out how sensitive a p-median
solution is when we delete edges from the graph. The moti-
Theory, application vation is the use of traffic networks, to inspect how the traffic
and the optimal locations of the p-medians change if some-
Keywords thing happens in the network. In this paper we concentrated
on deleting edges with different likelihood, to inspect how
p-median, sensitivity analysis, Mixed Integer Programming the cost and the optimal location of the p-medians change.
During our research we tested every case on two different
graphs to get a more complex picture about the computa-
tional results.
Similar works has been done investigating the effect of
changing network density in [4], and also studying facility
reliability issues in Berman et al. [1].
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.23-26 23
Koper, Slovenia, 10 October
Ágnes Vida Boglárka G.-Tóth
Institute of Informatics Institute of Informatics
University of Szeged University of Szeged
Vida.Agnes.1@stud.u-szeged.hu boglarka@inf.u-szeged.hu
ABSTRACT 1. INTRODUCTION
Network location problems are commonly associated with Locating facilities is a common problem when we want to
real world situations such as locating a new facility in a work with networks such as communication networks or traf-
city or setting up a new server in a computer network. In fic flows. In order to work with these networks in a math-
these real world situations changes can come up quite often, ematical aspect, we use an abstract model, a finite (often
such as a closed road because of an accident, or a broken weighted, non-oriented) graph G which has a set of vertices
connection in the network. These kind of problems give the (V ) and connecting edges (E ⊆ {V, V }). Weights are com-
motivation of this paper. Our aim was to inspect, how an monly attached to the edges, which represent the cost of the
existing network operates, when something has changed and transportation or the length of the road. Network locating
how sensitive a p-median solution is to the same changes. problems include several different questions, such as abso-
During our research we concentrated on deleting edges and lute center and median problems or p-center and p-median
solving p-median problem. In the p-median problem we try problems. For a good introduction in facility location prob-
to locate p facilities so the sum of the distances between lems on networks, see [2].
the facilities and the demand points is minimal. During the
sensitivity analysis we deleted different amounts of the edges In this paper we will concentrate on the p-median problem.
and we also tested the problem by locating 1, 2 or 3 medians The aim of the p-median problem is to find the optimal
to get a complex picture about the computational results. placement of p facilities on the network. The optimal lo-
During our work, we concentrated on how the solution and cation of the medians means that the sum of the distances
the location of the medians change. To get a complex picture between the vertices and the closest facility is minimal. To
about the results we used two different graphs. After the find the optimal location of the facilities, we must complete
tests we saw, that according to the shape of the graph, the the following constraints: one demand point can be assigned
number of the changes can be quite different. On the one to only one facility and maximum one facility can be placed
hand, when we worked with a graph which is easy to cut, at one vertex. We also have to provide that exactly p me-
the changes of the solution was unstable, and relatively big, dians are located. To understand the p-median problem we
while with a well-balanced graph, the changes were not that studied the article by Hakimi [3].
significant. On the other hand, the location of the facilities
did not change too much with either graph. During our research we always worked with non-oriented
n-vertex graphs with edge weights, which can also be rep-
Categories and Subject Descriptors resented with a square matrix, called weight matrix. Since
we are working on a graph, distance is always understood
G.2.2 [Mathematics of Computing]: Graph TheoryNet- as shortest path on the graph. From the weight matrix we
work problems; G.1.6 [Mathematics of Computing]: Op- need to determine the distance matrix with some methods
timization computing shortest paths on a graph.
General Terms The aim of this paper is to find out how sensitive a p-median
solution is when we delete edges from the graph. The moti-
Theory, application vation is the use of traffic networks, to inspect how the traffic
and the optimal locations of the p-medians change if some-
Keywords thing happens in the network. In this paper we concentrated
on deleting edges with different likelihood, to inspect how
p-median, sensitivity analysis, Mixed Integer Programming the cost and the optimal location of the p-medians change.
During our research we tested every case on two different
graphs to get a more complex picture about the computa-
tional results.
Similar works has been done investigating the effect of
changing network density in [4], and also studying facility
reliability issues in Berman et al. [1].
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.23-26 23
Koper, Slovenia, 10 October
