مسأله‌ یکپارچه‌ی دریافت، تحویل و بازگشت وسایل‌نقلیه با محدودیت‌های بارگذاری سه‌بعدی و پنجره‌ی زمانی

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

نویسندگان

1 دانشجوی کارشناسی‌ارشد، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان، اصفهان، ایران

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

3 استادیار، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان، اصفهان، ایران

چکیده

مسائل مسیریابی و بارگذاری، دو موضوع مهم‌ برای کاهش هزینه‌های حمل‌ونقل محسوب می‌شود. در دهه‌ی‌ اخیر به‌دلیل نزدیک‌سازی مسائل مسیریابی وسایل‌نقلیه به دنیای واقعی، این مسائل را به‌صورت یکپارچه با یکدیگر درنظر گرفته‌اند. رعایت نکردن محدودیت‌های بارگذاری منجر به آسیب رسیدن به کالاها و یا استفاده‌ی کمتر از فضای وسیله‌نقلیه می‌شود که در هرکدام از حالت‌ها باعث خسارت و ایجاد هزینه‌ی اضافه می‌شود. در این مقاله برای اولین‌بار مسأله یکپارچه‌ی مسیریابی دریافت، تحویل و بازگشت با محدودیت‌های بارگذاری سه‌بعدی و پنجره‌ی زمانی درنظر گرفته شده که محدودیت‌های انباشت، جهت‌گیری، عدم‌بارگذاری مجدد و شرایط چند تحویلی در این مسأله مورد بررسی قرار گرفته است. هم‌چنین در این مطالعه، آیتم‌ها و کانتینرها ناهمگون درنظر گرفته شده‌اند. با بررسی ادبیات موضوع این مسأله در ادبیات موضوع مشاهده نگردید. برای این مسأله یک مدل برنامه‌ریزی عدد صحیح مختلط، یک الگوریتم ابتکاری و دو الگوریتم فراابتکاری برمبنای جست‌وجوی ممنوع و جست‌وجوی همسایگی متغیر ارائه شده است. الگوریتم‌های فراابتکاری در ابعاد کوچک با حل پایین حاصل از آزادسازی برخی محدودیت‌های مدل ارائه شده مورد ارزیابی قرار گرفته و در ابعاد بزرگ نیز دو الگوریتم فراابتکاری با یکدیگر مقایسه شده‌اند. نتایج نشان می‌دهد متوسط درصد خطای نسبی در الگوریتم جست‌وجوی ممنوع و جست‌وجوی همسایگی متغیر به ترتیب برابر 96/0 و 88/0 می‌باشد. هم‌چنین الگوریتم جست‌وجوی ممنوع و جست‌وجوی همسایگی متغیر توانسته‌اند از 54 نمونه به‌ترتیب در 27 و 25 نمونه جواب بهتری ارائه دهند.

کلیدواژه‌ها

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

Integrated problem of pick up, delivery and backhaul with three-dimensional loading constraints and time window

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

  • Amir Hazrati 1
  • Ghasem Moslehi 2
  • Mohammad Reisi-Nafchi 3
1 M.A. Student, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
2 Professor, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
3 Assistant Professor, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
چکیده [English]

The routing and loading problems are two essential issues to reduce transportation costs. In the recent decade, these problems have been integrated to realize the vehicle routing problem. Failure to comply with the loading constraints may result in damage to the goods or less use of the vehicle space, which in each case will result in additional damage and cost. In this paper, for the first time, the integrated routing problem of pickup, delivery, and backhaul with three-dimensional loading constraints and time window is considered, where the constraints of accumulation, orientation, non-reloading, and multi-delivery conditions are examined. In this study, items and containers are considered heterogeneous. By examining the subject literature, this problem was not observed in the literature. A mixed-integer programming model, a heuristic algorithm, and two metaheuristic algorithms based on tabu search and variable neighborhood search are proposed for this problem. For small instances the proposed metaheuristics were compared to the lower bound obtained from relaxing some constraints of the model. For large instances, the two metaheuristic algorithms are compared together. The results show that the average percentage of relative error in the tabu search and variable neighbor search algorithms is 0.96 and 0.88, respectively. Also, the tabu search algorithm and variable neighborhood search were able to give better results out of 54 instances in 27 and 25 instances, respectively.

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

  • Routing
  • Pickup. Delivery and backhaul. 3-dimensional loading
  • Tabu search
  • Variable neighborhood search

مراجع

[1]    Karak, A., and Abdelghany, K., (2019). The hybrid vehicle-drone routing problem for pick-up and delivery services, Transportation Research Part C: Emerging Technologies, Vol. 102, pp. 427-449.
[2]    Li, H., and Lim, A., (2003). A metaheuristic for the pickup and delivery problem with time windows, International Journal on Artificial Intelligence Tools, Vol. 12, pp. 173-186.
[3]    Solomon, M.M., (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations research, Vol. 35, pp. 254-265.
[4]    Bravo, M., Rojas, L.P., and Parada, V., (2019). An evolutionary algorithm for the multi‐objective pick‐up and delivery pollution‐routing problem, International Transactions in Operational Research, Vol. 26, pp. 302-317.
[5]    Sitek, P., and Wikarek, J., (2019). Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach, Annals of Operations Research, Vol. 273, pp. 257-277.
[6]    Madankumar, S., and Rajendran, C., (2019). A mixed integer linear programming model for the vehicle routing problem with simultaneous delivery and pickup by heterogeneous vehicles, and constrained by time windows, Sādhanā, Vol. 44, pp. 39.
[7]    Granada-Echeverri, M., Toro, E., and Santa, J., (2019). A mixed integer linear programming formulation for the vehicle routing problem with backhauls, International Journal of Industrial Engineering Computations, Vol. 10, pp. 295-308.
[8]    Chávez, J., Escobar, J., Echeverri, M., and Meneses, C., (2018). A heuristic algorithm based on tabu search for vehicle routing problems with backhauls, Decision Science Letters, Vol. 7, pp. 171-180.
[9]    Salhi, S., and Nagy, G., (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the operational Research Society, Vol. 50, pp. 1034-1042.
[10] Gendreau, M., Iori, M., Laporte, G., and Martello, S., (2006). A tabu search algorithm for a routing and container loading problem, Transportation Science, Vol. 40, pp. 342-350.
[11] Fagerholt, K., Hvattum, L.M., Johnsen, T.A., and Korsvik, J.E., (2013). Routing and scheduling in project shipping, Annals of Operations Research, Vol. 207, pp. 67-81.
[12] Cherkesly, M., Desaulniers, G., and Laporte, G., (2015). A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading, Computers & Operations Research, Vol. 62, pp. 23-35.
[13] Männel, D., and Bortfeldt, A., (2016). A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints, European Journal of Operational Research, Vol. 254, pp. 840-858.
[14] Männel, D., and Bortfeldt, A., (2018). Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban, European Journal of Operational Research, Vol. 264, pp. 119-137.
[15] Bortfeldt, A., Hahn, T., Männel, D., and Mönch, L., (2015). Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints, European Journal of Operational Research, Vol. 243, pp. 82-96.
[16] Pinto, T., Alves, C., and Valério de Carvalho, J., (2020). Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls, International Transactions in Operational Research, Vol. 27, pp. 549–572.
[17] Reil, S., Bortfeldt, A., and Mönch, L., (2018). Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints, European Journal of Operational Research, Vol. 266, pp. 877-894.
[18] Pollaris, H., Braekers, K., Caris, A., Janssens, G.K., and Limbourg, S., (2016). Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints, EURO Journal on Transportation and Logistics, Vol. 5, pp. 231-255.
[19] Tao, Y., and Wang, F., (2015). An effective tabu search approach with improved loading algorithms for the 3L-CVRP, Computers & Operations Research, Vol. 55, pp. 127-140.
[20] Junqueira, L., and Morabito, R., (2015). Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier, Computers & Industrial Engineering, Vol. 88, pp. 110-130.
[21] Zhang, Z., Wei, L., and Lim, A., (2015). An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints, Transportation Research Part B: Methodological, Vol. 82, pp. 20-35.
[22] Mahvash, B., Awasthi, A., and Chauhan, S., (2017). A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints, International Journal of Production Research, Vol. 55, pp. 1730-1747.
[23] حسن‌آبادی، س.، (1395). یکپارچه‌سازی مسأله مسیریابی دریافت و تحویل با محدودیت‌های بارگذاری سه‌بعدی و پنجره زمانی، دانشکده مهندسی صنایع و سیستم‌ها, دانشگاه صنعتی اصفهان.
[24] Zachariadis, E.E., Tarantilis, C.D., and Kiranoudis, C.T., (2017). Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints, Operational Research, Vol. 17, pp. 115-143.
[25] Vega‐Mejía, C.A., Montoya‐Torres, J.R., and Islam, S.M., (2019). A nonlinear optimization model for the balanced vehicle routing problem with loading constraints, International Transactions in Operational Research, Vol. 26, pp. 794-835.
[26] Song, X., Jones, D., Asgari, N., and Pigden, T., (2019). Multi-objective vehicle routing and loading with time window constraints: a real-life application, Annals of Operations Research, Vol., pp. 1-27.
[27] Bortfeldt, A., and Yi, J., (2020). The split delivery vehicle routing problem with three-dimensional loading constraints, European Journal of Operational Research, Vol. 282, pp. 545-558.
[28] Paquay, C., Schyns, M., and Limbourg, S., (2016). A mixed integer programming formulation for the three‐dimensional bin packing problem deriving from an air cargo application, International Transactions in Operational Research, Vol. 23,  pp. 187-213.
[29] Junqueira, L., Morabito, R., and Yamashita, D.S., (2012). Three-dimensional container loading models with cargo stability and load bearing constraints, Computers & Operations Research, Vol. 39, pp. 74-85.
[30] Junqueira, L., Oliveira, J.F., Carravilla, M.A., and Morabito, R., (2013). An optimization model for the vehicle routing problem with practical three‐dimensional loading constraints, International Transactions in Operational Research, Vol. 20, pp. 645-666.
[31] Crainic, T.G., Perboli, G., and Tadei, R., (2008). Extreme point-based heuristics for three-dimensional bin packing, Informs Journal on computing, Vol. 20, pp. 368-384.
[32] Hemmelmayr, V.C., Cordeau, J.-F., and Crainic, T.G., (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Computers & Operations Research, Vol. 39, pp. 3215-3228.
[33] Ghilas, V., Demir, E., and Van Woensel, T., (2016). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines, Computers & Operations Research, Vol. 72, pp. 12-30.
[34] Glover, F., (1986). Future paths for integer programming and links to artificial intelligence, Computers & operations research, Vol. 13, pp. 533-549.
[35] Mladenović, N., and Hansen, P., (1997). Variable neighborhood search, Computers & Operations Research, Vol. 24, pp. 1097-1100.
[36] Koch, H., Bortfeldt, A., and Wäscher, G., (2018). A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints, OR Spectrum, Vol., pp. 1-47.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 8، شماره 17
اسفند 1399
صفحه 321-345

فایل ها

هم رسانی

ارجاع به این مقاله

آمار