A New Robust Mathematical Model for the Multi-product Capacitated Single Allocation Hub Location Problem with Maximum Covering Radius

Document Type : Research Paper

Authors

Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran

Abstract

This paper presents a new robust mathematical model for the multi-product capacitated single allocation hub location problem with maximum covering radius. The objective function of the proposed model minimizes the cost of establishing hubs, the expected cost of preparing hubs for handling products, shipping and transportation in all scenarios, and the cost variations over different scenarios. In the proposed model, a single product of a single node cannot be allocated to more than one hub, but different products of one node can be allocated to different hubs. Also, a product can be allocated to a hub only if equipment related to that product is installed on that hub. Considering the NP-Hard complexity of this problem, a GA-based meta-heuristic algorithm is developed to solve the large scale variants of the problem. To evaluate the performance of the proposed algorithm, its results are compared with the results of exact method and simulated annealing algorithm. These results show the good performance of the proposed algorithm.

Keywords

Main Subjects

References

Alinaghian, M., Ghazanfari, M., Salamatbakhsh, A. and Norouzi, N. (2012). A new competitive approach on multi-objective periodic vehicle routing problem. Int J Appl Oper Res, Vol.1, pp. 33-41.
Alumar, S., Kara, B.Y., (2008) “Network hub location problems: The state of the art”, European Journal of Operational Research, Vol. 190, pp. 1 –21.
Alumur, S. A., Nickel, S. and Saldanha-da-Gama, F. (2012). Hub location under uncertainty. Transportation Research Part B, Vol. 46(4), pp. 529–543.
Aykin, T. (1995a). Networking policies for hub-and-spoke systems with application to the air transportation system. Transportation Science, Vol. 29(3), pp. 201–221.
Beheshti, A. K., Hejazi, S. R., and Alinaghian, M. (2015). The vehicle routing problem with multiple prioritized time windows: A case study. Computers & Industrial Engineering, Vol. 90, pp. 402-413.
Ben-Tal, A.Nemirovski (2000), Robust solutions of Linear Programming problems contaminated with uncertain data, Mathematical Programming, Volume 88(3), pp. 411-424.
Ben-Tal, A.Nemirovski (1998), Robust Convex Optimization, Mathematics of Operations Research, pp. 769 – 805.
Berman, O., Drezner, Z. and Wesolowsky, G. O. (2007). The transfer point location problem. European Journal of Operational Research, Vol. 179(3), pp. 978–989.
Bertsimas, D., Sim, M., (2004). The price of robustness. Operat. Res. Vol. 52 (1), pp. 35–53.
Boland, N., Krishnamoorthy, M., Ernst, A.T., Ebery, J., (2004) “Preprocessing and cutting for multiple allocation hub location problems”, European Journal of Operational Research, Vol. 155, pp. 638–653.
Boukani, F. H., Moghaddam, B. F., and Pishvaee, M. S. (2016). Robust optimization approach to capacitated single and multiple allocation hub location problems. Computational and Applied Mathematics, Vol. 35(1), pp. 45-60.
Canovas, L., García, S. and Marín, A. (2007). Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique. European Journal of Operational Research, Vol. 179, pp. 990–1007.
Chou, C. C. (2010). Application of FMCDM model to selecting the hub location in the marine transportation: A case study in southeastern Asia. Mathematical and Computer Modelling, Vol. 51, pp. 791–801.
Contreras, I., Cordeau, J. F. and Laporte, G. (2011a). Stochastic uncapacitated hub location. European Journal of Operational Research, Vol. 212, pp. 518–528.
Contreras, I., Cordeau, J. F. and Laporte, G. (2011c). Benders decomposition for largescale uncapacitated hub location. Operations Research, Vol. 59(6), pp. 1477–1490.
Costa, M. G., Captivo, M. E. and Climaco, J. (2008). Capacitated single allocation hub location problem – A bi-criteria approach. Computers and Operations Research, Vol. 35(11), pp. 3671–3695.
Cunha, C. B., and Silva, M. R. (2007). A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. European Journal of Operational Research, Vol. 179, pp. 747–758.
De Sá, E. M., Morabito, R. and de Camargo, R. S. (2018). Benders decomposition applied to a robust multiple allocation incomplete hub location problem. Computers & Operations Research, Vol. 89, 31-50.
Ebery, J., Krishnamoorthy, M., Ernst, A., Boland, N., (2000) “The capacitated multiple allocation hub location problem: Formulations and algorithms”, European Journal of Operational Research, Vol. 120, pp. 614–631.
Ernst, A. T., and Krishnamoorthy, M. (1998). Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. European Journal of Operational Research, Vol. 104, pp. 100–112.
Ernst, A., Jiang, H. and, Krishnamoorthy, M. (2005). Reformulation and computational results for uncapacitated single and multiple allocation hub covering problem. Unpublished Report, CSIRO Mathematical and Information Sciences, Australia.
Gavish, B., and Suh, M. (1992). Configuration of fully replicated distributed database system over wide area networks. Annals of Operations Research, Vol. 36(1), pp. 167–191.
Ghaderi, Abdolsalam, and Ragheb Rahmaniani. (2015) "Meta-heuristic solution approaches for robust single allocation p-hub median problem with stochastic demands and travel times." The International Journal of Advanced Manufacturing Technology, pp. 1-21.
Ghaffari–Nasab, N., Ghazanfari, M., Saboury, A. and Fathollah, M. (2015). The single allocation hub location problem: a robust optimisation approach. European Journal of Industrial Engineering, Vol. 9(2), pp. 147-170.
Ghodratnama, A., Tavakkoli-Moghaddam, R., and Azaron, A. (2015). Robust and fuzzy goal programming optimization approaches for a novel multi-objective hub location-allocation problem: A supply chain overview. Applied Soft Computing, Vol. 37, pp. 255-276.
Hamacher, H. W., Labbé, M., Nickel, S., and Sonneborn, T. (2004). Adapting polyhedral properties from facility to hub location problems. Discrete Applied Mathematics, Vol. 145(1), pp. 104–116.
Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
I.Correia, S.Nickel ·F.Saldanha, (2014),” Multi-product Capacitated Single-Allocation Hub Location Problems: Formulations and Inequalities”, Springer Science, Vol. 14, pp. 1–25.
Jolai, F., Amalnick, M. S., Alinaghian, M., Shakhsi-Niaei, M. and Omrani, H. (2011). A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines. Journal of Intelligent Manufacturing, Vol. 22(2), pp. 247-261.
Kara, B. Y., and Tansel, B. C. (2000). On the single assignment p-hub center problem. European Journal of Operational Research, Vol. 125(3), pp. 648–655.
Kara, B., and Tansel, B. (2003). The Single-Assignment Hub Covering Problem: Models and Linearizations. The Journal of the Operational Research Society, Vol. 54(1), pp. 59-64.
Khalilpourazari, S., Pasandideh, S. H. R., & Niaki, S. T. A. (2016). Optimization of multi-product economic production quantity model with partial backordering and physical constraints: SQP, SFS, SA, and WCA. Applied Soft Computing, 49, 770-791.
Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. Journal of statistical physics, Vol. 34(5-6), pp. 975-986.
Labbe´,M.,Yaman,H.,Gourdin,E., (2005) “A branch and cut algorithm for the hub location problems with single   assignment”, Mathematical Programming, Vol. 102, pp. 371–405.
Madani, S.R., Nookabadi, A.S., Hejazi, S.R. (2017). reliable single allocation p-hub maximal covering location problem: Mathematical formulation and solution approach. Journal of Air Transport Management.
Meraklı, Merve, and Hande Yaman. (2016), "Robust intermodal hub location under polyhedral demand uncertainty."  Transportation Research Part B: Methodological, Vol. 86, pp. 66-85.
Meraklı, M., and Yaman, H. (2017). A capacitated hub location problem under hose demand uncertainty. Computers & Operations Research, Vol. 88, pp. 58-70.
Monma, C.L., Sheng, D.D., (1986). Backbone network design and performance analysis: A methodology for packet switching networks. IEEE Journals on Selected Areas in Communications SAC-4, pp. 946–965.
Mulvey, J. M., and Vanderbei, R. J. (1995). Robust optimization of large scale systems. Operations Research, Vol. 43(2), pp. 264–281.
O'kelly, M.E., (1987) “A quadratic integer program for the location of interacting hub facilities”, European Journal of Operational Research, No. 32, pp. 393- 404.
Pourghaderi, A. R., Tavakkoli-Moghaddam, R., Alinaghian, M. and Beheshti-Pour, B. (2008, December). A simple and effective heuristic for periodic vehicle routing problem. In Industrial Engineering and Engineering Management, 2008. IEEM 2008. IEEE International Conference on (pp. 133-137). IEEE.
Snyder, L.V., (2006). Facility location under uncertainty: a review. IIE Trans. Vol. 38, pp. 537–554.
T. Assavapokee, M.J. Realff, J.C. Ammons. (2008). Scenario relaxation algorithm for finite scenario-based min–max regret and min–max relative regret robust optimization. Computers & Operations Research, Vol. 35, pp. 2093–2102.
 
Wagner, B. (2008). Model formulation for hub covering problems. Journal of the Operational Research Society, pp. 932- 938.
Yu CS, Li HL (2000) A robust optimization model for stochastic logistic problems. Int J Prod Econ, Vol. 64(1–3), pp. 385–397.
International Journal of Supply and Operations Management
Volume 4, Issue 3 - Serial Number 3
August 2017
Pages 248-262

Files

Share

How to cite

Statistics