ارائه یک مدل ریاضی و روش حل ابتکاری برای مسئله مکان‌یابی-مسیریابی دو‌سطحی با در نظر گرفتن شرایط گذاشت و برداشت در حالت عدم قطعیت

نوع مقاله: مقاله صنایع

نویسندگان

دانشگاه علم و صنعت، دانشکده مهندسی صنایع

چکیده

در این مقاله به ارائه یک مدل ریاضی در حوزه مسائل مکان‌یابی- مسیریابی در حالت دو‌سطحی با در نظر‌گرفتن شرایط گذاشت و برداشت بصورت همزمان پرداخته شده است. در این مسئله به تعیین محل تسهیلات لازم و مسیرهای وسایل نقلیه برای خدمت‌رسانی به مشتریان با در نظرگرفتن برخی از محدودیت‌ها پرداخته می‌شود تا خواسته‌های تمام مشتریان را برآورده سازد و هزینه کل شبکه که شامل هزینه‌های ثابت احداث تسهیلات، هزینه‌های ثابت وسایل نقلیه و هزینه‌های عملیاتی وسایل نقلیه می‌باشد را به حداقل رساند. به دلیل عدم قطعیت موجود در تقاضای مشتریان، این پارامتر در مدل ریاضی در قالب اعداد فازی ذوزنقه‌ای لحاظ شده است. استفاده از این رویکرد می‌تواند به اتخاذ سطح مناسب خدمت به مشتریان توسط خبرگان با در نظر‌گرفتن هزینه‌های سیتم گردد. برای حل این مسئله از یک روش حل ابتکاری بر پایه جستجوی بزرگ همسایگی انطباقی استفاده شده است. برای نمایش کارایی الگوریتم ابتدا برای مدل آزاد شده از نمونه مسائل استاندارد موجود در ادبیات استفاده شده و سپس برای مدل در حالت گذاشت و برداشت نمونه مسائل جدید تولید شده و نتایج حاصل از حل آن گزارش شده است. نتایج بدست آمده از حل مدل حاکی از کارایی الگوریتم در یافتن جواب‌های بهتر نسبت به الگوریتم های ارائه شده بر روی مسائل استاندارد در زمانی معقول، در ادبیات موضوع مسائل مکانیابی- مسیریابی می‌باشد.

کلیدواژه‌ها

موضوعات


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

Presenting a Model and Heuristic Algorithm for Two-Echelon Location-Routing Problem under Uncertainty Considering the Simultaneous Pickup and Delivery

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

  • Seyyed-Mahdi Hosseini-Motlagh
  • Mohammadreza Ghatreh Samani
  • Abbas Jokar
چکیده [English]

In this paper, we address a variant of the Location-Routing Problem (LRP), namely the Two-echelon location routing problem with simultaneous pickup and delivery (2E-LRPSPD). The purpose of location-routing problem is to determine the optimal number and locations of depots while allocating customers to depots and determining number of optimal vehicle and vehicle routes to visit all customers. The objective is to minimize both the cost of open depots and the total cost of the routes. In this paper customer’s demand is uncertain with discrete values in fuzzy trapezoidal numbers. Applying this approach can result in making an appropriate decision of service level for customers by experts while accounting for considering the system’s costs. We propose an adaptive large neighborhood search for the Two-Echelon Location-Routing Problem with simultaneous pickup and delivery (2ELRPSPD). Computational experiments conducted on several sets of instances from the literature show that our algorithm outperforms existing solution methods for the 2E-LRP and a new data set is also generated for our presented model which contains both pickup and delivery demands and Computational results are reported. The results imply the efficiency of the proposed algorithm in finding better solution in comparison to the ones obtained via other algorithms existing in the literature of location routing problem.

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

  • Location routing problem
  • two-echelon
  • simultaneous pickup and delivery
  • Uncertainty
  • adaptive large neighborhood search
1-      

[1]

Prodhon, C and C. Prins, "A survey of recent research on location-routing problems," European Journal of Operational Research, vol. 238, no. 1, pp. 1-17, 2014.

[2]

Prodhon, C., "A hybrid evolutionary algorithm for the periodic location-routing problem," European Journal of Operational Research, vol. 210, no. 2, pp. 204-212, 2011.

[3]

Min, H., V, Jayaraman and R. Srivastava, "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, vol. 108, no. 1, pp. 1-15, 1998.

[4]

Nagy, G. and S. Salh, "Location-routing: Issues, models and methods," European Journal of Operational Research, vol. 177, no. 2, pp. 649-672, 2007.

[5]

Laporte, G and Y. Nobert, "An exact algorithm for minimizing routing and operating costs in depot location," European Journal of Operational Research, vol. 6, no. 2, pp. 224-226, 1981.

[6]

Sajjadi, S.R and S.H. Cheraghi, "Uncertain location routing problem (LRP) integrated to inventory considering space limitation," 2008.

[7]

Lin, C. K. Y., Chow, C. K., & Chen, A. "A location-routing-loading problem for bill delivery services," Computers & industrial engineering, vol. 43, no. 1, pp. 5-25, 2002.

[8]

M. Hamidi, K., Farahmand, S., Reza Sajjadi, and K. Nygard., "A hybrid GRASP-tabu search metaheuristic for a four-layer location-routing problem," International Journal of Logistics Systems and Management, vol. 12, p. 267–287, 2012.

[9]

Jiang, S and Z. Ma, "A Hybrid Genetic Algorithm for the Stochastic Dynamic Location-Routing-Inventory Problem in Closed-Loop Logistics System for Reusing End-of-Use Products," in International Conference on Transportation Engineering, 2009.

 

[10]

Alumur, S and B.Y. Kara, "A new model for the hazardous waste location-routing problem," Computers & Operations Research, vol. 34, no. 5, pp. 1406-1423, 2007.

[11]

Zarandi, M.H.F., A. Hemmati and S. Davari, "The multi-depot capacitated location-routing problem with fuzzy travel times," Expert Systems with Applications, vol. 38, no. 8, pp. 10075-10084, 2011.

[12]

Wasner, M and G. Zäpfel, "An integrated multi-depot hub-location vehicle routing model for network planning of parcel service," International Journal of Production Economics, vol. 90, no. 3, pp. 403-419, 2004.

[13]

Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. European Journal of Operational Research, 211(2), 318-332, 2011.

[14]

Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477, 2012.

[15]

F. Golozari, A. Jafari, and M. Amir, "Application of a hybrid simulated annealing-mutation operator to solve fuzzy capacitated location-routing problem," The International Journal of Advanced Manufacturing Technology, vol. 67, p. 1791–1807, 2013.

[16]

Ghodsi, R., & Amiri, A. S. A variable neighborhood search algorithm for continuous location routing problem with pickup and delivery. In 2010 Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation (pp. 199-203). IEEE, 2010.

[17]

Rieck, J., Ehrenberg, C., & Zimmermann, J. Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. European Journal of Operational Research, 236(3), 863-878, 2014.

[18]

Pishvaee, Mir Saman, Masoud Rabbani, and Seyed Ali Torabi. "A robust optimization approach to closed-loop supply chain network design under uncertainty." Applied Mathematical Modelling 35.2,pp637-649, 2011.

[19]

Torabi, S. Ali, and Elkafi Hassini. "An interactive possibilistic programming approach for multiple objective supply chain master planning." Fuzzy Sets and Systems 159, no. 2  pp 193-214, 2008.

[20]

L.A. Zadeh, "Fuzzy sets,," Information and Control 8, p. 338–353, 1965.

[21]

A. Kaufmann, "Introduction to the Theory of Fuzzy Subsets,," Academic Press, New York,, 1975.

[22]

L.A. Zadeh, "Fuzzy sets as a basis for a theory of possibility,," Fuzzy Sets and Systems 1, p. 3–28, 1978.

[23]

B. Liu, "Uncertain Theory: An Introduction to its Axiomatic Foundations,," Springer, Berlin,, 2004.

[24]

S. Nahmias, "Fuzzy variables, Fuzzy Sets and Systems," pp. 97-110, 1987.

[25]

Nguyen, V.-P., C. Prins and C. Prodhon, "A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem," Engineering Applications of Artificial Intelligence, vol. 25, no. 1, pp. 56-71, 2012.