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

 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 algorithmMarta 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 (3) Subject to 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 . 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 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
 ERLENKOTTER, D.: A Dual-Based Procedure for Uncapacitated Facility Location. Operations Research,Vol. 26, No 6, 1978, 992-1009
 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
 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   