Volume 4 Issue 1 pp. 127-138 Winter, 2013


Differential evolution algorithm for multi-commodity and multi-level of service hub covering location problem


M. EghbaliZarch M. Abedzadeh and M. Setak




The hub location problem involves a network of origins and destinations over which transportation takes place. There are many studies associated with finding the location of hub nodes and the allocation of demand nodes to these located hub nodes to transfer the only one kind of commodity under one level of service. However, in this study, carrying different commodity types from origin to destination under various levels of services (e.g. price, punctuality, reliability or transit time) is studied. Quality of services experienced by users such as speed, convenience, comfort and security of transportation facilities and services is considered as the level of service. In each system, different kinds of commodities with various levels of services can be transmitted. The appropriate level of service that a commodity can be transmitted through is chosen by customer preferences and the specification of the commodity. So, a mixed integer programming formulation for single allocation hub covering location problem, which is based on the idea of transferring multi commodity flows under multi levels of service is presented. These two are applied concepts, multi-commodity and multi-level of service, which make the model's assumptions closer to the real world problems. In addition, a differential evolution algorithm is designed to find near-optimal solutions. The obtained solutions using differential evolution (DE) algorithm (upper bound), where its parameters are tuned by response surface methodology, are compared with exact solutions and computed lower bounds by linear relaxation technique to prove the efficiency of proposed DE algorithm.




DOI: 10.5267/j.ijiec.2012.10.001

Keywords: Hub covering location, Multi-commodity, Multi-level of service, Differential evolution algorithm, Response surface methodology, Lower and upper bounds

References

References Alumur, SA., & Kara, B.Y. (2008a). Network hub location: the state of art.European Journal of Operational Research, 1, 1-21.

Alumur, S., & Kara, B.Y.(2008b). A hub covering network design problem for cargo applications in Turkey. Journal of the Operational Research Society, 10, 1349-1359.

Box, G.E.P., & Wilson, K.(1951). On the experimental attainment of optimum conditions. Journal of the Royal Statistical Society. Series B (Methodological), 13, 1-45.

Campbell, J.F.(1994). Integer programming formulations of discrete hub location problems.European Journal of Operational Research, 2, 387-405.

Campbell, J.F. (2009). Hub location for time definite transportation. Computers & Operations Research, 36, 3107-3116.

Calik, H., Alumur, SA., Kara, B.Y. & Karasan, O.E.,(2009). A tabu-search based heuristic for the hub covering problem over incomplete hub networks. Computers & Operations Research,12, 3088-3096.

Çetiner, S., Sepil, C., & Süral, H. (2010). Hubbing and routing in postal delivery systems. Annals of Operations Research, 181, 109-124.

Das, S., & Suganthan, P.N. (2010). Differential evolution: A survey of the state-of-the-art. Evolutionary Computation, IEEE Transactions, 99, 1-28.

Ernst, A., Jiang, H. & Krishnamoorthy, M.,(2005). Reformulations and computational results for uncapacitated single and multiple allocation hub covering problems.Unpublished Report, CSIRO Mathematical and Information Science.

Ernst, A.T., & Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science,4, 139-154.

Ernst, A.T., &Krishnamoorthy, M. (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research, 86, 141-159.

Fazel Zarandi, M., Davari, S.& Haddad Sisakht, S. (2012). The Q-coverage multiple allocation hub covering problem with mandatory dispersion. Scientia Iranica

Ghodratnama, A., Tavakkoli-Moghaddam, R., & Azaron, A. (2012). A fuzzy possibilistic bi-objective hub covering problem considering production facilities, time horizons and transporter vehicles. The International Journal of Advanced Manufacturing Technology, 1-20.

Hamacher, H.W., & Meyer, T. (2006). Hub cover and hub center problems. Departament of Mathematics, University of Kaiserslautern, Germany.

Klincewicz, J.G. (1998). Hub location in backbone/tributary network design: a review. Location Science, 6, 307-335.

Kennedy, J., &Eberhart, R.C.(1997). A discrete binary version of the particle swarm algorithm. IEEE TRANSACTION.

Karimi, H., & Bashiri, M. (2011). Hub covering location problems with different coverage types. Scientia Iranica,18, 1571–1578.

Kara, B., & Tansel, B. (2003). The single-assignment hub covering problem: Models and linearizations.Journal of the Operational Research Society, 59-64.

Lobato, F.S., Gedraite,R. & Neiro, S.M.S.,(2012). Solution of flow shop scheduling problems using the differential evolution algorithm.3rd International Conference on Engineering Optimization, Rio de Janeiro, Brazil.

Mohammadi, M., Jolai, F. & Rostami, H. (2011a). An M/M/c queue model for hub covering location problem.Mathematical and Computer Modelling, 54, 2623–2638.

Mohammadi, M., Tavakkoli-Moghaddam, R. & Rostami, H. (2011b) A multi-objective imperialist competitive algorithm for a capacitated hub covering location problem. International Journal of Industrial Engineering Computations. 2, 671-688.

Mohammadi, M., Tolui, H. & Yousefi, M. (2010). Solving a hub covering location problem under capacity constraints by a hybrid algorithm. Journal of Applied Operational Research, 2, 109-116.

O'kelly, M.E. (1987). A quadratic integer program for the location of interacting hub facilities.European Journal of Operational Research, 3, 393-404.

Rao, R.V. & Patel, V.,(2012). An elitist teaching learning based optimization algorithm for solving complex constrained optimization problems.International Journal of Industrial Engineering Computations, 3, 535-560.

Rao, R.V. & Patel,V. (2013) Comparative performance of an elitist teaching-learning-based optimization algorithm for solving unconstrained optimization problems. International Journal of Industrial Engineering Computations.

Sim, T.K.T. (2007). The hub covering flow problem and the stochastic p-hub center problem. United states: ProQuest Information and Learning Company.

Tan, P.Z., Kara, B.Y. (2007). A hub covering model for cargo delivery systems. Networks, 1, 28-39.

Wagner, B.,(2004) Model formulations for hub covering problems. Journal of the Operational Research Society, 7, 932-938.

Storn, R., &Price, K., (1996). Minimizing the real functions of the ICEC'96 contest by differential evolution. IEEE Transaction.

Sahraeian, R., & Korani, E. (2010). The hierarchical hub maximal covering problem with determinate cover radiuses. IEEE Transaction.

Vijay Chakaravarthy, G., Marimuthu, S., & Naveen Sait, A. (2011). Performance evaluation of proposed Differential Evolution and Particle Swarm Optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Intelligent Manufacturing, 1-17.