The stochastic location-assignment problem on a tree

The stochastic location-assignment problem on a tree

0.00 Avg rating0 Votes
Article ID: iaor20052972
Country: Netherlands
Volume: 136
Issue: 1
Start Page Number: 81
End Page Number: 97
Publication Date: Apr 2005
Journal: Annals of Operations Research
Authors: ,
Keywords: networks, programming: assignment
Abstract:

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.

Reviews

Required fields are marked *. Your email address will not be published.