Theoretical and computational analysis of the two-stage capacitated plant location problem : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Decision Science at Massey University, Palmerston North, New Zealand

Wildbore, Bronwyn Louise

Theoretical and computational analysis of the two-stage capacitated plant location problem : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Decision Science at Massey University, Palmerston North, New Zealand

dc.contributor.author	Wildbore, Bronwyn Louise
dc.date.accessioned	2008-06-08T22:13:55Z
dc.date.available	NO_RESTRICTION	en_US
dc.date.available	2008-06-08T22:13:55Z
dc.date.issued	2008
dc.description.abstract	Mathematical models for plant location problems form an important class of integer and mixed-integer linear programs. The Two-Stage Capacitated Plant Location Problem (TSCPLP), the subject of this thesis, consists of a three level structure: in the first or upper-most level are the production plants, the second or central level contains the distribution depots, and the third level is the customers. The decisions to be made are: the subset of plants and depots to open; the assignment of customers to open depots, and therefore open plants; and the flow of product from the plants to the depots, to satisfy the customers' service or demand requirements at minimum cost. The formulation proposed for the TSCPLP is unique from previous models in the literature because customers can be served from multiple open depots (and plants) and the capacity of both the set of plants and the set of depots is restricted. Surrogate constraints are added to strengthen the bounds from relaxations of the problem. The need for more understanding of the strength of the bounds generated by this procedure for the TSCPLP is evident in the literature. Lagrangian relaxations are chosen based more on ease of solution than the knowledge that a strong bound will result. Lagrangian relaxation has been applied in heuristics and also inserted into branch-and-bound algorithms, providing stronger bounds than traditional linear programming relaxations. The current investigation provides a theoretical and computational analysis of Lagrangian relaxation bounds for the TSCPLP directly. Results are computed through a Lagrangian heuristic and CPLEX. The test problems for the computational analysis cover a range of problem size and strength of capacity constraints. This is achieved by scaling the ratio of total depot capacity to customer demand and the ratio of total plant capacity to total depot capacity on subsets of problem instances. The analysis shows that there are several constraints in the formulation that if dualized in a Lagrangian relaxation provide strong bounds on the optimal solution to the TSCPLP. This research has applications in solution techniques for the TSCPLP and can be extended to some transformations of the TSCPLP. These include the single-source TSCPLP, and the multi-commodity TSCPLP which accommodates for multiple products or services.	en_US
dc.identifier.uri	http://hdl.handle.net/10179/660
dc.language.iso	en	en_US
dc.publisher	Massey University	en_US
dc.rights	The Author	en_US
dc.subject	Decision-making	en_US
dc.subject	Mathematical models	en_US
dc.subject	Lagrangian relaxation bounds	en_US
dc.subject	Linear programming	en_US
dc.subject	Theoretical analysis	en_US
dc.subject	Computational analysis	en_US
dc.subject.other	Fields of Research::230000 Mathematical Sciences::230100 Mathematics::230118 Optimisation	en_US
dc.title	Theoretical and computational analysis of the two-stage capacitated plant location problem : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Decision Science at Massey University, Palmerston North, New Zealand	en_US
dc.type	Thesis	en_US
massey.contributor.author	Wildbore, Bronwyn Louise
thesis.degree.discipline	Decision Science	en_US
thesis.degree.grantor	Massey University	en_US
thesis.degree.level	Doctoral	en_US
thesis.degree.name	Doctor of Philosophy (Ph.D.)	en_US