Research Article Open Access

Comparison of Exact Algorithms for Rectilinear Distance Single-Source Capacitated Multi-Facility Weber Problems

Chansiri Singhtaun1 and Peerayuth Charnsethikul1
  • 1 ,
Journal of Computer Science
Volume 6 No. 2, 2010, 112-116

DOI: https://doi.org/10.3844/jcssp.2010.112.116

Submitted On: 25 December 2009 Published On: 28 February 2010

How to Cite: Singhtaun, C. & Charnsethikul, P. (2010). Comparison of Exact Algorithms for Rectilinear Distance Single-Source Capacitated Multi-Facility Weber Problems. Journal of Computer Science, 6(2), 112-116. https://doi.org/10.3844/jcssp.2010.112.116

Abstract

Problem statement: The objective of this study is to develop efficient exact algorithms for a single source capacitated multi-facility location problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the two dimensional plane to satisfy the demand of n customers with minimum total transportation cost which is proportional to the rectilinear distance between the facilities and their customers. Approach: Two exact algorithms are proposed and compared. The first algorithm, decomposition algorithm, uses explicit branching on the allocation variables and then solve for location variable corresponding to each branch as the original Mixed Integer Programming (MIP) formulation with nonlinear objective function of the problem. For the other algorithm, the new formulation of the problem is first created by making use of a well-known condition for the optimal facility locations. The problem is considered as a p-median problem and the original formulation is transformed to a binary integer programming problem. The classical exact algorithm based on this formulation which is branch-and-bound algorithm (implicit branching) is then used. Results: Computational results show that decomposition algorithm can provide the optimum solution for larger size of the studied problem with much less processing time than the implicit branching on the discrete reformulated problem. Conclusion: The decomposition algorithm has a higher efficiency to deal with the studied NP-hard problems but is required to have efficient MIP software to support.

  • 1,243 Views
  • 1,745 Downloads
  • 1 Citations

Download

Keywords

  • Location-allocation problem
  • decomposition algorithms
  • mixed integer programming