"Najlepszą metodą przewidywania przyszłości jest jej tworzenie" - Peter Drucker   

Główne Menu


Strona Główna


PSTT
· O Stowarzyszeniu
· Wydarzenia
· Statut


Redakcja wortalu
· O Nas
· Kontakt

Artykuły
· Telematics
· Transport

Inne
· Słownik telematyczny
· Konferencje
· Polecamy
· Do pobrania
· FAQ

Partnerstwo


Szukaj


Artykuły :: Transport :: Conference papers

An impact of set of centers of distribution system design problem on computational time of solving algorithm
Marta JANÁČKOVÁ, Alžbeta SZENDREYOVÁ
2007-06-06 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 Dmax. 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:

dij = dij pre dij <= Dmax a pre iєI, jєJ,
(1)
dij = Dproh pre dij > Dmax a pre iєI, jєJ,(2)

where
Dproh . is sufficiently high penalty value,
dij …. 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
wzor1
(3)
Subject to
wzor2
for jєJ(4)
yi-zij>=0
for iєI, jєJ(5)
yiє{0, 1}
for iєI(6)
zijє{0, 1}
for iєI, jєJ(7)

where the used coefficients have the following meaning:
fi ... fixed charge for considers period for building up center i,
e0 ... prime cost for one unit transport along one distance unit on the link between primary source and a centre i,
e1 ... prime cost for one unit transport along one distance unit on the link between a centre and customer,
dsi .. the distance between the primary source and center i,
dij .. 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 107). Coefficient Dmax, 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 I1, …, I10. We have solved the associated set of instances for each enumerated value Dmax. 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 computational times in milliseconds

The values in row denoted I11 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 Dmax (rows I1, …, I4). Then the rapid decrease of the computational complexity followed. In the second half of Dmax range, there was computational time comparable to time, which was necessary for solution of the non-deformed problem.

 

ACKNOWLEDGEMENT
This work has been supported by research project VEGA 1/3375/06.


BIBLIOGRAPHY
[1] ERLENKOTTER, D.: A Dual-Based Procedure for Uncapacitated Facility Location. Operations Research,Vol. 26, No 6, 1978, 992-1009
[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, 295-305
[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 175-179, PL ISSN 0209-3324

Marta JANÁČKOVÁ
Faculty of Machinery Ingeneering, University of Žilina
AlŞbeta SZENDREYOVÁ
Faculty of Management Science and Informatics, University of Žilina

Logowanie

Użytkownik

Hasło


Załóż konto

Zapomniałem hasła

Nowe artykuły


Ankieta




Ogółem głosów: 0

Wyniki poprzednich ankiet


©NET-DESIGN 2007