مسئلۀ مکان‏یابی ـ مسیریابی هاب زمینی در محدودۀ نامتراکم و وسیع

نوع مقاله : مقاله علمی پژوهشی

نویسندگان

1 دکتری مدیریت تولید و عملیات، گروه مدیریت صنعتی، دانشکدۀ مدیریت، دانشگاه تهران، تهران، ایران

2 استاد گروه مدیریت صنعتی، دانشکدۀ مدیریت، دانشگاه تهران، تهران، ایران

3 استاد دانشکدۀ مهندسی صنایع، پردیس دانشکده‎های فنی، دانشگاه تهران، تهران، ایران

4 استاد دانشکدۀ مهندسی صنایع، دانشگاه شریف، تهران، ایران

چکیده

به‎منظور کنترل هزینه‏ها در یک شبکۀ حمل و نقل زمینی که میزان کالای انتقالی بین شهرها از میزان ظرفیت یک کامیون کمتر است، باید علاوه‎بر تعیین محل صحیح هاب‏ها، بار چند شهر با یکدیگر تجمیع شود و پس از تعیین مسیر حرکت کالاها، به هاب مناسب اختصاص یابد. در این مقاله، حالت خاصی از مسئلۀ مکان‏یابی ـ مسیریابی هاب زمینی مطرح می‏شود که مناسب با وضعیت ایران است؛ به‏طوری‏که شهرها در محدودۀ نامتراکم و وسیع واقع شده‏اند. یک مدل برنامه‏ریزی ریاضی عدد صحیح مختلط به‏منظور نگاشت مسئله ارائه شده است. با توجه به پیچیدگی محاسباتی حل بهینۀ مدل، روش حل دو مرحله‏ای، تلفیقی از الگوریتم‏های ژنتیک و شبیه‏سازی تبرید طراحی شده است. نتایج مقایسات عددی روش حل پیشنهاد شده با یک روش بهینه‏یاب، نشان از دقت و سرعت روش حل ارائه شده دارد. در نهایت یک مورد واقعی از ایران با 31 مرکز استان حل شده تا عملکرد مناسب روش حل پیشنهاد شده در این پژوهش نشان داده شود.

کلیدواژه‌ها


عنوان مقاله [English]

Road Hub Location-Routing Issue in a Sparse and Distant Area

نویسندگان [English]

  • Farzad Bahrami 1
  • Hossein Safari 2
  • Reza Tavakkoli-Moghaddam 3
  • Mohammad Modarres Yazdi 4
1 Ph.D. Candidate in Production and Operations Management, University of Tehran, Tehran, Iran
3 Prof., School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
4 Prof., Dep. of Industrial Engineering, Sharif University of Technology, Tehran, Iran
چکیده [English]

In order to manage the expenditures in a road transportation network in which the transport demands between cities are less than a truckload capacity, one needs to determine the location of hubs at first, and then collect the cargo from the cities in some routes which are assigned to the appropriate hubs. In this paper, a special case of hub location-routing issue was considered that is suitable for the particular conditions of Iran as cities are located in the sparse and distant places. A mixed integer mathematical programming model was proposed. As the model is NP-hard in nature, a two-phase hybrid method including genetic algorithms and simulated annealing was designed to solve the model. The results of the comparison between the model and the outputs demonstrated the accuracy and speed of the proposed solution method. Finally, a real case including all 31 capital cities of Iran provinces was solved to illustrate the appropriate performance of the solution method.

کلیدواژه‌ها [English]

  • Genetic Algorithm
  • Hub location
  • Mathematical Programming
  • Simulated Annealing
  • Vehicle routing problem
رضوی، م.، سوخکیان، م.ع.، زیارتی، ک. (1390). ارائۀ الگوریتم فراابتکاری مبتنی بر سیستم کلونی مورچگان برای مسئلۀ مکان‏یابی مسیریابی با چندین انبار و فرض تخصیص چندین مسیر به هر وسیلۀ نقلیه. مجلۀ مدیریت صنعتی، 3 (6)، 38-17.
شاهین، م.، جبل عاملی، م. س.، جبارزاده، آ. (1395). مکان‏یابی هاب سلسله‎مراتبی چند روش حمل و نقلی و چند کالایی در فضای غیرقطعی. مجلۀ مدیریت صنعتی، 8 (4)، 658-625.
Alumur, S., & Kara, B. Y. (2008). Network hub location problems: The state of the art. European journal of operational research, 190(1), 1-21.
Baker, B. M. & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
Campbell, A. M., Lowe, T. J. & Zhang, L. (2007). The p-hub center allocation problem. European Journal of Operational Research, 176(2), 819-835.
Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72(2), 387-405.
Campbell, J. F., & O’Kelly, M. E. (2012). Twenty-five years of hub location research. Transportation Science, 46(2), 153-169.
Černý, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45(1), 41-51.
Cunha, C. B. & 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, 179(3), 747-758.
Doulabi, S. H. H. & Seifi, A. (2013). Lower and upper bounds for location-arc routing problems with vehicle capacity constraints. European Journal of Operational Research, 224(1), 189-208.
Ernst, A.T. & Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science, 4(3), 139-154.
Holland, J. H. (1992). Genetic algorithms. Scientific american, 267(1), 66-72.
Jarboui, B., Derbel, H., Hanafi, S. & Mladenović, N. (2013). Variable neighborhood search for location routing. Computers & Operations Research, 40(1), 47-57.
Karaoglan, I., Altiparmak, F., Kara, I. & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.
Krikpatrick, S., Gelatt Jr. C.D. & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220 (4598), 671-680.
Kuby, M. J. & Gray, R. G. (1993). The hub network design problem with stopovers and feeders: The case of Federal Express. Transportation Research Part A: Policy and Practice, 27(1), 1-12.
Laporte, G., (1988). Location-routing problems. In Golden, B.L., Assad, A.A. (eds) Vehicle Routing: Methods, Studies. North-Holland, Amsterdam.
Lee, J. H. & Moon, I. (2014). A hybrid hub-and-spoke postal logistics network with realistic restrictions: A case study of Korea Post. Expert systems with applications, 41(11), 5509-5519.
Lee, Y., Lim, B. H. & Park, J. S. (1996). A hub location problem in designing digital data service networks: Lagrangian relaxation approach. Location Science, 4(3), 185-194.
Lopes, R. B., Ferreira, C., Santos, B. S. & Barreto, S. (2013). A taxonomical analysis, current methods and objectives on location‐routing problems. International Transactions in Operational Research, 20(6), 795-822.
Martı́n, J. C. & Román, C. (2003). Hub location in the South-Atlantic airline market: A spatial competition game. Transportation Research Part A: Policy and Practice, 37(10), 865-888.
Nagy, G. & Salhi, S. (1998). The many-to-many location-routing problem. Top, 6(2), 261-275.
Nagy, G. & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
Norouzi, N., Sadegh-Amalnick, M. & Tavakkoli-Moghaddam, R. (2016). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 11(1), 121-134.
O’kelly, M. E. (1986). The location of interacting hub facilities. Transportation science, 20(2), 92-106.
Razavi, M., Soukhakian, M. A. & Ziarati, K. (2011). A Meta Heuristic Algorithms Based on Ant Colony System For Solving Multi Depots Location-routing Problem with Multiple Using of Vehicle. Industrial Management, 3(6), 17-38. (in Persian)
Rieck, J., Ehrenberg, C. & Zimmermann, J. (2014). Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. European Journal of Operational Research, 236(3), 863-878.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European journal of operational research, 39(2), 150-156.
Sasaki, M., Campbell, J.F., Krishnamoorthy, M. & Ernst, A.T. (2014). A Stackelberg hub arc location model for a competitive environment. Computers & Operations Research, 47, 27-41.
Sasaki, M., Suzuki, A. & Drezner, Z. (1999). On the selection of hub airports for an airline hub-and-spoke system. Computers & Operations Research, 26(14), 1411-1422.
Shahin, M., Jabalameli, M. S., Jabbarzadeh, A. (2017). Multi-modal and multi-product hierarchical hub location under uncertainty. Industrial Management, 8(4), 625-658. (in Persian)
Taylor, G. D., Harit, S., English, J. R. & Whicker, G. (1995). Hub and spoke networks in truckload trucking: Configuration, testing and operational concerns. Logistics and Transportation Review, 31(3), 209-237.
Toh, R. S. & Higgins, R. G. (1985). The impact of hub and spoke network centralization and route monopoly on domestic airline profitability. Transportation Journal, 24(4), 16-27.
Wasner, M. & Zäpfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403-419.
Wolsey, L. A. (1998). Integer programming. New York, John Wiley & Sons, Inc.
Yaman, H., Kara, B. Y., & Tansel, B. Ç. (2007). The latest arrival hub location problem for cargo delivery systems with stopovers. Transportation Research Part B: Methodological, 41(8), 906-919.