Journal of the Korean Operations Research and Management Science Society (한국경영과학회지)

The Korean Operations Research and Management Science Society (한국경영과학회)
권호 표지

Extended Hub-and-spoke Transportation Network Design using a Symbiotic Evolutionary Algorithm

공생 진화알고리듬을 이용한 확장된 hub-and-spoke 수송네트워크 설계

  • 신경석 (전남대학교 산업공학과) ;
  • 김여근 (전남대학교 산업공학과)
  • Published : 2006.06.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we address an extended hub-and-spoke transportation network design problem (EHSNP). In the existing hub location problems, the location and number of spokes, and shipments on spokes are given as input data. These may, however, be viewed as the variables according to the areas which they cover. Also, the vehicle routing in each spoke needs to be considered to estimate the network cost more correctly. The EHSNP is a problem of finding the location of hubs and spokes, and pickup/delivery routes from each spoke, while minimizing the total related transportation cost in the network. The EHSNP is an integrated problem that consists of several interrelated sub-problems. To solve EHSNP, we present an approach based on a symbiotic evolutionary algorithm (symbiotic EA), which are known as an efficient tool to solve complex integrated optimization problems. First, we propose a framework of symbiotic EA for EHSNP and its genetic elements suitable for each sub-problem. To analyze the proposed algorithm, the extensive experiments are performed with various test-bed problems. The results show that the proposed algorithm is promising in solving the EHSNP.

Keywords

References

  1. Aykin, T., 'Lagrangian Relaxation based Approaches to Capacitated Hub-and-spoke Network Design Problem,' European Journal of Operational Research, Vol.79(1994), pp.501-523 https://doi.org/10.1016/0377-2217(94)90062-0
  2. Aykin, T., 'The Hub Location and Routing Problem,' European Journal of Operational Research, Vol.83(1995), pp.200-219 https://doi.org/10.1016/0377-2217(93)E0173-U
  3. Bianchessi N. and G. Righini, 'Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery,' Computers & Operations Research, in press
  4. Boland, N., M. Krishnamoorthy, A.T. Ernst, and J. Ebery, 'Preprocessing and Cutting for Multiple Allocation Hub Location Problems,' European Journal of Operational Research, Vol.155(2004), pp.638-653 https://doi.org/10.1016/S0377-2217(03)00072-9
  5. Campbell, F.F., 'Integer Programming Formulations of Discrete Hub Location Problems,' European Journal of Operational Research, Vol.72(1994), pp.387-405 https://doi.org/10.1016/0377-2217(94)90318-2
  6. Clark, G. and J. Wright, 'Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,' Operations Research, Vol.12(1964), pp.568-581 https://doi.org/10.1287/opre.12.4.568
  7. Dilek, T. and I.B. Laura, 'A Two-phase Tabu Search Approach to the Location Routing Problem,' European Journal of Operational Research, Vol.116(1999), pp.87-99 https://doi.org/10.1016/S0377-2217(98)00107-6
  8. Ebery, J., M. Krishnamoorthy, A. Ernst, and N. Boland, 'The Capacitated Multiple Allocation Hub Location Problem：Formulations and Algorithms,' European Journal of Operational Research, Vol.120(2000), pp. 614-631 https://doi.org/10.1016/S0377-2217(98)00395-6
  9. Elhedhli, S. and F.X. Hu, 'Hub-and-spoke Network Design with Congestion,' Computer and Operations Research, Vol.32(2005), pp.1615-1632 https://doi.org/10.1016/j.cor.2003.11.016
  10. Ernst, A.T. and M. Krishnamoorthy, 'Efficient Algorithms for the Uncapacitated Single Allocation p-hub Median Problem,' Location Science, Vol.4(1996), pp.139-154 https://doi.org/10.1016/S0966-8349(96)00011-3
  11. Hansen, P.H., B. Hegedahl, S. Hjortkjaer, and B. Obel, 'A Heuristic Solution to the Warehouse Location-routing Problem,' European Journal of Operational Research, Vol. 76(1994), pp.111-127 https://doi.org/10.1016/0377-2217(94)90010-8
  12. Helm, S.A., 'A Hybrid Heuristic for the Uncapacitated Hub Location Problem,' European Journal of Operational Research, Vol.106(1998), pp.489-499 https://doi.org/10.1016/S0377-2217(97)00286-5
  13. Helm, S.A. and M.A. Venkataramanan, 'Solution Approaches to Hub Location Problems,' Annals of Operations Research, Vol.78(1998), pp.31-50 https://doi.org/10.1023/A:1018954217758
  14. Jacobsen, S.K. and O.B.G. Madsen, 'A Comparative Study of Heuristics for a Two-level Routing-location Problem', European Journal of Operational Research, Vol.5(1980), pp.378-387 https://doi.org/10.1016/0377-2217(80)90124-1
  15. Kim, Y.K., J.Y. Kim, and Y. Kim, 'A Coevolutionary Algorithm for Balancing and Sequencing in mixed model assembly lines', Applied Intelligence, Vol.13(2000), pp.247- 258 https://doi.org/10.1023/A:1026568011013
  16. Kim, Y.K., K. Park, and J. Ko, 'A Symbiotic Evolutionary Algorithm for the Integration of Process Planning and Job Shop Scheduling,' Computers & Operations Research, Vol.30(2003), pp.1151-1171 https://doi.org/10.1016/S0305-0548(02)00063-1
  17. Laporte, G., Y. Nobert, and S. Taillefer, 'Solving a Family of Multi-depot Vehicle Routing and Location-routing Problems,' Transportation Science, Vol.22(1988), pp. 161-172 https://doi.org/10.1287/trsc.22.3.161
  18. Lumsden, K., F. Dallari, and R. Ruggeri, 'Improving the Efficiency of the Hub and Spoke System for the SKF European Distribution Network,' International Journal of Physical Distribution & Logistics Management, Vol.29(1999), pp.50-64 https://doi.org/10.1108/09600039910253878
  19. Melkote, S. and M.S. Daskin, 'Capacitated Facility Location/Network Design Problems,' European Journal of Operational Research, Vol.129(2001), pp.481-495 https://doi.org/10.1016/S0377-2217(99)00464-6
  20. Moriarty, D.E. and R. Miikkulainen, 'Forming Neural Networks through Efficient and Adaptive Coevolution,' Evolutionary Computation, Vol.5(1997), pp.373-399 https://doi.org/10.1162/evco.1997.5.4.373
  21. Perl, J. and M.S. Daskin, 'A Warehouse Location Problem,' Transportation Research Quarterly B, Vol.19(1985), pp.381-396 https://doi.org/10.1016/0191-2615(85)90052-9
  22. Potter, M.A., 'The Design and Analysis of a Computational Model of Cooperative Coevolution,' Ph.D. dissertation, George Mason University, (1997)
  23. Skorin-Kapov, D., J. Skorin-Kapov, and M. O'Kelly, 'Tight Linear Programming Relaxations of Uncapacitated p-hub Median Problems,' European Journal of Operational Research, Vol.94(1996), pp.582-593 https://doi.org/10.1016/0377-2217(95)00100-X
  24. Shin, K.S., 'A Set of Data for Extended Hub-and-spoke Transportation Networks Design using an Symbiotic Evolutionary Algorithm,' available at http://syslab.chonnam.ac.kr/links/EHSNPdata.zip, (2006)
  25. Srivastava, R. and W.C. Benton, 'The Location- routing Problem：Consideration in Physical Distribution System Design,' Computers and Operations Research, Vol.6 (1990), pp.427-435
  26. Topcuoglu, H., F. Corut, M. Ermis, and G. Yilmaz, 'Solving the Uncapacitated Hub Location Problem using Genetic Algorithms,' Computer and Operations Research, Vol.32(2005), pp.967-984 https://doi.org/10.1016/j.cor.2003.09.008
  27. Wu, T.-H., C. Low, and J.-W. Bai, 'Heuristic Solutions to Multi-depot Locationrouting Problems,' Computers & Operations Research, Vol.29(2002), pp.1393-1415 https://doi.org/10.1016/S0305-0548(01)00038-7
  28. Zafel, G. and M. Wasner, 'An Integrated Multi-depot Hub-location Vehicle Routing Model for Network Planning of Parcel Service,' International Journal of Production Economics, Vol.90(2004), pp.403-419 https://doi.org/10.1016/j.ijpe.2003.12.002