Artykuły :: Transport :: Conference papersAn impact of set of centers of distribution system design problem on computational time of solving algorithm Marta JANĂÄKOVĂ, AlĹžbeta SZENDREYOVĂ  20070606 12:05:56 
1. INTRODUCTION
When solving the location problem, it is need to accept not only delivery cost but also fixed charge to create new centers. Even the problem is simple uncapacitated location problem, it is difficult, there are exact algorithms, which can solve it in real time. To give other condition to basic location problem the problem will be more complicated. That is why the algorithm cannot solve the new problem. In some cases it is possible to transform this model to basic location problem considering the condition to the objective function. Such way we solve the uncapacitated location problem with maximal service distance. We find out that exact algorithm does not work on transformed transportation network as well how it works on real network. In this paper we deal with the influence of cardinality of a possible location set on time consumption of an exact algorithm.
2. MATHEMATICAL MODEL
We add condition to the basic problem, which enables to serve a customer from such centre, distance of which is less than given value D_{max}. We have made the following transformation of the network, to be able to solve the problem by the exact algorithm for the basic uncapacitated location problem:
• d_{ij} = d_{ij}  pre d_{ij} <= D_{max} a pre iŃI, jŃJ,  (1) 
• d_{ij} = D_{proh}  pre d_{ij} > D_{max} a pre iŃI, jŃJ,  (2) 
where
D
_{proh} . is sufficiently high penalty value,
d
_{ij} …. is the distance between a centre and a customer,
I ..... the set of possible centre locations (e.g. warehouses),
J ….. the set of the customers.
By this transformation we obtained model of the basic uncapacitated location problem, but the distances are deformed:
Minimize
 
 (3)

Subject to

 for jŃJ  (4)

 y_{i}z_{ij}>=0
 for iŃI, jŃJ  (5)

 y_{i}Ń{0, 1}
 for iŃI  (6)

 z_{ij}Ń{0, 1}
 for iŃI, jŃJ  (7)

where the used coefficients have the following meaning:
f_{i} ... fixed charge for considers period for building up center i,
e_{0} ... prime cost for one unit transport along one distance unit on the link between primary source and a centre i,
e_{1} ... prime cost for one unit transport along one distance unit on the link between a centre and customer,
d_{si} .. the distance between the primary source and center i,
d_{ij} .. the distance between a centre and a customer, which was calculated using relations (1)
and (2).
The new quantitative side of the objective function have different time consumption to solve problem by exact algorithm.
3. EXPERIMENSTS
The road network of the Slovak Republic was base of our numerical experiments. This network consists of 2907 nodes and we formed sets of problem instances, which differ in cardinalities of possible location sets. The smallest instance contains 100 possible locations and the biggest one contains 900 possible locations. For each set of instances we have generated ten variants with the same number of possible locations. Approximately same fixed charge was used in each experiment (in order 10^{7}). Coefficient D_{max}, which was enumerated from the input data, took values from 51 to 332. This range was enlarged for the instances with bigger sets of possible locations. It included values from 31 to 342. The range of each given set was divided in ten subranges I_{1}, …, I_{10}. We have solved the associated set of instances for each enumerated value D_{max}. An improved modification of the Erlenkotters algorithm (BBDual) was used for this purpose [1]. We have limited the computational time by 60 minutes. Whenever solving time exceeded this limit, the computation was prematurely stopped. This phenomena is denoted by >60 in the following table. The average computational times for the particular sets of variants are reported in milliseconds. The results are plotted in the following table.
Table 1. The computational times in milliseconds
The values in row denoted I_{11} correspond to computational times of uncapacitated location problem without any limit on the accessibility.
4. CONCLUSIONS
We have awaited that the computational complexity of the studied exact algorithm should increase proportionally to the cardinality of possible location set. When basic uncapacitated location problem was solved, the computational time was very small and of increased almost proportionally to the possible location set cardinality. When the performance of the algorithm is observed on the deformed networks, the much bigger computational time can be noticed. This increase is not regular. We were very surprised that the increase occurred only at lower values of coefficient D_{max} (rows I_{1}, …, I_{4}). Then the rapid decrease of the computational complexity followed. In the second half of D_{max} range, there was computational time comparable to time, which was necessary for solution of the nondeformed problem.
ACKNOWLEDGEMENT
This work has been supported by research project VEGA 1/3375/06.
BIBLIOGRAPHY
[1] ERLENKOTTER, D.: A DualBased Procedure for Uncapacitated Facility Location. Operations Research,Vol. 26, No 6, 1978, 9921009
[2] JANĂÄEK, J., BUZNA L.: A Comparison Continuous Approximation with Mathematical Programming Approach to Location Problems. Central European Journal of Operations Research, Vol. 12, No 3, Sept.2004, 295305
[3] JANĂÄKOVĂ, M., SZENDREYOVĂ, A.: An impact of transportation network topology on time consumption of an exact algorithm for distribution system design. Zeszyty Naukowe, No55, November2005, Wydawnictwo Politechniki ĹlÄ
skiej, pp 175179, PL ISSN 02093324
Marta JANĂÄKOVĂ
Faculty of Machinery Ingeneering, University of Ĺ˝ilina
AlĹžbeta SZENDREYOVĂ
Faculty of Management Science and Informatics, University of Ĺ˝ilina