حل مساله مکانیابی- مسیریابی وسیله نقلیه با ظرفیت سوخت مشخص بر اساس پنجره زمانی سخت و رضایتمندی مشتریان به کمک الگوریتم فراابتکاری ژنتیک رتبه بندی نامغلوب | ||
مدیریت مهندسی و رایانش نرم | ||
مقاله 2، دوره 9، شماره 1 - شماره پیاپی 16، فروردین 1402، صفحه 19-35 اصل مقاله (928.5 K) | ||
نوع مقاله: مقاله پژوهشی | ||
شناسه دیجیتال (DOI): 10.22091/JEMSC.2021.6257.1143 | ||
نویسنده | ||
محمد مشرفی* | ||
کارشناسی ارشد مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران. رایانامه: Mohammadmoshrefi1371@gmail.com | ||
چکیده | ||
مساله چندهدفه مکانیابی- مسیریابی یکی از مهمترین حوزههای تحقیقاتی در زمینه حمل ونقل و مدیریت پخش است. هدف از این پژوهش، بهینه سازی یک مساله چند هدفه است. ترکیب نمودن دو مساله مسیریابی و مکانیابی، در نظر گرفتن مجموعهای از انبارها، برآورده ساختن نیازهای مشتریان از هریک از انبارها و طراحی یک مسیر بهینه برای وسیله نقلیه که کمترین هزینه را بر سیستم حمل و نقل وارد آورد، از اهداف اصلی این پژوهش است. عواملی مانند میزان رضایتمندی مشتریان از دریافت خدمات، محدودیت سوخت در وسائط نقلیه و وجود بازههای زمانی با اهمیت که تحت عنوان پنجره زمانی سخت از آن نام برده میشود، اگرچه در مسائل مکانیابی و مسیریابی، دارای اهمیت زیادی هستند ولی کمتر به آنها پرداخته شده است و در این تحقیق تلاش شده که به این موضوع پرداخته شود.رسیدن به بهترین اولویت با دستیابی به کمترین فاصله طی شده و قرارگرفتن در کمترین انحراف از پنجره زمانی، از جمله اهداف این تحقیق است. ترکیب نمودن متغیر مربوط به میزان ظرفیت سوختگیری وسایل نقلیه و همچنین سرعت مصرف سوخت در آنها نیز در این تحقیق بکار گرفته شده است. در این پژوهش، ابتدا یک مدل برنامهریزی خطی و بر اساس عدد صحیح مختلط ارائه گردیده است سپس روش فراابتکاری بر اساس الگوریتم ژنتیک مرتب شده غیر مغلوب برای یافتن بهینه آن پیشنهاد گردیده است. برای ارزیابی عملکرد پیشنهادی مثالی در همین چارچوب ذکر میگردد که در نتیجه آزمایشهای محاسباتی، کارایی روش تحقیق موجود و نقاط قوت و ضعف آن را نشان میدهد. | ||
کلیدواژهها | ||
الگوریتم مرتب شده غیرمغلوب؛ پنجره زمانی سخت؛ دپوی تخصیص مشتری؛ مکانیابی- مسیریابی وسیله نقلیه | ||
عنوان مقاله [English] | ||
Location Problem - Routing a vehicle with a specified fuel capacity based on a tough time window and customer satisfaction | ||
نویسندگان [English] | ||
Mohammad Moshrefi | ||
Msc, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran. Email: MohammadMoshrefi1371@gmail.com | ||
چکیده [English] | ||
Multi-objective location-routing problem is one of the most important research areas in the field of transportation and distribution management. The aim of this study is to optimize a multi-objective problem. Combining two routing and location problems, considering a set of warehouses, meeting the customer’s requirements from each warehouse, and designing an optimal route for the vehicle that brings the lowest cost to the transportation system are the main objectives of this research. Although factors such as customer satisfaction with receiving services, fuel constraints in vehicles and the existence of important time intervals, which are referred to as hard time window, are of great importance in location and routing problems, less has been paid to them. In this research, efforts have been made to address these issues. To achieve the best priority by finding the shortest route and to reach the least deviation from the time window is some of the objectives of this research. Combining variables related to vehicle fuel capacity and fuel consumption speed has also been applied in this study. In this research, first, a mixed integer linear programming model is presented and then metaheuristic method based on Non-dominated Sorting Genetic Algorithm is proposed to find the optimal solution. To evaluate the proposed performance, an example is mentioned in this framework. The result of computational experiments, shows the efficiency of the existing research methodology and its strengths and weaknesses. | ||
کلیدواژهها [English] | ||
Non-dominated Sorting Genetic Algorithm, Hard Time Window, Warehouse Assignment, Vehicle Location-Routing Problem | ||
مراجع | ||
K . Gheisari, F. Ghannadpour “Routing of locomotives in the network using a hybrid genetic algorithm” Transportation Research Journal, Issue 3, Fall 2008 . https://doi.org/10.1016/j.trb.2017.04.003
D.L. Applegate, R.E. Bixby, V. Chvatal, and W.J. Cook “The Traveling Salesman Problem” A Computational Study, Princeton University Press, Princeton, NJ, 2007. https://doi.org/1015/j.trb.2023.37.96 Dantzig, G.B.; Ramser, J.H. (1959). "The Truck Dispatching Problem". Management Science 6 (1): 80–91. doi:10.1287/mnsc.6.1.80. ISSN 0025-1909. JSTOR 2627477. https://doi.org/1029/j.trb.2004.16.18 Seyed farid Ghannadpoura , Simak Nooria , Reza Tavakkoli-Moghaddamb,Keivan Ghoseiri ,” A multi-objective dynamic vehicle routing problem with fuzzy timewindows: Model, solution and application “ , 2014. https://doi.org/1033/j.trb.2007.8.18 Gendreau, M., Laporte, G. and Potvin, J.Y. (1999) "Metaheuristics for the vehicle routing problem", Technical Report CRT-963, Centre de Recherche surles Transports, Université de Montréal. https://doi.org/1033/j.trb.2008.5.37 Cordeau, J.F. and Laporte, G. (2002) "Modeling and optimization of vehicle routing and arc routing problem", Les Cahiers du GERARD, G-2002-30, Montréal, Canada H3T 2A7. https://doi.org/1093/j.trb.2002.33.78 Hasle, G. (2003) "Heuristic for rich VRP models", working paper, Department of Optimization, Department of Informatics, University of Oslo. https://doi.org/1080/j.trb.2015.32.50 Pisinger, D. and Ropke, S. (2005) "A general heuristic for vehicle routing problem", Department of Computer Science, University of Copenhagen. https://doi.org/1081/j.trb.2009.13.133 Tan, K.C., Lee, L.H., Hu, K.Q. and Qu, K. (2001) "Heuristic methods for vehicle routing problem with time windows”, Artificial Intelligence in Engineering, 15, pp. 281-295. https://doi.org/1023/j.trb.2011.24.64 Laporte, G. and Semet F. (1999) "Classical heuristics for the vehicle routing problem", Les Cahiers du GERAD, G98-54, Group for Research in Decision Analysis, Montreal, Canada. https://doi.org/1024/j.trb.2005.37.109 Gendreau, M., Laporte, G. and Potvin, J.Y. (1999) "Metaheuristics for the vehicle routing problem", Technical Report CRT-963, Centre de Recherche surles Transports, Universite de Montreal. https://doi.org/1018/j.trb.2014.24.85 Cordeau, J.F. and Laporte, G. (2002) "Modeling and optimization of vehicle routing and arc routing problem", Les Cahiers du GERARD, G-2002-30, Montréal, Canada H3T 2A7. https://doi.org/1057/j.trb.2012.22.42 Braysy, O. and Gendreau, M. (2001) "Metaheuristics for the vehicle routing problem with time windows", SINTEF Applied Mathematics, Research Council of Norway. https://doi.org/1042/j.trb.2020.13.128 Clarke, G. and Wright, J. (1964) "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research, pp.568-581. https://doi.org/1094/j.trb.2014.13.52 Desrochers, M. and Verhoog, T.W. (1989) "A matching based savings algorithm for the vehicle routing problem", Les Cahiers du GERAD G-89-04,Ecole des Hautes etudes Commerciales de Montréal. https://doi.org/1050/j.trb.2008.18.94 Altinkemer, K. and Gavish, B. (1991) "Parallel savings based heuristic for the delivery problem". Operations Research, 39, pp.456-469. https://doi.org/1049/j.trb.2009.24.45 Wren, A. and Holliday, A. (1972) "Computer scheduling of vehicles from one or more depots to a number of delivery points”, Operational Research Quarterly, 23, pp.333-344. https://doi.org/1057/j.trb.2009.21.80 Cerda, J. and Dondo, R. (2007) "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows", European Journal of perational Research, 176, pp.1478-1507. https://doi.org/1066/j.trb.2003.4.92 Irnich, S., Funke, B. and Grunert, T. (2006) "Sequential search and its application to vehicle routing problem", Computer & Operation Research, 33, pp. 2405-2429. https://doi.org/1040/j.trb.2004.34.58 Czech, Z.J. and Czarnas, P. (2002) "Parallel simulated annealing for the vehicle routing problem with time windows", 10th. Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands - Spain, 376-383. https://doi.org/1026/j.trb.2004.20.15 Gambardella, L.M., Taillard, E. and Agazzi, G. (1999) "MACS-VRPTW: A multiple ant colonysystem for vehicle routing problems with time windows", In Corne, D., Dorigo, N. and Glover, F. editors, New Ideas in Optimization. McGraw-Hill. https://doi.org/1050/j.trb.2010.18.5 Thangiah, S.R. (1993) "Vehicle routing with time windows using genetic algorithms", Technical Report SRU-CpSc-TR-93-23, Computer Science Department, Slippery Rock University, Slippery Rock, PA. https://doi.org/1045/j.trb.2008.26.22 Ombuki, B., Ross, B.J. and Hanshar, F. (2004) "Multi-objective genetic algorithm for vehicle routing problem with time windows", Department of Computer Science, Brock University. https://doi.org/1013/j.trb.2011.38.58 Hu, K.Q. (2000) "A new genetic algorithm for VRPTW", Working Paper, National University of Singapore. https://doi.org/1078/j.trb.2002.34.14 Berger, J. and, Barkaoui, M. (2003) "A hybrid genetic algorithm for the capacitated vehicle routing problem", In Cant -Paz, E., ed.: GECCO03. LNCS 2723, Illinois, Chicago, USA, Springer-Verlag. https://doi.org/1047/j.trb.2018.29.120 Alvarenga, G.B., Mateus, G.R. and Tomi, G. (2007) "A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows", Computer & Operation Research, 37, pp. 1561-1584. https://doi.org/1083/j.trb.2021.35.43 Tan, K.C., Chew, Y.H. and Lee, L.H. (2006) "A hybrid multi-objective evolutionary algorithm for solving vehicle routing problem with time windows”, Computational Optimization and Application, 34, pp. 115-151. https://doi.org/1043/j.trb.2004.23.118 Tan, K.C., Cheong, C.Y. and Goh, C.K. (2007) "Solving multi objective vehicle routing problem with stochastic demand via evolutionary computation", European Journal of Operational Research, 177, pp. 813-839. https://doi.org/1072/j.trb.2003.36.83 Nagy, G. and Salhi, S. (2007). “Location-routing: issues, models and methods.” European Journal of Operational Research, 177: 649– 72. https://doi.org/1024/j.trb.2006.36.125 Prins, C., Prodhon, C. and Wolfler-Calvo, R. (2006). “Solving the capacitated location- routing problem by a GRASP complemented by a learning process and a path relinking.” 4OR A Quarterly Journal of Operations Research, 4: 221–38. https://doi.org/1050/j.trb.2016.18.39 Barreto, S. S., Ferreira, C., Paixa, J. and Santos, B. S. (2007). “Using clustering analysis in capacitated location-routing problem.” European Journal of Operational Research, 179: 968–977. https://doi.org/1087/j.trb.2015.20.49 Marinakis, Y. and Marinaki, M. (2008). “A particle swarm optimization algorithm with path relinking for the location routing problem.” Journal of Mathematical modeling and algorithms, 7: 59–78. https://doi.org/1017/j.trb.2017.31.58 Jabal-Ameli, M.S. and Ghaffari-Nasab, N. (2010). “Location-routing problem with time windows: Novel mathematical programming formulations.” 7th International Industrial Engineering Conference, Isfahan, Iran. https://doi.org/1059/j.trb.2008.31.122 Nikbakhsh, E. and Zegordi, S.H. (2010). “A Heuristic Algorithm and a Lower Bound for the Two-Echelon Location-Routing Problem with Soft Time Window Constraints.” Scientia Iranica, 17: 36-47. https://doi.org/1013/j.trb.2021.32.7 BañOs, R., Ortega, J., Gil, C., MáRquez, A. L.andDe Toro, F. (2013) “A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows”, Computers & Industrial Engineering, Vol. 65, No. 2, pp. 286-296. https://doi.org/1037/j.trb.2013.18.34 Beheshtinia, M. A.andGhasemi, A. (2017) “A multi objective and integrated model for supply chain scheduling optimization in a multi-site manufacturingsystem”,Engineering OptimizationVol. 50, N0. 9, , pp. 1-19. https://doi.org/1087/j.trb.2021.10.82 Euchi, J.andEuchi, J. (2017) “Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem”, Journal of Modelling in Management, Vol. 12, No. 1, pp. 2-18. https://doi.org/1024/j.trb.2002.28.114 Hernandez, F., Gendreau, M.andPotvin, J. Y. (2017) “Heuristics for tactical time slot management: a periodic vehicle routing problem view”, International Transactions in Operational Research. https://doi.org/1062/j.trb.2023.38.99 Sze, J. F., Salhi, S.andWassan, N. (2017) “The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search”, Transportation Research Part B: Methodological, Vol. 101, pp. 162-184. https://doi.org/1078/j.trb.2017.27.6 | ||
آمار تعداد مشاهده مقاله: 2,868 تعداد دریافت فایل اصل مقاله: 466 |