Supply connected location-allocation problem

Abstract

<p>This study introduces a new model for a location distribution system, which is called the Supply Connected Location Allocation Problem (SCLAP). The problem involves locating p facilities with respect to n demand points and a supply plant. The supply plant originates all material in the system and distributes it to facilities along a route to be determined. Facilities then distribute the material to demand points via direct shipments. The problem minimizes the cost of shipping material from supply plant to all demand points via facilities. A description of the model is given and its subproblems are discussed in relation to well-known models in the literature. The problem is then investigated in three avenues: First, some special cases on which the problem is efficiently solvable are identified. For this, simple structured networks (e.g. a line and a tree) are considered. A dynamic programming solution procedure with polynomial time complexity is developed for the case on a line and it is extended to a special case of tree networks. Second, the problem is considered on general networks and a single assignment branch-and-bound algorithm is proposed to solve it. The algorithm is tested on randomly generated networks for relatively small sizes of problem instances. Discussions on the computational results are given with respect to computation time and the size of the branch and bound tree. Next, local search type heuristics are discussed briefly and two heuristic approaches are developed. Two versions of algorithms are constructed for each of those heuristics and they are tested on randomly generated networks, with respect to computation time and closeness to optimality (when optimal solutions were available) or to closeness to the best solution found. Finally, the study is concluded with recommendations for future research.</p>