حل مسئلۀ مسیریابی وسایل نقلیه و راهبرد حمل‏و‏نقل متقاطع با الگوریتم جست‏وجوی پراکنده

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

نویسندگان

1 استادیار گروه مدیریت صنعتی، دانشکدۀ اقتصاد، مدیریت و حسابداری دانشگاه یزد، یزد، ایران

2 کارشناس‎ارشد مدیریت صنعتی، دانشکدۀ اقتصاد، مدیریت و حسابداری دانشگاه یزد، یزد، ایران

چکیده

یکی از روش‏های بهبود جریان فیزیکی در زنجیرۀ تأمین، حمل‌و‌نقل متقاطع است که  روش مناسبی برای کاهش موجودی و بهبود رضایت مشتریان معرفی شده است. از سویی، مسئلۀ مسیریابی وسیلۀ نقلیه از مهم‏ترین مسائل در مدیریت توزیع، با هدف یافتن مسیرهای بهینه برای توزیع محموله‏های مختلف به‎شمار می‎رود‏. بنابراین، پژوهش حاضر با هدف مسیریابی وسایل نقلیه با حمل‌و‌نقل متقاطع در شرکت بیسکویت شادی ‏مهرگان مهریز انجام گرفت و مسئلۀ مد نظر با الگوریتم جست‌وجوی پراکنده حل شد. با توجه به یافته‏های پژوهش، فاصله و هزینۀ بهینه با استفاده از الگوریتم جست‌وجوی پراکنده برابر 11438 و 10186655 شد که نسبت به وضعیت موجود شرکت به‌ترتیب‌ 54/30 درصد و 7/6 درصد بهبود یافت. همچنین برای سنجش کارایی، نتایج با روش نزدیک‏ترین همسایه مقایسه شد. بنابراین، می‏توان نتیجه گرفت که الگوریتم جست‌وجوی پراکنده، جواب‏های خوبی برای این مسئله به‌دست می‏آورد و زمان تأخیر نیز کاهش می‏یابد.

کلیدواژه‌ها


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

Solving of vehicle routing problem with cross docking by scatter search algorithm

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

  • Ali Morovati Sharifabadi 1
  • Mahnaz Bavarkob 2
1
2
چکیده [English]

One of methods of improvement of the material flow is cross docking that In is considered as a good method to reduce inventory and improve customer satisfaction. Too, the vehicle routing problem is one of the important problems in distribution management and its goal is to find paths for delivering various cargos. Therefore, this study was conducted in order to vehicle routing problem with Cross-docking in MEHRIZ SHADI MEHREGAN Biscuit and the problem was solved with a scatter search Algorithm. The findings concluded that the optimal distance by scatter search Algorithm was equal to 11,438 km that Compared with the current status that improved respectively of 30.54%. The optimal cost by scatter search algorithm was equal to 10186655 that Compared with the current status and improved 6.7%. Therefore, can be concluded that the scatter search Algorithm is a good solution to this problem.

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

  • Supply Chain
  • Vehicle routing problem
  • cross docking
  • scatter search algorithm
Amiri, M. & Kheirandish, M. (2000). A Model for Improving Supply Chain Management in Foolad Ardabil Company. Management Development Journal, 14 (71): 4-17. (in Persian)
Apte, UM. & Viswanathan, S. (2000). Effective Cross Docking for Improving Distribution Efficiencies. International Journal of Logistics: Research and Applications. 3 (3): 291–302.
Aras, N., Aksen, D. & Tagrl Tekin, M. (2011). Selective Multi-Depot Vehicle Routing Problem with pricing. Transportation Research Part C, 19(5): 866-884.
Belle, J.V., Valckenaers, P. & Cattrysse, D. (2012). Cross docking: State of the Art. Omega, 40(6): 846-827.
Boloori Arabani, A., Zandieh, M. & Fatemi Gomi, S-M-T. (2011). Multi Objective Genetic-Based Algorithms for A Cross-Docking Scheduling Problem. Applied soft computing, 11(8): 4954-4970.
Calvete, H.I., Galé, C., Oliveros, M.J. & Snchez-Valverde, B. (2007). A Goal Programming Approach to Vehicle Routing Problems with Soft Time Windows Star, Open. European Journal of Operational Research, 177(3): 1720–1733.
Cook, R.L., Gibson B. & Mac Curdy, D. (2005). A Lean Approach to Cross-Docking. Supply Chain Management, 9(2): 54-59.
Dantzig, G. & Ramser, J. (1959). The Truck Dispatching Problem. Journal of Management Science, 6(1): 80-91.
Dareh Miraki, M. (2013). A new heuristic algorithm to solve vehicle routing problem, operations research journal and its applications, 4(35):1-7.
(in Persian)
Dehbari, S., Purrusta, A., Naderi, M., Ghobadian, E. & Tavakoli Moghadam, R. (2013). Multi objective vehicle routing with probable service time and fuzzy demand under time window constraints, Operations Research in Applications, 4 (35): 85-106. (in Persian)
Dondo, R. & Cerda, J. (2013). A Sweep-Heuristic Based Formulation for the Vehicle Routing Problem with Cross Docking. Computers and Chemical Engineering, 48(2013): 1-54.
Dondo, R., Mendez, C.A. & Cerda, J. (2011). The Multi-Echelon Vehicle Routing Problem with Cross Docking in Supply Chain Management. Computers and chemical engineering, 35(12): 3002-3024.
Dondo, R.G. & Cerda, J. (2009). A Hybrid Local Improvement Algorithm for Large-Scale Multi-Depot Vehicle Routing Problems with Time Windows. Computers and Chemical Engineering, 33(2): 513–530.
Eydi, A.R. & Abdorahimi, H. (2012). Model and solution approach for multi-period and multi-depot vehicle routing problem with flexibility in specifying the last depot of each rout. International journal of industrial engineering & production management, 23 (3): 333-349. (in Persian)
Fu, Z., Eglese, R. & Li, L.Y.O. (2008). A Unified TABU Search Algorithm for Vehicle Routing Problems with Soft Time Windows. Journal of the Operational Research Society, 59(5): 663–673.
Gary, M. & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP Completeness. Freeman, San Francisco.
Hosseini Nasab, S., Safaadeh, M. & Mamduhi, A. (2012). A method for routing optimization in public transportation integrating bus network and extremist bus, Transportation Engineering, 4 (8): 303-316. (in Persian)
Jia, H., Li, Y., Dong, B. & Ya, H. (2013). An improved tabu search approach to vehicle routing problem. Social and behavioral sciences, 96 (6): 1208-1217.
Kinnear, E. (1997). Is There Any Magic in Cross-Docking? Supply Chain Management: An International Journal, 2 (2): 49-52.
Laporte, G. (1992). The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European journal of operational research, 59(3): 345-358.
Lee, Y.H., Jung, J.W. & Lee, K.M. (2006). Vehicle Routing Scheduling for Cross-Docking in the Supply Chain, Computers & Industrial Engineering, 51(2):  247–256.
Li, Y., Lim, A. & Rodrigues, B. (2004). Cross-Docking: JIT Scheduling with Time Windows. Journal of the Operational Research Society, 55 (12): 1342–51.
Lio, C. J., Lin, Y & Shih, S.C. (2010). Vehicle Routing with Cross-Docking in the Supply Chain, expert systems with applications, 37(10): 6868-6873.
Liu, R. & Jiang, Z. (2012). The close-open mixed vehicle routing problem. European Journal of Operational Research, 220(2): 349–360.
Macedo, R., Alves, C., Carvalho, J.M.V.D; Clautiaux, F. & Hanafi, S. (2011). Solving the Vehicle Routing Problem with Time Windows and Multiple Routes Exactly Using a Pseudo-Polynomial model. European Journal of Operational Research, 214(3): 536–545.
Mahdavi-Asl, V., Khademi-Zare, H. & Hosseini-Nasab, H. (2012). Offering a mathematical model and heuristic method for solving multi-depot and multi-product vehicle routing problem with heterogeneous vehicle, International journal of industrial engineering & production management, 23 (3): 303-315. (in Persian)
Marinakis, Y. & Marinaki, M. (2010). A Hybrid Genetic – Particle Swarm Optimization Algorithm for the Vehicle Routing Problem. Expert Systems with Applications, 37(2): 1446–1455.
Mester, D., Braysy, O. & Dullaert, W. (2007). A Multi-Parametric Evolution Strategies Algorithm for Vehicle Routing Problems. Expert Systems with applications, 32(2): 508-517.
Mohammadi Zanjirani, D. & Asadi Aghageri, M. (2009). Designing Mathematical Model for Transportation Routing in Supply Chain, With a Case Study in DonarKhazar Company. Journal of industrial management, 1 (3): 119-136. (in Persian)
Moon, I., Lee, J.H. & Seong, J. (2012). Vehicle Routing Problem with Time Windows Considering Overtime and Outsourcing Vehicles. Expert Systems with Applications, 39(18): 13202–13213.
Mosheiov, G. (1998). Vehicle Routing with Pickup and Delivery: Tour Partitioning Heuristics. Computers & industrial engineering, 34(3): 669-684.
Mousavi, S.M. & Tavakili-Moghadam, R. (2013). A hybrid simulated annealing for location and routing scheduling problems with cross docking in the supply chain. Journal of manufacturing systems, 32 (2): 335-347.
Novoa, C. & Storer, R. (2009). An Approximate Dynamic Programming Approach for the Vehicle Routing Problem with Stochastic Demands. European Journal of Operational Research, 196(2): 509–515.
Olfat, L. & Barati, M. (2012). An Importance-Performance Analysis of Supply Chain Relationships Metrics in Small and Medium Sized Enterprises in Automotive Parts Industry. Journal of industrial management. 4 (2): 21-42.
Osvald, A. & Strin, L.Z. (2008). A Vehicle Routing Algorithm for the Distribution of Fresh Vegetables and Similar perishable Food. Journal of food engineering, 85(2): 285-292.
Pandelis, D.G., Kyriakidis, E.G. & Dimitrakos, T.D. (2012). Single Vehicle Routing Problems with A Predefined Customer Sequence Compartmentalized Load and Stochastic Demands. European Journal of Operational Research, 217(2): 324–332.
Polimeni, A. & Vitetta, A. (2012). An approach for solving vehicle routing problem with link cost variability in the time. Procedia - Social and Behavioral Sciences, 39: 607 – 621.
Razavi, M., Sokhakian, M.A. & Ziarati, K. (2010). A Meta heuristic algorithms based on ant colony system for solving multi depots location-routing problem with multiple using of vehicle. Journal of industrial management, 3 (6): 17-38. (in Persian)
Razmi, J. & Yousefi, M. (2012). A new mathematical model for schools service routing problem and solving by proposed algorithm. Journal of Industrial engineering, 46 (2): 185-194.(in Persian)
Razmi, J., Hale, H. & Ezati, B. (2011). Designing a dynamic model Transit routing and its solution by ant algorithm, Industrial Engineering and Sharif Management, 26 (2): 65-70. (in Persian)
Reimann, M., Doerner, K. & Hartl, R.F. (2004). D-Ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem. Computers & operations research, 31(4): 563-591.
Salehipour, A. & Sepehri, M.M. (2013). A new model for mobile repairer problem based mixed integer programming. International journal of industrial engineering & production management, 23 (3): 284-292. (in Persian)
Santos, F.A., Mateus, G.R. & Cunha, A.S.D. (2011). A Branch-and-Price Algorithm for a Vehicle Routing Problem with Cross-Docking. Electronic Notes in Discrete Mathematics, 37: 249–254.
Sepehri, M. & Hosseini Motlagh, S. (2009). Optimize routing of transportation systems in automated warehouses, Journal of transportation research, 5 (2): 127-138. (in Persian)
Sepehri, M.M. & Satak, M. (2005). Modeling and solving of different vehicle routing problem with carrying load in the back in with unequal capabilities. Journal of Transportation, 1 (1): 23-33.(in Persian)
Shahin Moghadam, S,. Fatemi Ghomi, S.M.T. & Karimi, B. (2014). Vehicle routing scheduling problem with cross docking and split deliveries, Computers & chemical engineering, 69 (3): 98-107.
Soltani, R. & Sajjadi, S.J. (2010). Scheduling Trucks in Cross-Docking Systems: A Robust Meta-Heuristics approach. Journal of Transportation Research Part E, 46(5): 650-666.
Sung, C.S. & Song, S.H. (2003). Integrated Service Network Design for a Cross-Docking Supply Chain Network. Journal of the Operational Research Society, 54(12): 1283-1295.
Taghavifard, M., Sheikh, K. & Shahsavari, A., (2008). Modified ant colony algorithm for the vehicle routing problem with time windows. International journal of industrial engineering & production management, 20 (2): 23-30. (in Persian)
Taillard, E., Badeau, P., Gendreau, M., Guertin, F. & Potvin, J.Y. (1997). A TABU Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science, 31(2): 170–186.
Tan, K.C., Lee, L.H., Zhu, Q.L. & Ou, K. (2001). Heuristic Methods for Vehicle Routing Problem with Time Windows. Artificial Intelligence in engineering, 15 (3): 281-295.
Tan, W.F., Lee, L.S., Majid, Z.A. & Seow, H.V. (2012). Ant Colony Optimization for Capacitated Vehicle Routing Problem. Journal of Computer Science, 8 (6): 846-852.
Tang, J., Zhang, J. & Pan, Z. (2010) A Scatter search for solving vehicle routing problem with loading cost. Expert Systems with Applications, 37 (6): 4073-4083.
Tareghian, H.R., Farahi, M.H. & Modaresi, T. (2009). Determining the number of kanbans by scatter search algorithm, science journal of Shahid Chamran university of Ahvaz, 3 (20): 24-35. (in Persian)
Tavakoli Moghadam, R., Alinaghian, M. & Salamat-Bakhsh, A.R. (2010). A new mathematical programming model for a vehicle routing problem in a competitive environment: a real case study. Journal of transportation research, 4 (21): 311-323. (in Persian)
Tavakoli Moghadam, R., Alinaghian, M., Norouzi, N. & Salamat-Bakhsh, A. (2011). Solving a new vehicle routing problem considering safety in hazardous materials transportation: a real-case study. Journal of transportation engineering, 3 (7): 223-239. (in Persian)
Tavakoli Moghadam, R., Alinaghian, M., Norouzi, N. & Salamat-Bakhsh, A. (2012). Solving a new model for vehicle routing problem with safety consideration in dangerous material transportation, Transportation engineering, 3 (7): 223-237. (in Persian)
Tavakoli Moghadam, R., Joulai, F. & Ghandi Bidgoli, S. (2009). Solving of parallel machine scheduling with weighted earliness-tardiness by multi objective scatter search. Journal of faculty of engineering (university of Tehran), 42 (7): 923-934. (in Persian)
Tavakoli-Moghadam, R., Rabbani, M., Shariat, M.A. & Safaee, N. (2006). Vehicle routing problem with soft time windows using an integrated meta-heuristic algorithm. Journal of faculty of engineering (university of Tehran), 40 (4): 469-476. (in Persian)
Tizroo, A., Azar, A., Ahmadi, R. & Rafeei, M. (2011). Modeling agility of supply chain case study: Zobahan co. journal of industrial management, 3 (7): 17-36.
Vahdani, B. & Zandieh, M. (2010). Scheduling Trucks in Cross-Docking Systems: Robust Meta-Heuristics. Computers & Industrial Engineering, 58 (1): 12–24.
Vincius, W.C.M., Geraldo, R.M. & Thiago, F.N. (2014). Iterated local search heuristics for the vehicle routing problem with Cross-Docking. Expert systems with applications, 41 (16): 7495-7506.
Wang J. (2009). Apply particle swarm optimization to solve the vehicle routing problem with cross docking in the supply chain. Department of Industrial Management - National Taiwan University of Science and Technology.
Wen, M., Larsen, J., Clausen, J., Cordeau, J-F. & Laporte, G. (2009). Vehicle Routing with Cross- Docking. Journal of the Operational Research Society, 60 (12): 1708–1718.
Yousefi Khoshbakht, M. & Rahmati, F. (2011). An improved ant colony system for solving the vehicle routing problem with simultaneous pickup and delivery, Journal of transportation research, 8 (2): 183-198. (in Persian)
Yousefi Khoshbakht, M., Didehvar, F., Rahmati, F. & Sedighpoor, M. (2012). An effective imperialist competitive algorithm for solving the open vehicle routing problem, Journal of transportation research, 9 (1): 83-95.
(in Persian)