ارائه یک مدل برنامه‌ریزی خطی عدد صحیح برای حل مسئله مسیریابی وسایل نقلیه ناوگان ثابت ناهمگون چندکالایی با امکان تحویل چندبخشی

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

نویسندگان

1 دانشجوی دکتری، گروه مدیریت صنعتی، دانشکده علوم اداری و اقتصاد، دانشگاه اصفهان، اصفهان، ایران.

2 دانشیار، گروه مدیریت، دانشکده علوم اداری و اقتصاد، دانشگاه اصفهان، اصفهان، ایران.

10.22059/imj.2024.374742.1008144

چکیده

هدف: هدف این مطالعه ارائه مدلی برای حداقل‌سازی هزینۀ کل حمل‌ونقل در مسائل مسیریابی وسایل نقلیه ناوگان ثابت ناهمگون چندمحصولی با امکان تحویل چندبخشی است. این نوع مسائل، معمولاً در آن دسته از شرکت‌های تولیدی مشاهده می‌شود که محصولات گوناگون (با اندازه‌ها یا وزن‌های مختلف) تولید می‌کنند و آن‌ها را توسط ناوگان ناهمگونی از وسایل نقلیه و به‌طور مداوم به خرده‌فروشی‌ها و سایر مشتریان خود می‌فرستند. در این مسائل، انواع مختلفی از وسایل نقلیه با ظرفیت‌های بارگیری متفاوت به‌طور محدود در دسترس است و هر یک از آن‌ها هزینه ثابت به‌کارگیری و هزینه متغیر سفر مختص به خود را دارد. مسائل مسیریابی وسایل نقلیه با سه ویژگی هم‌زمان ناوگان ناهمگون، چند محصولی و امکان تحویل چندبخشی با وجود اهمیت بالایی که دارند تا پیش از این چندان مطالعه نشده است.
روش: یک مدل برنامه‌ریزی خطی عدد صحیح محض، برای حل مسئله مسیریابی وسایل نقلیه‌ای توسعه یافته است که شامل ویژگی‌های تحویل چندبخشی، چند محصولی و ناوگان ناهمگون ثابت است. این مدل با انتخاب تعدادی از وسایل نقلیه از میان ناوگان حمل‌ونقل و تعیین محصولاتی که باید در هر یک از آن‌ها بارگیری شود، مشخص‌کردن مسیر حرکت، ترتیب ملاقات مشتریان توسط هر وسیلۀ نقلیه و اینکه هر وسیلۀ نقلیه چه محصولاتی را به کدام مشتری تحویل می‌دهد، توانسته است هزینه کل حمل‌ونقل، یعنی مجموع هزینه‌های ثابت، هزینه‌های متغیر سفر و هزینه‌های توقف در محل مشتریان را به حداقل برساند. برای تعیین ترتیب ملاقات مشتریان، از یک روش ابتکاری در مدل‌سازی استفاده شده است.
یافته‌ها: نتایج محاسباتی حاصل از حل تعدادی از مسائل تصادفی با استفاده از روش پیشنهادی نشان می‌دهد که این روش قادر است برای مسائلی در مقیاس کوچک (تا ۱۵ مشتری) در زمان مناسبی به جواب بهینه دست یابد و برای مسائلی با مقیاس متوسط (با ۲۰ تا ۳۰ مشتری) در محدوده زمانی یک ساعت جواب قابل قبولی پیدا کند. همچنین با استفاده از مدل پیشنهادی برای مسائل در مقیاس بزرگ‌تر (تا ۵۰ مشتری) در محدودۀ زمانی یک ساعت، جواب‌های شدنی به‌دست آمد و این جواب‌ها، به مرور زمان بهبود یافتند. از میان پارامترهای مسئله، تعداد مشتریان بیشترین تأثیر را روی زمان حل مسئله داشته است و پس از آن، به‌ترتیب تعداد انواع محصولات و تعداد وسایل نقلیه، زمان حل مسئله را تحت تأثیر قرار می‌دهد.
نتیجه‌گیری: با توجه به نتایج حاصل از این مطالعه، مدل ارائه شده می‌تواند به‌عنوان ابزاری مؤثر برای بهینه‌سازی هزینۀ حمل‌ونقل محصولات، در مسائل مسیریابی وسایل نقلیه با ویژگی‌های هم‌زمان تحویل چندبخشی، چند محصولی و ناوگان ناهمگون استفاده شود. این مدل قادر است به‌صورت مناسب و بهینه، به حل مسائل مختلف در مقیاس‌های کوچک و متوسط بپردازد که این امر می‌تواند به بهبود کارایی و کاهش هزینه‌های حمل‌ونقل در شرکت‌های تولیدی کمک کند. انتظار می‌رود طراحی مدل‌های فراابتکاری برپایۀ منطق مدل برنامه‌ریزی ریاضی پیشنهادی، ضمن افزایش سرعت حل مسئله، بتواند به دستیابی به جواب نزدیک به بهینه و قابل قبول برای مسائل با مقیاس بزرگ‌تر کمک کند.

کلیدواژه‌ها

موضوعات

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

An Integer Linear Programming Model for the Heterogeneous Fixed Fleet Vehicle Routing Problems with Multiple Products and Split Deliveries

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

  • Abolfazl Momeni 1
  • Majid Esmaelian 2
  • Dariush Mohamadi Zanjarani 2
1 Ph.D. Candidate, Department of Industrial Management, Faculty of Administrative Sciences and Economics, University of Isfahan, Isfahan, Iran.
2 Associate Prof., Department of Management, Faculty of Administrative Sciences and Economics, University of Isfahan, Isfahan, Iran.
چکیده [English]

Objective
This study aims to propose a model to minimize the total transportation cost in Heterogeneous Fixed Fleet Vehicle Routing Problems with Multi-products and Split Deliveries. This type of vehicle routing problem is commonly encountered in manufacturing companies that produce various products (with different sizes or weights) and distribute them continuously to retail stores and other customers using a heterogeneous fleet of vehicles. In these problems, different types of vehicles with varying loading capacities are available in limited numbers, each with its own fixed and variable (travel) costs.Despite their high importance, vehicle routing problems that involve a heterogeneous fleet, multiple products, and split deliveries have not been extensively studied.
 
Methods
A pure integer linear programming model is developed to address the problem. The proposed model aims to minimize the total transportation cost, including fixed costs, variable (travel) costs, and stopping costs at destinations. The model selects several vehicles from the fleet and determines the products to be loaded in each one. It then establishes the route for each vehicle and specifies which products each vehicle delivers to which customer. An innovative modeling technique is employed to determine the sequence in which vehicles meet customers.
Results
The computational results from solving 32 instances of random problems using the proposed method demonstrate its effectiveness. For small-scale problems (up to 15 customers), the method can achieve optimal solutions within a reasonable time frame (ranging from 1 to 2000 seconds, depending on the problem size). For medium-scale problems (20 to 30 customers), it can find acceptable solutions within 3600 seconds. Additionally, for larger-scale problems (up to 50 customers), feasible solutions were obtained and improved over time within a one-hour limit (3600 seconds). Among the problem parameters, the number of customers has the greatest impact on the problem-solving time, followed by the number of product types and the number of vehicles.
 
Conclusion
The results of this study indicate that the proposed model is an effective approach for optimizing transportation costs in vehicle routing problems characterized by split deliveries, multiple products, and heterogeneous fleets. The model proves to be a robust and efficient solution for small to medium-scale problems, significantly enhancing operational efficiency and reducing transportation costs for manufacturing companies. It is anticipated that developing meta-heuristic models based on the proposed mathematical programming framework will not only accelerate problem-solving but also facilitate the attainment of near-optimal and satisfactory solutions for larger-scale issues.

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

  • Heterogeneous fleet
  • Multi-product
  • Split delivery
  • Vehicle routing problem
  • Pure integer linear programming

مراجع

اصغری‌زاده، عزت‌اله؛ جعفرنژاد، احمد؛ زندیه، مصطفی؛ جویبار، سبحان (1396). تبیین الگوی مدل‌سازی ترافیک در مسائل مسیریابی خودرو مبتنی بر پارادایم حمل‏ونقل سبز (مورد مطالعه: شرکت زمزم). مدیریت صنعتی، 9(2)، 217-244.
جوانفر، الهام؛ رضائیان، جواد؛ شکوفی، کیوان؛ مهدوی ایرج (1396). مسئله مکان‌یابی مسیریابی انبارهای عبوری چند محصولی با در نظرگرفتن وسایل نقلیه ناهمگن ظرفیت دار و قابلیت برداشت و تحویل در چند بار در یک شبکه زنجیره تأمین چند سطحی. مهندسی حمل‌ونقل، 8(4)، 603-627.
رحمان‌دوست، افروز؛ حافظ الکتب، اشکان؛ رحمانی پرچیکلایی، بیژن؛ عزیزی، امیر (1402). طراحی مدل ریاضی چندهدفه استوار مبتنی بر پایداری برای مسیریابی وسایل نقلیه جمع‌آوری پسماند شهری. مدیریت صنعتی، 15(4)، 680-709.
شاهبندرزاده، حمید؛ نجمی، محمد حسن؛ عطایی، علیرضا (1396). ارائه مدل ریاضی بر اساس مسئله مسیریابی خودرو ظرفیت‌دار با پنجره‏های زمانی برای جمع‌آوری زباله. مدیریت صنعتی، 9(1)، 147-166.
کاظمی، محبوبه؛ محمدی زنجیرانی، داریوش؛ اسماعیلیان، مجید (1400). مدل چندهدفه مکان‌یابی مراکز بارانداز عبوری، زمان‏بندی و مسیریابی هم‏زمان وسایل نقلیه، تحت بخش‌بندی تقاضا برای اقلام فاسدشدنی. مدیریت صنعتی، 13(4)، 606-633.
مهدوی اصل، وحید؛ خادمی زارع، حسن؛ حسینی نسب، حسن (1391). ارائه یک مدل ریاضی و روش ابتکاری جدید برای حل مسئله مسیریابی وسایل نقلیه چند قرارگاهی و چند محصولی با وسایل نقلیه متفاوت. نشریه بین‌المللی مهندسی صنایع و مدیریت تولید، 23(3)، 303-315.
 
References
Asawarungsaengkul, K., Rattanamanee, T. & Wuttipornpun, T. (2013). A multi-size compartment vehicle routing problem for multi-product distribution: Models and solution procedures. International Journal of Artificial Intelligence, 11(13A), 237-256.
Asgharizadeh, E., Jafar Nejad, A., Zandieh, M. & Jooybar, S. (2017). Explaining the Approach of Traffic Modeling to Vehicle Routing Issues Based on the Paradigm of Green Transportation (Case Study: ZAMZAM Co). Journal of Industrial Management, 9(2), 217-244. (in Persian)
Ayyildiz, E., Şahin, M. C. & Taskin, A. (2023). A Multi Depot Multi Product Split Delivery Vehicle Routing Problem with Time Windows: A Real Cash in Transit Problem Application in Istanbul, Turkey. Journal of Transportation and Logistics, 7(2), 213-232.
Belfiore, P. & Yoshizaki, H. T. Y. (2009). Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal of Operational Research, 199(3), 750-758.
Belfiore, P. & Yoshizaki, H. T. Y. (2013). Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Computers & Industrial Engineering, 64(2), 589-601.
Chowmali, W. & Sukto, S. (2020). A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery. Decision Science Letters, 9(1), 77-90.
Coelho, L. C. & Laporte, G. (2013). A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem. International Journal of Production Research, 51(23-24), 7156-7169.
Dantzig, G. B. & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Fahmy, S. A. & Gaafar, M. L. (2023). Modelling and solving the split-delivery vehicle routing problem, considering loading constraints and spoilage of commodities. International Journal of Systems Science: Operations & Logistics, 10(1), 2074566.
Golden, B., Assad, A., Levy, L. & Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1), 49-66.
Hasani-Goodarzi, A. & Tavakkoli-Moghaddam, R. (2012). Capacitated vehicle routing problem for multi-product cross-docking with split deliveries and pickups. Procedia-Social and Behavioral Sciences, 62, 1360-1365.
Javanfar, E., Rezaeian, J., Shokofi, K. & Mahdavi, I. (2017). Multi product cross-docking location vehicle routing problem with capacity hetrogeneous vehicles and split pickup and delivery in multi level supply chain. Journal of Transportation Engeneering, 8(4), 603–627. (in Persian)
Kabadurmus, O. & Erdogan, M. S. (2023). A green vehicle routing problem with multi-depot, multi-tour, heterogeneous fleet and split deliveries: a mathematical model and heuristic approach. Journal of Combinatorial Optimization, 45(3), 89.
Kazemi, M., Mohamadi Zanjirani, D. & Esmaelian, M. (2021). The Multi-Objective Locating Model for Cross-Docking Centers and Vehicle Routing Scheduling With Split Demands for Perishable Products. Industrial Management Journal, 13(4), 606-633. (in Persian)
Lenstra, J. K. & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
Levy, D., Sundar, K. & Rathinam, S. (2014). Heuristics for routing heterogeneous unmanned vehicles with fuel constraints. Mathematical Problems in Engineering, 1-12. DOI:10.1155/2014/131450
Mahdavi Asl, V., Khademi Zare, H. & Hoseyni 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, 23(3), 303-315. (in Persian)
Matthopoulos, P.P. & Sofianopoulou, S. (2019). A firefly algorithm for the heterogeneous fixed fleet vehicle routing problem. International Journal of Industrial and Systems Engineering, 33(2), 204-224.
Mjirda, A., Jarboui, B., Macedo, R., Hanafi, S. & Mladenović, N. (2014). A two phase variable neighborhood search for the multi-product inventory routing problem. Computers & Operations Research, 52, 291-299.
Moin, N. H., Salhi, S. & Aziz, N. (2011). An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem. International Journal of Production Economics, 133(1), 334-343.
Munari, P., Dollevoet, T. & Spliet, R. (2016). A generalized formulation for vehicle routing problems. arXiv preprint arXiv:1606.01935.
Ozfirat, P. M. & Ozkarahan, I. (2010). A constraint programming heuristic for a heterogeneous vehicle routing problem with split deliveries. Applied Artificial Intelligence, 24(4), 277-294.
Qiu, Y., Wang, L., Xu, X., Fang, X. & Pardalos, P. M. (2018). Formulations and branch-and-cut algorithms for multi-product multi-vehicle production routing problems with startup cost. Expert Systems With Applications, 98, 1-10.
Rahmandoust, A., Hafezalkotob, A., Rahmani Parchikolaei, B. & Azizi, A. (2023). Designing a Multi-Objective Stable Mathematical Model for Routing Municipal Waste Collection Vehicles. Industrial Management Journal, 15(4), 680-709. (in Persian)
Salhi, S., Sari, M., Saidi, D. & Touati, N. (1992). Adaptation of some vehicle fleet mix heuristics. Omega, 20(5-6), 653-660 .
Shahabi-Shahmiri, R., Asian, S., Tavakkoli-Moghaddam, R., Mousavi, S. M. & Rajabzadeh, M. (2021). A routing and scheduling problem for cross-docking networks with perishable products, heterogeneous vehicles and split delivery. Computers & Industrial Engineering, 157, 107299.
Shahbandarzadeh, H., Najmi, M.H. & Ataei, A. (2017). A Mathematical Model Based on Capacitated Vehicle Routing Problem with Time Lapses for Garbage Collection. Journal of industrial management, 9(1), 147-166. (in Persian)
Surjandari, I., Rachman, A., Dianawati, F. & Wibowo, R. (2011). Petrol delivery assignment with multi-product, multi-depot, split deliveries and time windows. International Journal of Modeling and Optimization, 1(5), 375.
Wang, Z., Li, Y. & Hu, X. (2015). A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint. Computers & Industrial Engineering, 89, 162-176.
Yakıcı, E. & Karasakal, O. (2013). A min–max vehicle routing problem with split delivery and heterogeneous demand. Optimization Letters, 7(7), 1611-1625.
Yilmaz Eroglu, D., Caglar Gencosman, B., Cavdur, F. & Ozmutlu, H. C. (2014). Introducing the MCHF/OVRP/SDMP: Multicapacitated/Heterogeneous Fleet/Open Vehicle Routing Problems with Split Deliveries and Multiproducts. The Scientific World Journal, (1), 515402. DOI:10.1155/2014/515402
Zhao, J., Dong, H. & Wang, N. (2023). Green split multiple-commodity pickup and delivery vehicle routing problem. Computers & Operations Research, 159, 106318.
مدیریت صنعتی
دوره 16، شماره 3
1403
صفحه 334-360

فایل ها

هم رسانی

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

آمار