An efficient genetic algorithm for the uncapacitated multiple allocation p-hub median problem

• Autorzy: Stanimirovic Z.
• Języki publikacji: EN

Abstrakty

EN

In this paper the Uncapacitated Multiple Allocation p-hub Median Problem (the UMApHMP) is considered. A new heuristic method based on a genetic algorithm approach (GA) for solving UMApHMP is proposed. The described GA uses binary representation of the solutions. Genetic operators which keep the feasibility of individuals in the population are designed and implemented. The mutation operator with frozen bits is used to increase the diversibility of the genetic material. The running time of the GA is improved by caching technique. Proposed GA approach is bench-marked on the well known CAB and AP data sets and compared with the existing methods for solving the UMApHMP. Computational results show that the GA quickly reaches all previously known optimal solutions, and also gives results on large scale AP instances (up to n=200, p=20) that were not considered in the literature so far.

Słowa kluczowe

EN

p-hub problem; genetic algorithms; discrete location and assignment

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2008
• Tom: Vol. 37, no 3
• Strony: 669--692
• Opis fizyczny: Bibliogr. 63 poz.

Twórcy

autor

Stanimirovic Z.

• Faculty of Mathematics, University of Belgrade Studentski trg 16/IV, 11 000 Belgrade, Serbia,

Bibliografia

• ABADINOUR-HELM, S. (1998) A Hybrid Heuristic for the Uncapacitated Hub Location Problem. European Journal of Operational Research 106, 489-499.
• ABADINOUR-HELM, S. (2001) Using simulated annealing to solve the p-hub median problem. International Journal of Physical Distribution and Logistics Management 31 (3), 203-220.
• ABADINOUR-HELM, S. and VENKATARAMANAN, M.A. (1998) Solution Approaches to Hub Location Problems. Annals of Operations Research 78, 31-50.
• AHUJA, R., MAGNANTI, T. and ORLIN, J. (1993) Network Flows: Theory, Algorithms and Applications. Prentice-Hall, New York.
• ALUMUR, S. and KARA, B.Y. (2008) Network hub location problems: The state of the art. European Journal of Operational Research 190 (1), 1-21.
• AYKIN, T. (1995) Networking Policies for Hub-and-spoke Systems with Application to the Air Transportation System. Transportation Science 29, 201-221.
• BÄCK, T., FOGEL, D.B. and MICHALEWICZ, Z. (2000) Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol-Philadelphia.
• BÄCK, T., FOGEL, D.B. and MICHALEWICZ, Z. (2000) Evolutionary Computation 2: Advanced Algorithms and Operators, Institute of Physics Publishing, Bristol-Philadelphia.
• BEASLEY, J.E. (1996) Obtaining Test Problems via Internet. Journal of Global Optimization 8, 429-433. http://mscmga.ms.ic.ac.uk/jeb/orlib/info.html
• BOLAND, N., KRISHNAMOORTHY, M., ERNST, A.T. and EBERY, J. (2004) Preprocessing and Cutting for Multiple Allocation Hub Location Problems. European Journal of Operational Research 155, 638-653.
• BRYAN, D.L. (1998) Extensions to the hub location problem: Formulations and numerical examples. Geographical Analysis 30, 315-330.
• BRYAN, D.L. and O’KELLY, M.E. (1999) Hub-and-spoke networks in air transportation: An analytical review. Journal of Regional Science 39, 275-295.
• CAMPBELL, J.F. (1992) Location and allocation for distribution systems with transshipments and transportation economies of scale. Annals of Operations Research 40, 77-99.
• CAMPBELL, J.F. (1994) Integer programming formulations of discrete hub location problems. European Journal of Operational Research 72, 387-405.
• CAMPBELL, J.F. (1996) Hub Location and the p-hub Median Problem. Operations Research 44 (6), 923-935.
• CAMPBELL, J.F., ERNST, A. and KRISHNAMOORTHY, M. (2002) Hub Location Problems. In: H. Hamacher and Z. Drezner, eds., Location Theory: Applications and Theory. Springer-Verlag, Berlin-Heidelberg, 373-407.
• CAMPBELL, J.F., STIEHR, G., ERNST, A.T. and KRISHNAMOORTHY, M. (2003) Solving hub arc location problems on a cluster of workstations. Parallel Computing 29, 555-574.
• CAMPBELL, J.F., ERNST, A. and KRISHNAMOORTHY, M. (2005a) Hub Arc Location Problems: Part I - Introduction and Results. Management Science 51, 1540-1555.
• CAMPBELL, J.F., ERNST, A. and KRISHNAMOORTHY, M. (2005b) Hub Arc Location Problems: Part II - Formulations and Optimal Algorithms. Management Science 51, 1556-1571.
• EBERY, J. (2001) Solving large single allocation p-hub problems with two or three hubs. European Journal of Operational Research 128 (2), 447-458.
• ELHEDHLI, S. and HU, F.X. (2005) Hub-and-spoke network design with congestion. Computers and Operations Research 32, 1615-1632.
• ERNST A.T. and KRISHNAMOORTHY, M. (1996) Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science 4 (3), 139-154.
• ERNST A.T. and KRISHNAMOORTHY, M. (1998a) Exact and Heuristic Algorithms for the Uncapacitated Multiple Allocation p-hub Median Problem. European Journal of Operational Research 104, 100-112.
• ERNST A.T. and KRISHNAMOORTHY, M. (1998b) An exact solution approach based on shortest-paths for p-hub median problems. Informs Journal on Computing 10 (2), 149-162.
• ERNST, A.T., JIANG, H. and KRISHNAMOORTHY, M. (2005) Reformulations and computational results for uncapacitated single and multiple allocation hub covering problems. Unpublished Report, CSIRO Mathematical and Information Sciences, Australia.
• FILIPOVIĆ, V. (1998) Proposal for Improvement of Tournament Selection Operator in Genetic Algorithms (in Serbian). Master thesis, Faculty of Mathematics, University of Belgrade.
• FILIPOVIĆ, V. (2003) Fine-Grained Tournament Selection Operator in Genetic Algorithms. Computing and Informatics 22 (2), 143-161.
• FILIPOVIĆ, V. (2006) Selection and Migration Operators and WEB Services in Paralel Evolutionary Algorithms ( in Serbian). PhD thesis, Faculty of Mathematics, University of Belgrade.
• HOLLAND, J.H. (1975) Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor.
• HORNER, M.W. and O’KELLY, M.E. (2001) Embedding economies of scale concepts for hub network design. Journal of Transport Geography 9 (4), 255-265.
• KARA, B.Y. (1999) Modeling and analysis of issues in hub location problems. Ph.D. Thesis, Bilkent University, Industrial Engineering Department, Bilkent, Ankara, Turkey.
• KARA, B.Y. and TANSEL, B.C. (1999) On the single-assignment p-hub covering problem. Technical report, Department of Industrial Engineering, Bilkent University, Bilkent 06533, Ankara, Turkey.
• KARA, B.Y. and TANSEL, B.C. (2003) The single-assignment hub covering problem: Models and linearizations. Journal of the Operational Research Society 54, 59-64.
• KIMMS, A. (2005) Economies of scale in hub-and-spoke network design models: We have it all wrong. Technical Report, Technische Universitat Bergakademie Freiberg, Germany.
• KLINCEWICZ, J.G. (1991) Heuristics for the p-hub location problem. European Journal of Operational Research 53, 25-37.
• KLINCEWICZ, J.G. (1992) Avoiding local optima in the p-hub location problem using tabu search and GRASP. Annals of Operations Research 40, 283-302.
• KRATICA, J. (1999) Improving Performances of the Genetic Algorithm by Caching. Computers and Artificial Intelligence 18 (3), 271-283.
• KRATICA, J. (2000) Parallelization of Genetic Algorithms for Solving Some NP-complete Problems (in Serbian). PhD thesis, Faculty of Mathematics, University of Belgrade.
• KRATICA, J., TOSIĆ, D., FILIPOVIĆ, V. and LJUBIĆ, I. (2001) Solving the Simple Plant Location Problem by Genetic Algorithm. RAIRO Operations Research 35 (1), 127-142.
• KRATICA, J. and STANIMIROVIĆ, Z. (2006) Solving the Uncapacitated Multiple Allocation p-Hub Center Problem by Genetic Algorithm. Asia-Pacific Journal of Operational Research 23 (4), 425-437.
• KRATICA, J., STANIMIROVIĆ, Z., TOSIĆ, D. and FILIPOVIĆ, V. (2006) Two Genetic Algorithms for Solving the Uncapacitated Single Allocation p-Hub Median Problem. European Journal of Operational Research 182, 15-28.
• LJUBIĆ, I. (2004) Exact and Memetic Algorithms for Two Network Design Problems. PhD thesis, Institute of Computer Graphics, Vienna University of Technology.
• MARIANOV, V., SERRA, D. and REVELLE, C. (1999) Location of hubs in a competitive environment. European Journal of Operational Research 114, 363-371.
• NICKEL, S., SCHOBEL, A. and SONNEBORN, T. (2001) Chapter 1: Hub location problems in urban traffic networks. In: J. Niittymaki and M. Pursula, eds., Mathematics Methods and Optimization in Transportation Systems, Kluwer Academic Publishers.
• O’KELLY, M.E., SKORIN-KAPOV, D. and SKORIN-KAPOV, J. (1995) Lower bounds for the hub location problem. Management Science 41, (4) 713-721.
• O’KELLY, M.E. (1987) A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 32, 393-404.
• O’KELLY, M.E. (1998) A geographer’s analysis of hub-and-spoke networks. Journal of Transport Geography 6 (3), 171-186.
• O’KELLY, M.E. and BRYAN, D.L. (1998) Hub location with flow economies of scale. Transportation Research B 32 (8), 605-616.
• PIRKUL, H. and SCHILLING, D.A. (1998) An efficient procedure for designing single allocation hub and spoke systems. Management Science 44 (12), 235-242.
• PODNAR, H., SKORIN-KAPOV, J. and SKORIN-KAPOV, D. (2002) Network cost minimization using threshold-based discounting. European Journal of Operational Research 137, 371-386.
• PODNAR, H. and SKORIN-KAPOV, J. (2003) Genetic algorithm for network cost minimization using threshold based discounting. Journal of Applied Mathematics and Decision Sciences 7, 207-228.
• RAIDL, G.R. and LJUBIĆ, I. (2002) Evolutionary Local search for the Edge-Biconnectivity Augmentation Problem. Information Processing Letters 82 (1), 39-45.
• SASAKI, M., SUZUKI, A. and DREZNER, Z. (1999) On the selection of hub airports for the airline hub-and-spoke system. Computers and OR 26, 1411-1422.
• SKORIN-KAPOV, D. (2001) On cost allocation in hub-like network. Annals of Operations Research 106, 63-78.
• SKORIN-KAPOV, D. and SKORIN-KAPOV, J. (1994) On tabu search for the location of interacting hub facilities. European Journal of Operational Research 73, 502-509.
• SKORIN-KAPOV, D. and SKORIN-KAPOV, J. (2005) Threshold based discounting networks: The cost allocation provided by the nucleolus. European Journal of Operational Research 166, 154-159.
• SKORIN-KAPOV, D., SKORIN-KAPOV, J. and O’KELLY, M. (1996) Tight linear programming relaxations of uncapacitated p-hub median problems. European Journal of Operational Research 94, 582-593.
• SOHN, J. and PARK, S. (1997) A linear program for the two-hub location problem. European Journal of Operational Research 100 (3), 617-622.
• SOHN, J. and PARK, S. (2000) The single allocation problem in the interacting three-hub network. Networks 35 (1), 17-25.
• TOPCUOGLU, H., CORUT, F., ERMIS, M. and YILMAZ, G. (2005) Solving the uncapacitated hub location problem using genetic algorithms. Computers and OR 32 (4), 967-984.
• WAGNER, B. (2004a) A note on the latest arrival hub location problem. Management Science 50 (12), 1751-1752.
• WAGNER, B. (2004b) Model formulations for hub covering problems. Working paper, Institute of Operations Research, Darmstadt University of Technology.
• YAMAN, H. (2005) Polyhedral analysis for the uncapacitated hub location problem with modular arc capacities. SIAM Journal on Discrete Mathematics 19 (2), 501-522.