"The best way to predict the future is to create it." - Peter Drucker   

Main menu

Return to Main Page

· About Association
· Events
· Statute of Association

Editorial staff
· About us
· Contact

· Transport

· Telematics dictionary
· Events
· Links
· Download



Artykuły :: Transport :: Conference papers

An impact of set of centers of distribution system design problem on computational time of solving algorithm
2007-06-06 12:05:56

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.

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,
dij = Dproh pre dij > Dmax a pre iєI, jєJ,(2)

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:
Subject to
for jєJ(4)
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.

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.

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.


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

[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

Faculty of Machinery Ingeneering, University of Žilina
Faculty of Management Science and Informatics, University of Žilina

Log In



Sign Up

Forgot password

New articles