Static and sequential location-allocation problems on networks and areas with probabilistic demands

Location-allocation problems arise in many practical settings and may be generically stated as follows: Given the location or distribution of a set of customers and their associated demands, simultaneously determine an optimal location of a number of supply facilities and their allocation of products or services to the customers, so as to minimize total location and transportation costs. This study is concerned with the development, convergence analysis, and testing of exact and heuristic algorithms for location-allocation problems in which demands can occur continuously over regions according to some probability density functions. In this context, minisum location problems on undirected networks are considered in which demands can occur on links with uniform probability distributions. Three types of networks are considered. The first type is a chain graph. It is shown that except for the 1-median case, the problem is generally nonconvex. However, for the p-median case, it is shown that all local and global trd.nima to the problem may be discovered by solving a series of linear programming problems. This analysis forms the basis for similar problems on trees and graphs with isolated cycles. These problems are then extended to multiperiod versions in which demands may change dynamically over time periods and at mostly one facility can be located per time period. Chain and tree graphs are considered in conjunction with three optimization strategies: myopic, long-range, and discounted present worth. It is hoped that the exact methods developed for these special networks will lead to at least effective heuristics for problems on more general networks. Finally, location-allocation problems are considered in which the region to be served is a convex polygon having a uniform demand distribution. Both single and multifacility formulations are considered. For the single facility problem, an algorithm is developed which is shown to converge to a global optimal solution. This analysis is extended to the nonconvex multifacility case, and although optimality is not guaranteed, an algorithm is presented for finding a good starting solution which increases the likelihood of finding an optimal solution. Extensions of the above problems to include discrete demand points and computational experience are also provided.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Industrial Engineering and Operations Research

Department dc:contributor.department

Industrial Engineering and Operations Research

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1983

Author dc:creator

• Cavalier, Tom Michael

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/10919/106316

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/106316