No label defined (Q3313580)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3843458
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3843458

      Statements

      0 references
      1983
      0 references
      logistics
      0 references
      location on a tree
      0 references
      minimization of maximum transportation cost
      0 references
      discrete location problems
      0 references
      budget constraint
      0 references
      chordal graph
      0 references
      strong duality results
      0 references
      p-center problem
      0 references
      series of set covering problems
      0 references
      polynomial time algorithm
      0 references
      In this paper two discrete location problems are discussed. It is assumed that clients are located at the vertices of a tree network. Facilities have to be established on the tree in order to supply the clients. There is a budget constraint on the total setup cost associated with the facilities. Furthermore it is assumed that the transportation cost between client and facility is a continuous nondecreasing function of their distance. For ease of exposition a linear function has been chosen. The problems considered are to find locations of the facilities such that the budget constraint is statisfied and so as to minimize the maximum transportation cost. In the first problem it is assumed that facilities can be located anywhere on the tree and all setup costs are equal. In this case the budget constraint reduces to an upper bound, say p, on the number of facilities. It is shown how the concept of a chordal graph can be used to derive strong duality results for this so called p-center problem. In the second problem it is assumed that facilities can be located at a finite set of points, say the vertices, of the tree and that setup costs may differ. It is shown that this problem can be solved as a series of set covering problems on a (0,1)-matrix in standard greedy form for which a polynomial time algorithm is given.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references