Facility Location Decisions Based on Driving Distances on Spherical Surface

Han Shih

University of Missouri, Columbia, USA.

DOI: 10.4236/ajor.2015.55037                

Abstract

Facility location problems are concerned with the location of one or more facilities in a way that optimizes a certain objective such as minimizing transportation cost, providing equitable service to customers, capturing the largest market share, etc. Many facility location decisions involving distance objective functions on Spherical Surface have been approached using algorithmic, metaheuristic algorithms, branch-and-bound algorithm, approximation algorithms, simulation, heuristic techniques, and decomposition method. These approaches are most based on Euclidean distance or Great circle distance functions. However, if the location points are widely separated, the difference between driving distance, Euclidean distance and Great circle distance may be significant and this may lead to significant variations in the locations of the corresponding optimal source points. This paper presents a framework and algorithm to use driving distances on spherical surface and explores its use as a facility location decision tool and helps companies assess the optimal locations of facilities.

Keywords

Facility Location, Spherical Surface, Euclidean Distance, Great Circle Distance, Clustering, Heuristic Method

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Reid, R.D. and Sanders, N.R. (2013) Operations Management. 5th Edition, John Wiley & Sons, Hoboken.
[2]	Wikipedia (2014) Facility Location Problem. http://en.wikipedia.org/wiki/Facility_location_problem
[3]	Brimberg, J., Hansen, P., Mladenovic, N. and Salhi, S. (2008) A Survey of Solution Methods for the Continuous Location-Allocation Problem. International Journal of Operations Research, 5, 1-12.
[4]	Tcha, D.W. and Lee, B.I. (1984) A Branch-and-Bound Algorithm for the Multi-Level Uncapacitated Facility Location Problem. European Journal of Operational Research, 18, 35-43. http://dx.doi.org/10.1016/0377-2217(84)90258-3
[5]	Francis, R.L. and White J.A. (1974) Facility Layout and Location: An Analytical Approach. Prentice-Hall, Inc., Englewood Cliffs.
[6]	Love, R.F., James, J., Morris, G. and Wesolowsky, G.O. (1988) Facilities Location: Models & Methods. North-Holland Publishing Co., New York.
[7]	Farahani, R.Z. and Masoud, H. (2009) Facility Location: Concepts, Models, Algorithm and Case Studies, Springer-Verlag Berlin Heidelberg, Germany. http://dx.doi.org/10.1007/978-3-7908-2151-2
[8]	Vygen, J. (2004-2005) Approximation Algorithms for Facility Location Problems (Lecture Notes). Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany.
[9]	Shmoys, D.B., Tardos, E. and Aardal, K. (1998) Approximation Algorithms for Facility Location Problems (Extended Abstract). Proceedings of the 29th Annual ACM Symposium on Theory of Computing, El Paso, 4-6 May 1997, 1-21.
[10]	Iyigun, C. and Ben-Israel, A. (2010) A Generalized Weiszfeld Method for the Multi-Facility Location Problem. Operations Research Letters, 38, 207-214. http://dx.doi.org/10.1016/j.orl.2009.11.005
[11]	Ballou, R.H. (2004) Business Logistics/Supply Chain Management: Planning, Organizing and Controlling the Supply chain. 5th Edition, Pearson/Prentice Hall Inc., New Jersey.
[12]	Katz, I.N. and Cooper, L. (1980) Optimal Location on a Sphere. Computers & Mathematics with Applications, 6, 175-196. http://dx.doi.org/10.1016/0898-1221(80)90027-9
[13]	Drezner, Z. and Wesolowsky, G.O. (1978) Facility Location on a Sphere. Journal of the Operational Research Society, 29, 997-1004. http://dx.doi.org/10.1057/jors.1978.213
[14]	Xue, G.L. (1994) A Globally Convergent Algorithm for Facility Location on a Sphere. Computers & Mathematics with Applications, 27, 37-50. http://dx.doi.org/10.1016/0898-1221(94)90109-0
[15]	Mwemezi, J. and Huang, Y. (2011) Optimal Facility Location on Spherical Surfaces: Algorithm and Application. New York Science Journal, 4, 21-28.
[16]	Sullivan, E. and Peters, N. (1980) A Flexible User-Oriented Location-Allocation Algorithm. Journal of Environmental Management, 10, 181-193.
[17]	Bespamyatnikh, S., Kedem, K., Segal M. and Tamir A. (2000) Optimal Facility Location under Various Distance Functions. International Journal of Computational Geometry & Applications, 10, 523-534. http://dx.doi.org/10.1142/S0218195900000292
[18]	Levin, Y. and Ben-Israel, A. (2004) A Heuristic Method for Large Scale Multifacility Location Problems. Computers & Operations Research, 31, 257-272. http://dx.doi.org/10.1016/S0305-0548(02)00191-0
[19]	Levin, Y. and Ben-Israel, A. (2002) The Newton Bracketing Method for Convex Minimization. Computational Optimization and Applications, 21, 213-229. http://dx.doi.org/10.1023/A:1013768901780
[20]	Rodríguez-Chía, A.M. and Valero-Franco, C. (2013) On the Global Convergence of a Generalized Iterative Procedure for the Minisum Location Problem with ?p Distances for p > 2. Springer and Mathematical Optimization Society, Mathematical Programming, Series A, 137, 477-502.
[21]	Kotian, S.R., Bonilla, C. and Hale, T.S. (2008) The Planar k-Central Location Problem. The Open Industrial and Manufacturing Engineering Journal, 1, 42-49. http://dx.doi.org/10.2174/1874152500801010042
[22]	SAS Inc. (2014). http://support.sas.com/documentation/cdl/en/lefunctionsref/67398/HTML/default/ viewer.htm#n1korpfg2e18lon1nwpow9qijdxe.htm
[23]	Ksu. http://www.math.ksu.edu/~dbski/writings/haversine.pdf
[24]	The Math Forum. (1994-2013). http://mathforum.org/library/drmath/view/51756.html
[25]	Google Inc. (2014). https://www.google.com/maps/dir/
[26]	Wikipedia (2014). http://en.wikipedia.org/wiki/Euclidean_distance
[27]	Wiktionary (2014). http://en.wiktionary.org/wiki/Euclidean_distance
[28]	Wikipedia (2014). http://en.wikipedia.org/wiki/Great-circle_distance
[29]	Movable Type Ltd. (2014). http://www.movable-type.co.uk/scripts/latlong.html
[30]	Weiszfeld, E. (1937) Sur le point par lequel la somme des distances de n points donnVes est minimum. Tohoku Mathematical Journal, 43, 355-386.
[31]	Aykin, T. (1984) Some Aspects in the Large Region Location Problems on the Surface of the Earth. PhD Thesis, State University of New York at Buffalo.
[32]	SAS Inc. (2014). http://support.sas.com/documentation/cdl/en/statug/63033/ HTML/default/viewer.htm#modeclus_toc.htm
[33]	Heizer, J. and Render, B. (2011) Principles of Operations Management. 8th Edition, Prentice Hall, Upper Saddle River.
[34]	Pearson (2014). http://www.prenhall.com/divisions/bp/app/russellcd/PROTECT/CHAPTERS/CHAP09/HEAD06.HTM
[35]	Geomidpoint (2014). http://www.geomidpoint.com/calculation.html
[36]	Chen, Z.X. and He, W. (2010) Study and Application of Center-of-Gravity on the Location Selection of Distribution Center, Logistics Systems and Intelligent Management. International Conference on Logistics Systems and Intelligent Management, Harbin, 9-10 January 2010, 981-984.
[37]	Kuo, C.C., Richard, E. and White, R.E. (2004) A Note on the Treatment of the Center-of-Gravity Method in Operations Management Textbooks. Decision Sciences Journal of Innovative Education, 2, 219-227.
[38]	Chase, R.B., Aquilando, N.J. and Jacobs, F.R. (2006) Operations Management for Competitive Advantage. 11th Edition, McGraw-Hill/Irwin, New York.
[39]	Ligas, M. and Banasik, P. (2011) Conversion between Cartesian and Geodetic Coordinates on a Rotational Ellipsoid by Solving a System of Nonlinear Equations. Geodesy and Cartography, 60, 145-159. http://dx.doi.org/10.2478/v10277-012-0013-x
[40]	ThinkGeo LLC. (2014). http://thinkgeo.com/map-suite-developer-gis/desktop-edition/
[41]	Natural Earth (2014). http://www.naturalearthdata.com/downloads/
[42]	Hillier, F.S. and Lieberman, G.J. (2009) Introduction to Operations Research. 9th Edition, McGraw-Hill Higher Education, New York.
[43]	Litwhiler Jr., D.W. and Aly, A.A. (1979) Large Region Location PROBLEMS. Computer & Operations Research, 6, 1-12. http://dx.doi.org/10.1016/0305-0548(79)90009-1