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

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

نویسندگان

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

2 کارشناس ارشد مهندسی صنایع، دانشگاه سمنان، سمنان، ایران

چکیده

هدف این مقاله، بررسی زمان‌بندی وسایل نقلیه در یک زنجیره تأمین چند‌محصولی با در نظر گرفتن رابطۀ متقابل بین بخش حمل­ونقل و بخش تولید است. سطح یکپارچگی در نظر گرفته شده در زنجیره تأمین، شامل شرکت سازندۀ محصولاتِ نهایی و تأمین­کنندگان ردۀ اول است که یک ناوگان حمل­ونقل آنها را به یکدیگر مرتبط می‌کند. هدف، نحوۀ تخصیص سفارش‌ها به تأمین­کنندگان و تعیین توالی ساخت آنها در هر تأمین­کننده به‌همراه تخصیص سفارش‌ها به وسایل نقلیه و تعیین توالی حمل آنها است؛ به‌قسمی که مجموع زمان تحویل سفارش‌ها حداقل شود. این مسأله تاکنون در ادبیات موضوع بررسی نشده است. ابتدا مدل ریاضی مسأله، ارائه می­شود. پس از نشان‌دادن NP-Hard بودن مسأله، برای حل آن یک الگوریتم ترکیبی - تلفیقی جدید از دو الگوریتم ژنتیک و شبیه­سازی تبرید - با نام شبیه­سازی تبرید جمعیتی (PSA) ارائه می‌شود. برای اعتبارسنجی الگوریتم PSA نتایج آن با نتایج الگوریتم شبیه­سازی تبرید و توسعۀ الگوریتم DGA مقایسه می­شود .این دو الگوریتم، نزدیک‌ترین مسأله در ادبیات موضوع به مسأله بررسی‌شده در این مقاله هستند. افزون بر این با ریلکس‌کردن برخی فرضیات، نتایج الگوریتم PSA با نتایج الگویتم DGA مقایسه می‌شود. نتایج مقایسه‌ها نشان‌دهندۀ برتری عملکرد الگوریتم PSA در همۀ مقایسه‌ها است. همچنین مقایسۀ نتایج الگوریتم PSA برای مسائل با ابعاد کوچک، نشان‌دهندۀ کارایی مناسب آن است.

کلیدواژه‌ها


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

Vehicle Routing in a Multi-product Supply Chain using Populated Simulated Annealing Algorithm

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

  • Mohammad Ali Beheshtinia 1
  • Ali Borumand 2
  • Mohammad Reza Taheri 2
  • Hesam Babaei 2
1 Assistant Professor, Industrial engineering department, Semnan University, Semnan, Iran
2 MA of industrial engineering, Semnan University, Semnan, Iran
چکیده [English]

This paper aims to examine the scheduling of vehicles in a multi-product supply chain regarding to the mutual relationship between the transportation and the manufacturing units. The integration level in the supply chain consists of a manufacturer and its first tier suppliers, which are linked by a transportation fleet. The problem is determining orders allocation to the suppliers, orders production sequence at the suppliers, orders allocation to the vehicles, and orders transportation priority, in order to minimize the sum of orders delivery time. This issue has not been discussed in the literature, so far. At first, the mathematical model of the problem is presented, then the NP-Hardness of the problem is demonstrated. For solving the problem, a new combination of genetic algorithm and simulated annealing algorithm, named as Populated Simulated Annealing algorithm (PSA) is proposed. For verifying the PSA, its results are compared to results of simulated annealing algorithm (SA) and developed version of DGA algorithm, proposed for the nearest problem in the literature to our problem. Furthermore, relaxing some hypothesis, the results of PSA are compared to DGA results. All of the comparisons show that PSA is more efficient than the other algorithms. Finally, comparison of PSA with exact solution for small size problems demonstrates its proper efficiency.
Introduction: The vehicle routing problem (VRP) is one of the most important issues in the world's industry, which, today, is highly regarded because of its practical applications in industries.
We examined the scheduling of production and transportation in a multi-product supply chain considering the interaction between the transportation and the manufacturing units. The supply chain consists of two parts.The first part is suppliers which are located in different geographical locations handling specific orders. The second part consists of several vehicles that collect the orders processed by suppliers and deliver them to the company. The considered transportation system is similar to vehicle routing problem (VRP). The difference between VRP and the problem in this research is that in VRP the amount of goods that should be transported, and is known. However, as it is assumed in this research, the allocation of orders and sequencing of their manufacturing are the decisive variables. Problem objectives are determining the allocation of orders to suppliers, orders production sequence, orders allocation to the vehicles, and transportation sequence, in order to minimize the summation of the orders completion time. Innovation of this paper is as follows:

A combination of production scheduling problem in suppliers and VRP in a supply chain when the supplier can’t process all orders.
Developing a new mathematical model for solving the problem.
Three algorithms have been proposed to solve this problem, including: developed DGA, simulated annealing algorithm (SA), and a new combination of these two algorithms, which is named populated simulated annealing algorithm (PSA).

A supply chain consists of a set of suppliers, producers and distributors that cooperate with each other in order to satisfy customers’ need. A supply chain determines all levels in which the value is added to a product. VRP has several versions. In this study, it is considered that a number of heterogeneous vehicles are collecting orders from suppliers located in different geographical locations.
With considering the integration level of companies in the supply chain, researches can be divided into four categories:
1)        Researches that examine the relationship between manufacturers and suppliers;
2)        Researches that examine the relationship between manufacturers and distributors or customers;
3)        Researches that focus on the relationship between some manufacturers together (Outsourcing);
4)        Researches that consider combination of the above scenarios.
5)         
Considering the examination level of supply chain, researches have been divided in two categories: 1) Researches that have a macro planning and coordinating in the completion chain; 2) Researches that have an operational scheduling and coordinating in the supply chain.
The literature shows that the combination of VRP with scheduling problem in supply chains possessing constraint on allocating the orders to suppliers has not been studied.
 
Materials and Methods:Step 1) Developing a new mathematical model for this problem.
Step 2) Developing the PSA algorithm to solve the problem.
Step 3) Validating PSA algorithm as follows:
       Step 3-1) Producing random samples with different structures.
Step 3-2) Comparing PSA with SA and developing DGA.
Step 3-3) Comparing PSA with DGA after adding a relaxation assumption.
Step 3-4) Solving small samples with PSA and comparing with exact solution.
Step 4) Doing sensitivity analysis on the three main parameters. (Number of orders, Number of suppliers, and Number of vehicles)
 
Results and Discussion: The results of the comparison demonstrate that the populated simulated annealing algorithm shows better results than the other two. This method shows that the combination of genetic algorithm and simulated annealing in this specific way can adapt advantages of both methods. The results show that the mean of answers is increased by increasing number of orders,. With increasing suppliers, the objective function is improved because the orders allocate to different suppliers and the delivery time is decreased. By increasing orders processing time, the objective function value gets worse because the waiting time for processing orders is increased. By increasing transport times, the average solution is increased. It’s because vehicles should spend more time along the way.
 
Conclusion
This issue has not been discussed in the literature. At first, the mathematical model is presented and then it is shown that the problem is NP-Hard. Three algorithms have been proposed to solve this problem: Developed DGA, Simulated Annealing Algorithm, and a new combination of these two algorithms, which is named Populated Simulated Annealing Algorithm. Random samples with different structures is created and solved by these three algorithms. Also, relaxation of distance assumption between suppliers that are in the same location has been discussed at Zegordi and Beheshti Nia (2009) and is compared with PSA which shows that PSA is more efficient than the other algorithms. Finally, the comparison of PSA with exact solution for small size problems demonstrates its proper efficiency.
 
References
Archetti, C., Jabali, O., & Speranza, M. G. (2015). Multi-period vehicle routing problem with due dates. Computers & Operations Research, 61, 122-134.
Ray, S., Soeanu, A., Berger, J., & Debbabi, M. (2014). The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. Knowledge-Based Systems, 71, 238-265.
Zegordi, S., & Beheshti Nia, M. (2009). Integrating production and transportation scheduling in a two-stage supply chain considering order assignment. The International Journal of Advanced Manufacturing Technology, 44(9-10), 928-939. doi: 10.1007/s00170-008-1910-x

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

  • Routing
  • Genetic Algorithm
  • Simulated Annealing
  • Scheduling

مقدمه

مسأله مسیریابی وسایل نقلیه (VRP[i]) یکی از مهم‌ترین مسائل موجود در صنایع جهان است و امروزه به‌علت کاربردهای واقعی در مسائل صنعتی توجه زیادی به آن شده است. اولین بار این مسأله را دانتزیک و رامسر مطرح کردند. این مسأله، در زمینه‌های حمل­ونقل، توزیع و لجستیک مهم است (دانتزیگ و رامسر[ii]، 1959). در سال‌های اخیر، برای کاهش قیمت­ها و افزایش رقابت‌پذیری، فشار زیادی بر صنایع وارد شده است. دراین‌راستا، مدیران از روش­های مختلفی چون برنامه­ریزی و زمان‌بندی تولید استفاده کرده­اند و تمرکز آنها به درون بنگاه برای کاهش هزینه­ها بوده است؛ ولی سازمان­ها برای ادامۀ حیات و بقا، ناچار به تعامل با سایر سازمان­ها هستند؛ از‌این‌رو برای کاهش هزینه­ها باید دیدی فر‌ا‌سازمانی داشت. بنابراین بررسی هم‌زمان نحوۀ مسیریابی و زمان‌بندی حمل­ونقل با زمان‌بندی تولید، توجه بسیاری از مدیران را به خود جلب کرده است؛ زیرا این دو نوع زمان‌بندی بر یکدیگر تأثیر متقابل دارند و تصمیماتی که در یکی از این دو مسأله گرفته می­شود، روی تصمیمات مسائل دیگر اثرگذار است. ازاین‌رو این مقاله، زمان‌بندی تولید و حمل­ونقل در یک زنجیره تأمین را با در نظر گرفتن تأثیر متقابل این دو برهم بررسی می‌کند. زنجیره تأمین شامل مجموعه­ای از تأمین­کنندگان، تولیدکنندگان و توزیع‌کنندگان است که هدف واحد آنها، برطرف‌کردن نیاز مشتری است. یک زنجیره تأمین، تعیین‌کنندۀ تمام سطوحی است که در یک کالای تولیدی، ارزش افزوده ایجاد می‌کند ( چانگ و لی[iii]، 2004). از سوی دیگر حالت چند‌محصولی نیز در این زنجیره تأمین در نظر گرفته شده است. حالت چندمحصولی یعنی یک تأمین­کننده قادر به پردازش تمام سفارش‌ها نیست و با‌توجه‌به ماهیت سفارش‌ها، تنها بخشی از آنها را پردازش می‌کند. مسأله VRP دارای نسخه‌های متعددی است. در این پژوهش حالتی از آن در نظر گرفته می­شود که تعدادی وسایل نقلیه ناهمگن وظیفۀ جمع آوری سفارش‌ها را از تأمین‌کنندگان در نقاط جغرافیایی متفاوت بر عهده دارند. تفاوت مسأله بررسی‌شده در این پژوهش با مسأله VRP این است که در مسأله VRP فرض می‌شود مقدار کالایی که باید از هر تأمین­کننده حمل شود، مشخص است؛ اما در مسأله بررسی‌شده در این پژوهش، فرض می‌شود تخصیص سفارش‌ها به تأمین­کنندگان و تعیین توالی تولید آنها، جزءِ متغیرهای تصمیم مسأله است.

زنجیره تأمین بررسی‌شده در این مقاله مربوط به یک زنجیره تأمین دو‌بخشی است. بخش نخست شامل تأمین‌کنندگان است. این تأمین­کنندگان در نقاط مختلف جغرافیایی مستقر هستند و هریک توانایی تولید برخی از سفارش‌ها را دارند. بخش دوم متشکل از چند وسیلۀ نقلیه است که باید سفارش‌های پردازش‌شده نزد تأمین­کنندگان را جمع­آوری کنند و به شرکت سازنده تحویل دهند. شکل 1 نشان‌دهندۀ شمای کلی زنجیره تأمین بررسی‌شده، است. در این زنجیره، 5 سفارش، 4 تأمین­کننده و 2 وسیله نقلیه در نظر گرفته شده است. در این شکل، تخصیص سفارش‌ها به تأمین‌کنندگان، وسایل نقلیه و مسیر حرکت وسایل نقلیه مشخص شده است. این ساختار در صنایعی نظیر خودروسازی، محصولات الکترونیکی و صنایع شیمیایی وجود دارد.

هدف مسأله، تعیین چگونگی تخصیص سفارش‌ها به تأمین­کنندگان، تعیین ترتیب پردازش سفارش‌ها تخصیص‌یافته به یک تأمین­کننده، تخصیص سفارش‌ها به وسایل نقلیه و تعیین ترتیب حمل به هر وسیلۀ نقلیه است؛ به قسمی که مجموع زمان تحویل سفارش‌ها حداقل شود.

1

 

2

3

 

4

 

1

2

5

 

1

 

4

 

2

 

3

 

تأمین­کننده :

 

 

وسیله نقلیه :

 

 

سفارش :

 

 

راهنما

 

تولیدکننده :

 

 


شکل 1- حالت کلی زنجیرۀ تأمین

 

در ادامه در بخش 2، ادبیات در حوزۀ زنجیره تأمین مرور می­شود. در بخش 3 دربارۀ مسأله بررسی‌شده به‌تفصیل توضیح داده می‌شود و مسأله با یک مدل برنامه­ریزی عدد صحیح مختلط فرموله می­شود. در بخش 4 روش­های حل پیشنهادی ارائه‌می‌شوند. در بخش 5 الگوریتم شبیه­سازی تبرید جمعیتی با الگوریتم ژنتیک و شبیه­سازی تبرید کلاسیک مقایسه می‌شود و درنهایت در بخش 6 جمع­بندی و زمینه­هایی برای پژوهش‌های آتی فراهم می‌شود.

 

مرور ادبیات

تاکنون پژوهش‌های متعددی در زمینۀ ترکیب زمان‌بندی تولید و حمل­ونقل در زنجیره تأمین انجام شده است. وانگ و چنگ[iv] (2009) مسأله زمان‌بندی تأمین و تحویل سفارش‌ها را با هدف حداقل‌کردن بازۀ ساخت بررسی کرده‌اند. در مسأله آنها وسیلۀ نقلیه با ظرفیت محدود و زمان حملِ ثابت، سفارش‌ها را از انبار تأمین­کنندگان به کارخانه و وسیله‌ای دیگر از کارخانه به مشتریان انتقال می‌دهد. آنها نشان دادند مسأله از نوع NP-hard است و یک الگوریتم ابتکاری برای حل آن ارائه کرده‌اند. یمیر و دمیرلی[v] (2010) یک الگوریتم ژنتیک برای زمان‌بندی در یک زنجیره تأمین دو مرحله­ای ارائه کرده­اند. آنها یک مدل برنامه­ریزی خطی عدد صحیح مختلط[vi] نیز برای بهینه­سازی تأمین و مونتاژ قطعات و زمان‌بندی توزیع، ارائه کرده‌اند. اسکولز ریتر و همکاران[vii] (2010) یکپارچگی تولید و حمل­ونقل در یک زنجیره تأمین عمومی را بررسی و یک مدل ریاضی برای حل مسأله ارائه کرده‌اند. تابع هدف مسأله آنها حداقل‌کردن مجموع هزینه­های دیرکرد سفارش‌ها، هزینه­های پردازش، هزینه‌های نگهداری سفارش‌ها و هزینه­های ثابت و متغیر حمل‌ونقل هستند. لئو و چن[viii] (2012) یکپارچگی مسیریابی، کنترل موجودی و زمان‌بندی را در یک زنجیره تأمین بررسی کرده‌اند و پس از مدل‌سازی ریاضی مسأله، الگوریتم جستجوی همسایگی برای حل آن ارائه کرده‌اند. تابع هدف مسأله، حداقل‌کردن مجموع هزینه­های موجودی، مسیریابی و استفاده از وسایل نقلیه است. مهرآوران و لجندران[ix] (2012) زمان‌بندی در محیط جریان‌کاری با زمان­های آماده­سازی وابسته به توالی را با دو تابع هدف حداقل‌کردن سفارش‌های نیمه‌ساخته و حداکثرکردن سطح سرویس بررسی کرده‌اند. آنها یک الگوریتم جستجوی ممنوع[x] برای حل مسأله، ارائه کرده‌اند. کو و وانگ[xi] (2012) مسأله مسیریابی چندنقطه­ای وسیلۀ نقلیه را با هزینۀ بارگیری بررسی کرده‌اند و روش جستجوی همسایگی متغیر را برای حل آن ارائه کرده­اند. روش آنها شامل سه مرحله است: مرحلۀ اول ایجاد یک روش تصادفی برای تولید جواب اولیه؛ مرحلۀ دوم، انتخاب تصادفی چهار اپراتور برای جستجو در جواب­های همسایگی و مرحلۀ سوم، ارائه معیارهای مشابه شبیه­سازی تبرید برای پذیرش پاسخ­های همسایگی است. عثمان و دمیرلی[xii] (2012) زمان‌بندی تحویل و اندازۀ انباشتۀ اقتصادی را در یک زنجیره تأمین سه‌مرحله­ای و چند‌محصولی بررسی کرده‌اند. این مراحل شامل تأمین­کنندگان ردۀ دوم، تأمین­کنندگان ردۀ اول و مونتاژکنندۀ قطعات هستند. آنها یک مدل جدید بر پایه مسأله تخصیص مضاعف برای مسأله ارائه کرده‌اند. مدل آنها، سیکل مشترکی را برای هماهنگی در پر ‌و‌ تخلیه‌شدن انبارها، تعیین می­کند. الریچ[xiii] (2013) یکپارچگی زمان‌بندی ماشین­آلات و مسیریابی وسایل نقلیه را با در نظر گرفتن پنجره­های زمانی مطالعه کرده است. در این پژوهش یک زنجیره تأمین دو‌مرحله­ای بررسی شده است. مرحلۀ نخست شامل یک محیط ماشین­های موازی[xiv] با زمان­های آمادگی وابسته به ماشین است. مرحلۀ دوم نیز شامل یک ناوگان وسایل نقلیه با ظرفیت­های حمل متفاوت است. کابرا و همکاران[xv] (2013) زمان‌بندی در زنجیره تأمین داروسازی را برای یک محیط چند‌مرحله­ای، چند‌محصولی و چند‌دوره­ای بررسی کرده‌اند. آنها زمان‌بندی را به‌صورت پیوسته در نظر گرفته و یک مدل برنامه­ریزی عدد صحیح مختلط برای آن ارائه کرده‌اند. آورباخ و بیسان[xvi] (2013) مسأله زمان‌بندی در یک زنجیره تأمین دوسطحی را بررسی و یک الگوریتم تخمینی برای آن ارائه کرده‌اند. در مسأله آنها قطع عملیات مجاز و تحویل سفارش‌ها به‌صورت دسته­ای در نظر گرفته شده است. تابع هدف، حداقل‌کردن مجموع جریان سفارش‌ها و هزینه­های تحویل کالاها در نظر گرفته شده است. رن و همکاران[xvii] (2013) یک زنجیره تأمین دو‌مرحله­ای را در نظر گرفتند. در این زنجیره، تعدادی تأمین­کننده، قطعات لازم برای یک مونتاژکننده را فراهم می­آورند. زمان تحویل هر محصول برابر حداکثر زمان تحویل قطعاتی است که تأمین­کنندگان برای مونتاژکننده فراهم می­آورند. توماس و همکاران[xviii] (2014) زمان‌بندی در زنجیره تأمین زغال سنگ را با چند فعالیت مستقل، بررسی کرده‌اند. در این مسأله، محدودیت­های منابع با هم در ارتباط هستند. مسأله آنها از دو زیرمسأله برنامه­ریزی و زمان‌بندی تشکیل شده است. آنها یک مدل ریاضی عدد صحیح مختلط برای مسأله، ارائه و از تکنیک تولید ستون[xix] برای حل آن استفاده کرده‌اند. ساویک[xx] (2014) ارتباط زمان‌بندی با انتخاب تأمین‌کنندگان را در حالت وجود ریسک­های قطع، بررسی و یک مدل برنامه­ریزی عدد صحیح مختلط و احتمالی برای مسأله ارائه کرده‌اند. در این پژوهش، فرض شده است تأمین­کنندگان در دو دستۀ­ داخل ناحیه تولید و خارج آن تقسیم­بندی شده­اند. تابع هدف، حداقل‌کردن هزینه­ها و افزایش سطح سرویس هستند. سالوارجاه و ژانگ[xxi] (2014) زمان‌بندی زنجیره ­تأمینی را بررسی کرده‌اند که در آن یک تولیدکننده، مواد نیمه‌ساخته را از تأمین­کنندگان در زمان­های متفاوت دریافت می‌کند و کالاهای تکمیل‌شده را به‌صورت دسته­ای به مشتریان تحویل می­دهد. تابع هدف مسأله آنها حداقل‌کردن مجموع وزنی جریان سفارش‌ها و هزینه­های تحویل دسته­ها هستند و برای حل آن یک الگوریتم ابتکاری پیشنهاد کرده‌اند. ری و همکاران[xxii] (2014) یک مسأله حمل‌ونقل چندانباری را با در نظر گرفتن چندین وسیلۀ حمل بررسی کرده­اند که امکان تحویل چند‌نوبتۀ کالا در آن وجود دارد. آنها یک مدل برنامه‌ریزی خطی جدید ارائه داده­اند. همچنین با ارائۀ یک الگوریتم ابتکاری، جوابی نزدیک به جواب بهینه به‌دست آورده‌اند. آرچتی و همکاران[xxiii] (2015) یک مسأله حمل­ونقلِ چند‌دوره­ای را با در نظر گرفتن تاریخ تحویل بررسی کرده­اند. هدف، یافتن مسیر بهینه برای وسایل نقلیه است؛ به‌گونه­ای که تمام هزینه­های حمل­ونقل، انبارداری، جریمه­ها، هزینه­های سرویس­دهی و ... حداقل شوند. آنها یک الگوریتم شاخه­وکران و یک تحلیل محاسباتی برای حل این مسأله ارائه دادند.

با در نظر گرفتن میزان یکپارچگی شرکت­ها در زنجیره تأمین، پژوهش‌های انجام‌شده به چهار دسته تقسیم می‌شوند. 1)‌ پژوهش‌هایی که رابطۀ شرکت‌های سازنده با تأمین­کنندگانشان را بررسی کرده‌اند؛ 2) پژوهش‌هایی که رابطۀ شرکت سازنده با توزیع­کنندگان یا مشتریانشان را بررسی کرده‌اند؛ 3) پژوهش‌هایی که رابطۀ چند شرکت سازنده را با یکدیگر بررسی کرده‌اند (برو‌ن‌سپاری[xxiv])؛ 4) پژوهش‌هایی که ترکیبی از حالت‌های بالا را در نظر گرفته‌اند.

از نظر سطح بررسی زنجیره تأمین، پژوهش‌های انجام‌شده به دو دسته تقیسم می‌شوند: 1) پژوهش‌هایی که به‌صورت کلان در زنجیره تأمین، برنامه­ریزی تولید[xxv] و هماهنگی را انجام داده‌اند. 2) پژوهش‌هایی که به‌صورت عملیاتی زمان‌بندی و هماهنگی را در زنجیره تأمین انجام داده‌اند. بررسی ادبیات موضوع نشان می­دهد، ترکیب مسأله VRPبا مسأله زمان‌بندی تولید در زنجیره تأمین در حالت وجود محدودیت در تخصیص سفارش‌ها به تأمین­کنندگان تاکنون بررسی نشده است.

نخعی و همکاران (1386) و ذگردی و بهشتی‌نیا (1388) در پژوهش خود یک زنجیره تأمین خودروسازی سه‌مرحله‌ای را بررسی کرده‌اند. این زنجیره تأمین شامل تأمین­کنندگان، ناوگان حمل و شرکت‌های سازندۀ محصول نهایی است. آنها مسأله را به‌صورت یکپارچه در نظر گرفته­اند و یک الگوریتم ژنتیک برای آن ارائه داده­اند. تفاوت اصلی پژوهش حاضر با این پژوهش‌ها این است که در مسائل آنها فرض شده است، همۀ تأمین­کنندگان در یک نقطه مستقر هستند و هر تأمین‌کننده توانایی پردازش هرنوع سفارشی را دارد. همچنین آنها از روش حل متفاوتی استفاده کرده‌اند.

مسأله ذگردی و بهشتی­نیا[xxvi] (2009) نزدیک‌ترین پژوهش به این پژوهش است. آنها در مسأله خود فرض کرده­اند، تأمین­کنندگان در نواحی مختلف جغرافیایی پراکنده شده­اند و زمان حمل­ونقل بین تأمین­کنندگان در یک ناحیه جغرافیایی، برابر صفر در نظر گرفته می­شود. همچنین فرض شده است حمل‌ونقل بین تأمین­کنندگانی که در نواحی مختلف جغرافیایی پراکنده­اند مجاز نیست. به‌عبارتِ‌دیگر، در مسأله آنها محاسبات حمل‌و‌نقل بین تأمین‌کنندگان انجام نمی­شود؛ یعنی مسأله مسیریابی وسایل نقلیه مطرح نیست. در این مقاله، مسأله آنها برای توسعه حالتی است که حمل­ونقل بین تمام تأمین‌کنندگان مجاز است و زمان­های حمل‌ونقل در نظر گرفته می‌شود‌؛ به‌عبارتی مسأله مسیریابی نیز در نظر گرفته می­شود. بررسی مقالات موجود در ادبیات موضوع نشان می­دهد، ترکیب مسأله VRPبا مسأله زمان‌بندی تولید در زنجیره تأمین در حالت وجود محدودیت در تخصیص سفارش‌ها به تأمین­کنندگان تاکنون بررسی نشده است. همچنین برای حل آن از یک الگوریتم ترکیبی با نام شبیه­سازی تبرید جمعیتی (PSA) استفاده می­شود. این الگوریتم، تلفیق جدیدی از دو الگوریتمِ ژنتیک (GA) و شبیه­سازی تبرید (SA) است.

جدول 1- دسته‌بندی مسائل در ادبیات موضوع زمان‌بندی در زنجیره تأمین

زمان

در نظر گرفتن ناوگان حمل‌و‌نقل

سطح یکپارچگی

مقاله

دارای افق زمانی

زمان پیوسته

زمان گسسته

خیر

بله

ترکیبی

تمرکز روی ساخت

توزیع کننده-سازنده

تامین­کننده-سازنده

*

 

 

*

*

 

 

 

Wang & Cheng, 2009

*

 

 

*

 

 

*

 

Scholz-Reiter et al., 2010

*

 

*

 

*

 

 

 

Yimer & Demirli, 2010

*

 

 

*

 

 

 

*

Liu & Chen, 2012

*

 

*

 

 

 

*

 

Mehravaran and Logendran, 2012

*

 

*

 

 

 

 

*

and Osman, 2012 Demirli

*

 

 

*

 

 

*

 

Kuo & Wang, 2012

*

 

*

 

 

 

*

 

Averbakh and Baysan, 2013

*

 

*

 

 

*

 

 

Kabra et al., 2013

*

 

 

*

 

 

 

*

Ullrich, 2013

*

 

*

 

 

 

 

*

Ren, Du, & Xu, 2013

*

 

 

*

 

 

 

*

Archetti, Jabali, & Speranza, 2015

*

 

*

 

 

 

 

*

Sawik, 2014

*

 

*

 

 

 

*

 

Selvarajah and Zhang, 2014

*

 

 

*

*

 

 

 

Zegordi & BeheshtiNia, 2009

*

 

 

*

*

 

 

 

نخعی و همکاران ، 1386

*

 

 

*

*

 

 

 

ذگردی و بهشتی­نیا ، 1388

*

 

 

*

 

 

 

*

پژوهش حاضر

 

بنابراین نوآوری‌های این مقاله به‌شرح زیر هستند:

  • تعمیم مسأله ذگردی (2009) در حالتی که حمل‌و‌نقل بین همه تأمین­کنندگان مجاز است و نباید زمان حمل بین تأمین­کنندگان را نادیده گرفت.
  • ارائه ترکیبی از مسأله VRP و زمان‌بندی تولید در تأمین­کنندگان یک زنجیره تأمین در حالتی که هر تأمین­کننده قادر به پردازش تمام سفارش‌ها نباشد.
  • توسعۀ یک مدل ریاضی جدید برای حل مسأله.
  • ارائه یک الگوریتم ترکیبی به‌نام الگوریتم شبیه­سازی تبرید جمعیتی (PSA[xxvii]) برای حل مسأله که تلفیق جدیدی از دو الگوریتم GA[xxviii] و SA[xxix] است و همگام­سازی دو الگوریتم مذکور با فرضیات این مسأله.

 

 

تعریف مسأله

در این بخش، ابتدا فرضیات مسأله تبیین و سپس مدل ریاضی مربوط به مسأله ارائه می­شود.

مفروضات مسأله: این مقاله به مسأله زمان‌بندی وسایل نقلیه در زنجیره تأمین چند‌محصولی تمرکز دارد. هدف آن، حداقل‌کردن مجموع زمان تحویل سفارش‌ها است. بخش اول از این زنجیره تأمینِ دو ‌بخشی، شامل مجموعۀ تأمین­کنندگان و بخش دوم، شامل ناوگان حمل­ونقل می­شود که وظیفه ارسال سفارش‌ها از تأمین­کنندگان به یک شرکت سازنده محصولات نهایی را بر عهده دارد.

تعاریف و مفروضات مسأله بررسی‌شده به‌شرح ذیل هستند:

  • تعداد n سفارش وجود دارد. m تأمین­کننده بدون محدودیت ظرفیت، این سفارش‌ها را پردازش می‌کنند. همچنین این n سفارش با l وسیلۀ نقلیه، جمع­آوری و به شرکت اصلی انتقال داده می‌شوند. هریک از این n سفارش دارای حجم یا وزن مشخصی هستند؛ اما ممکن است این حجم یا وزن با هم برابر نباشند.
  • تأمین­کنندگان در نقاط مختلف جغرافیایی قرار دارند و و فاصلۀ آنها نسبت به هم و نسبت به شرکت اصلی مشخص است. برای کاهش هزینه­های حمل­ونقل، وسایل نقلیه مجاز هستند سفارش‌ها را از تأمین­کنندگان در نواحی جغرافیایی مختلف بارگیری کنند. تأمین­کنندگان به‌علت داشتن تجهیزات تخصصی، توانایی پردازش تمامی سفارش‌ها را ندارند و فقط سفارش‌های خاصی را پردازش می‌کنند.
  • هر وسیلۀ نقلیه، پس از تحویل محموله به شرکت اصلی، از مسأله حذف نمی­شود و باید دوباره استفاده شود. سفارش‌هایی را که هربار با یک وسیلۀ نقلیه به شرکت اصلی تحویل داده می­شوند، یک محموله می‌گویند. هر محموله شامل کالاهای پردازش‌شدۀ چند تأمین­کنندۀ مختلف است. زمان تحویل به شرکت، برای سفارش‌های موجود در یک محموله، یکسان است. حداکثر محمولۀ هر وسیله در بیشترین حالت ممکن برابر با تعداد سفارش‌ها است؛ آن‌هم وقتی همۀ سفارش‌ها به یک وسیله نقلیه تخصیص یابد و این وسیله در هر محمولۀ خود یک سفارش را حمل کند.

سوال اصلی پژوهش به‌صورت زیر است:

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

سوالات فرعی پژوهش نیز به صورت زیر است:

  • اختصاص سفارش‌ها به تأمین­کنندگان چگونه باشد؟
  • توالی انجام سفارش‌های تخصیص‌یافته به هر تأمین­کننده چگونه باشد؟
  • نحوۀ تخصیص محموله­ها به وسائل چگونه باشد؟
  • نحوۀ تقسیم‌بندی سفارش‌های تخصیص‌یافته به هر وسیلۀ نقلیه به محموله‌های مختلف و مسیریابی حرکت آن چگونه باشد؟

شکل 2، یک جوابِ شدنی مسأله بررسی‌شده را نشان می­دهد؛ به‌طوری که دو وسیلۀ نقلیه مسئولِ جمع‌آوری سفارش‌های پردازش‌شده هستند. وسیلۀ نقلیه اول، ابتدا باید سفارش شماره 4 را نزد تأمین‌کننده چهارم بارگیری کند، سپس با‌توجه‌به ظرفیت باقی‌مانده، سفارش دوم نزد تأمین­کنندۀ اول را بارگیری کرده و به کارخانه سازندۀ محصولات نهایی تحویل دهد. همچنین وسیله نقلیۀ دوم باید سفارش‌های 1 و 5 نزد تأمین­کنندۀ سوم و سپس سفارش 3 نزد تأمین­کنندۀ دوم را بارگیری و به کارخانه تحویل دهد.

 

 

شکل 2- یک جواب شدنی از مسأله

 

مدل ریاضی مسأله: در این بخش مدل ریاضی عدد صحیح مختلط مسأله بیان می­شود. قبل از ارائه مدل ریاضی مسأله، ابتدا نمادهای استفاده‌شده معرفی می­شوند. مجموعۀ استفاده‌شده در مدل عبارت‌اند از:

- مجموعه‌ای شامل N سفارش، هر سفارش با اندیسi یا q نشان داده می­شود:

- مجموعه‌ای شامل Sتأمین­کننده، هر تأمین­کننده با اندیس s یا s' نشان داده می­شود:

- مجموعه‌ای شامل V وسیلۀ نقلیه، هر وسیلۀ نقلیه با اندیس m نشان داده می­شود:

- ممکن است هر وسیلۀ نقلیه نیز چندین محموله داشته باشد که اندیس آن با b نمایش داده می­شود:

- در هر محموله، اولویت بارگذاری سفارش‌ها با اندیس p نشان داده می­شود. بیشترین مقدار برای p برابر N است (وقتی همه سفارش‌ها به یک محموله از یک وسیلۀ نقلیه اختصاص یابد):

پارامترهای مسأله نیز عبارتند از:

- ظرفیت اشغالی توسط سفارش i ام: Voli

- ظرفیت حمل وسیلۀ نقلیه mام برحسب تعداد سفارش‌ها: Capm

- زمان پردازش سفارش i ام: pti

- مدت زمان تردد بین تأمین­کنندۀ s و کارخانه با وسیلۀ نقلیه m: ttTms

- مدت زمان تردد بین تأمین­کنندۀ s و s' با وسیلۀ نقلیه m:

- یک ماتریس با ابعاد N*S، اگر a(i,s) برابر 1 باشد به‌معنای مجاز‌بودن تخصیص سفارش i به تأمین­کنندۀ s است و بالعکس: A

- یک عدد بزرگ مثبت: M

متغیرهای تصمیم مدل نیز به‌صورت زیر هستند:

- زمان تکمیل سفارش i در مرحلۀتأمین­کنندگان: ci

- زمان تحویل سفارش iبه کارخانه: Di

- زمان بارگذاری سفارش i ام روی یکی از وسایل نقلیه به‌منظور حمل: Li

- وقتی وسیلۀ نقلیه m ام، آماده حمل سفارش i در bامین مأموریت خود است: avmbi

- اگر سفارش i ام به تأمین­کنندۀ s ام داده شود، برابر یک و در غیر این‌صورت برابر صفر است: xsi

- اگر در مرحلۀ تأمین­کنندگان سفارش i قبل از سفارش q قرار گیرد، برابر یک و در غیر این‌صورت برابر صفر است: yiq

- اگر اولویت حمل pاام در bامین حمل به وسیلۀ نقلیه m مربوط به سفارش iاام باشد برابر یک و در غیر ‌این‌صورت برابر صفر است: Umbip

مدل ریاضی مسأله به‌صورت زیر است:

(1)

 

 

(2)

   

(3)

   

(4)

   

(5)

   

(6)

   

(7)

   

(8)

   

(9)

m=1,2,...,V

b=1,2,…,N

p=1,2,…,N-1

 

(10)

m=1,2,...,V

b=1,2,…,N-1

 

(11)

   

(12)

i =1,2,...,N

 

(13)

   

(14)

   

(15)

   

(16)

   

(17)

   

 

     

 

 

   

 

مجموعه محدودیت 2 نشان می‌دهد، هر سفارش تنها باید به یک تأمین­کننده تخصیص داده شود. مجموعه محدودیت 3 نشان می‌دهد، هر سفارش باید تنها به یک وسیلۀ نقلیه و به یک محموله از آن تخصیص یابد. مجموعه محدودیت 4 نشان می‌دهد، یک سفارش نمی­تواند به بیش از یک موقعیت در محموله­ها و وسایل نقلیه تخصیص یابد. مجموعه محدودیت 5 تضمین می­کند، در هر محموله مجموع فضای اشغالیِ سفارش‌های تخصیص‌یافته به یک وسیلۀ نقلیه نباید از ظرفیت آن وسیلۀ نقلیه بیشتر شود. مجموعه محدودیت 6 زمان تکمیل هر سفارش در مرحلۀ تأمین­کنندگان را در نظر می­گیرد. مجموعه محدودیت 7 بیان می­کند، هر تأمین­کننده نمی­تواند در هر لحظه بیش از یک سفارش را پردازش کند. مجموعه محدودیت 8 مقداری از متغیرهای زاید را حذف می‌کند. مجموعه محدودیت 9 تضمین می­کند، اگر به اولویت p ام محمولۀ b ام از وسیلۀ نقلیه mاام سفارشی تخصیص نیابد، به اولویت p+1 ام آن محموله، سفارشی تخصیص داده نمی‌شود. مجموعه محدودیت 10 تضمین می­کند، اگر به محمولۀ b ام از وسیلۀ نقلیه m ام سفارشی تخصیص نیابد، به محمولۀ b+1 ام آن سفارشی تخصیص داده نمی‌شود. مجموعه محدودیت 11 و 12 نشان می‌دهند، زمان بارگذاری هر سفارش برابر بیشینۀ زمان تکمیل پردازشِ سفارش و زمان آماده‌بودن وسیلۀ نقلیه مرتبط برای حمل آن است.

مجموعه محدودیت 13 تعیین‌کنندۀ زمانِ آماده‌بودن یک وسیلۀ نقلیه برای حمل سفارشی است که به اولویت اولِ اولین محموله آن اختصاص یافته است. مجموعه محدودیت 14 تعیین‌ کنندۀ زمان آماده‌بودن یک وسیلۀ نقلیه برای حمل سفارشی است که به اولویت اولِ یک محموله اختصاص یافته است؛ زمان آماده‌بودن با‌توجه‌به زمان تحویل سفارش‌های محمولۀ قبلی، مقصد محمولۀ قبلی و زمان حمل تا تأمین­کنندۀ مرتبط، تعیین می‌کنند. مجموعه محدودیت 15تعیین کنندۀ زمان آماده‌بودن یک وسیلۀ نقلیه برای حمل سفارشی است که به یک محموله اختصاص یافته است؛ زمان ‌آماده‌بودن با‌توجه‌به زمان بارگذاری سفارش اولویتِ حمل قبلی و زمان حمل بین تأمین‌کنندگان مرتبط تعیین می­شود. مجموعه محدودیت 16 زمان تحویل یک سفارش را با‌توجه‌به زمان بارگذاری کلیۀ سفارش‌های متعلق به محموله خود و مقصد آن تعیین می­کنند. مجموعه محدودیت 17 از اختصاص سفارش‌ها به تأمین­کنندگان غیرمجاز جلوگیری می­کند.

در‌واقع زمان بارگذاری یک قطعه هنگامی اتفاق می‌افتد که سفارش نزد تأمین کننده آماده و وسیلۀ نقلیه به محل تأمین کننده رسیده است.

همان‌گونه که اشاره شد، Ci بیانگر زمان تکمیل سفارش i ام و Avmbiبیانگر زمان آماده‌بودن وسیلۀ نقلیه برای حمل سفارش مربوطه است. زمان بارگذاری واقعی سفارش i ام که با Li نشان داده می­شود، بزرگتر یا مساوی هر دو این متغیرها است. محدودیت‌های 11 و 12 بیانگر این نکته هستند.

چانگ و لی (2004) نشان می‌دهند، مسأله بررسی‌شده در حالتِ وجود یک وسیلۀ نقلیه، دو تأمین­کننده و بدون در نظر گرفتن فاصلۀ بین تأمین‌کنندگان، از نوع NP-hard است؛ بنابراین حالت تعمیم­یافتۀ مسأله شامل S تأمین­کننده و V وسیلۀ نقلیه از نوع NP-hard خواهد بود.

 

ارائه روش­های حل

برای حل مسأله مذکور، سه الگوریتم شامل الگوریتم ژنتیک، الگوریتم شبیه­سازی تبرید و الگوریتم ترکیبی به‌نام الگوریتم شبیه­سازی تبرید چند­جمعیتی (PSA) (تلفیقی جدید از الگوریتم­های ژنتیک و شبیه­سازی تبرید)، ارائه می­شوند.

الگوریتم GA: الگوریتم GA یک الگوریتم فرا ابتکاری است و در حل مسائل NP-hard استفاده می­شود. این الگوریتم جواب­‌های خوبی در زمان معقول ارائه می­دهد. ایدۀ اصلی الگوریتم ژنتیک از اصل تنازع بقاء موجودات گرفته شده است. این الگوریتم را جان هالند[xxx] در سال 1970 ارائه داده است.

گام­های الگوریتم فراابتکاری GA برای این مسأله به‌شرح ذیل است:

گام 1) ایجاد تعدادی جواب تصادفی( نسل اولیه[xxxi]).

گام 2) انجام عملگر­های تلفیق[xxxii] و جهش[xxxiii] برای تعدادی از جواب­های این نسل.

گام 3) انتخاب نسل بعدی با استفاده از عملگر انتخاب[xxxiv].

گام 4) اگر معیار خاتمه محقق شد، الگوریتم پایان می­یابد، در ‌غیر‌ این‌صورت به گام 2 بازگشته و این روند تکرار می­شود.

تعریف ساختاری مناسب برای رمزنگاری[xxxv] هر جواب به‌صورت یک کرومزوم، کلیدی­ترین عنصر در الگوریتم ژنتیک به‌منظور حل مسائل جدید است. به‌عبارت‌دیگر، اگرساختار کرومزومی در فضای ژنوتایپ[xxxvi] تعریف شود که معادل هر جواب در فضای فنوتایپ[xxxvii] باشد، حل مسأله با الگوریتم ژنتیک میسر است و بالعکس.

ساختار کرومزوم در الگوریتم ژنتیک ارائه‌شده، دو‌بُعدی است. بُعد عمودی، نشان­دهندۀ تأمین­کنندگان و وسایل نقلیه و بُعد افقی نشان­دهندۀ سفارش‌های تخصیص‌یافته و ترتیب آنها به هر‌یک از تأمین‌کنندگان و وسایل نقلیه است.

1

تأمین­کننده 1

5→3→2

تأمین­کننده 2

4

تأمین­کننده 3

4→1→3→5

وسیله نقلیه 1

2

وسیله­ نقلیه 2

شکل 3- سفارش­های تخصیص‌یافته و ترتیب آنها

 

به‌منظور توضیح بیشتر، فرض کنید 5 سفارش، 3 تأمین­کننده و2 وسیلۀ نقلیه وجود دارد و تخصیص سفارش­ها به تأمین­کنندگان و وسایل نقلیه، همچنین اولویت پردازش و حمل آنها به‌صورت شکل 1 است. آنگاه ساختار کرومزومی بیان‌کنندۀ تخصیصِ شکل 3، شکل 4 خواهد بود.

 

 

 

 

1

تأمین­کننده 1

 

5

3

2

تأمین­کننده 2

 

 

 

4

تأمین­کننده 3

4

1

3

5

وسیله­ی نقلیه 1

 

 

 

2

وسیله­ی نقلیه 2

شکل 4- ساختار کروموزوم در الگوریتم ژنتیک پیشنهادی

 

درصورت تخصیص سفارش‌ها بیش از ظرفیت وسیلۀ نقلیه به آن، برای وسیلۀ نقلیه مذکور تور (محموله) جدیدی ایجاد می­شود. نحوۀ تشکیل این تورهای جدید برای هر وسیلۀ نقلیه با الگوریتم زیر است:

گام 1- اولویت سفارش‌های اختصاص داده‌‌شده به وسیلۀ نقلیه مورد نظر را براساس ساختار کرومزوم در نظر بگیرید.

گام 2- سفارش با اولویت اول را به اولین تور اختصاص دهید.

گام 3- سفارشی که اولویت حمل اول را داشته و هنوز به محموله‌ها تخصیص نیافته است، در نظر بگیرید. اگر ظرفیت وسیلۀ نقلیه اجازه تخصیص سفارش مذکور را به تور فعلی می­دهد، این تخصیص را انجام دهید؛ در ‌غیر ‌این‌صورت، تور فعلی را بسته و تور جدیدی ایجاد کنید. این سفارش را به تور جدید تخصیص دهید و تور جدید را به‌جای تور فعلی در نظر بگیرید.

گام 4- اگر تمامی سفارش‌ها تخصیص داده‌شده به وسیلۀ نقلیه به تورها تخصیص یافته‌اند، الگوریتم را خاتمه دهید؛ در‌ غیر ‌این‌صورت به گام 2 بازگردید. هر وسیلۀ نقلیه پس از جمع‌آوری سفارش‌های یک تور، به کارخانه بازگشته و آنها را تحویل می‌دهد و دوباره برای جمع­آوری سفارش‌های تور بعدی عازم می­شود.

مانند سایر مسائل زمان‌بندی، درصورت تغییر در ورودی‌های مسأله، نظیر تعداد وسایل نقلیه، تعداد سفارش‌ها و .. مسأله جدید باید دوباره حل شود.

عملگر تلفیق: عمل تلفیق به‌صورت شکل 5 انجام می­شود. برای این کار ابتدا دو کرومزوم از چرخ رولت انتخاب می­شوند. سپس یک آرایه تصادفی صفر و یک تولید می­شود. تعداد سلول­های آن به‌اندازه تعداد سفارش‌ها هستند. سفارشی که در آرایۀ تولید‌شده، عدد صفر به آن تعلق گرفته، جایگاه خود را در کرومزوم فرزند از والد اول و سفارش با عدد یک جایگاهش را از والد دوم به ارث می­برد. اگر این جایگاه قبلا پر شده، سفارش به اولین سلول خالی سمت راست تخصیص می­یابد.

عملگر جهش: شکل 6 چگونگی عملگر جهش را نشان می­دهد. در این حالت با احتمال 0.5، بخش تأمین­کننده و یا وسیلۀ نقلیه انتخاب شده و دو سفارش به‌صورت تصادفی با هم تعویض می­شوند.

در عملگر تعویضِ استفاده‌شده، ابتدا یک عدد تصادفی بین 0 و 1 تولید می­شود. اگر عدد تصادفی تولید‌شده بین 0 و 5/0 باشد، 2 ژن را از تکۀ مربوط به تأمین­کنندگان انتخاب کرده و مکان این 2 ژن تعویض می­شود. در تخصیص جدید باید دقت داشت که تأمین­کننده می‌تواند سفارش تعویض‌شده را پردازش کند یا خیر. درصورت مثبت‌بودن جواب، روند کار ادامه پیدا می­کند؛ در ‌غیر ‌این‌صورت جریمۀ زیادی به تابع هدفِ این کرومزوم اختصاص داده می­شود. حال اگر عدد تصادفی تولید‌شده بین 5/0 و 1 باشد، 2 ژن را از تکۀ مربوط به وسایل نقلیه انتخاب کرده و مکان این 2 ژن تعویض می­شود.

 

 

شکل 5- عملگر تلفیق

 

 

شکل 6- عملگر جهش

 

با استفاده از روش تاگوچی پارامترهای الگوریتم GA به‌صورت جدول 2 تعیین شدند.

 

جدول 2- پارامترهای الگوریتم GA

مقدار

پارامتر

100

جمعیت اولیه

9/0

نرخ تلفیق

1/0

نرخ جهش

عدم بهبود بهترین عضو هر جمعیت در 20 تکرار متوالی

معیار خاتمه

 

الگوریتمSA: کریک پاتریک و وکی[xxxviii] (1983) الگوریتم شبیه­سازی تبرید را برای حل مسائل بهینه­سازی ترکیبی پیشنهاد کردند. این الگوریتم با الهام‌گرفتن از نحوۀ سرد‌‌شدن فلزات، مسائل مختلف را بهینه‌سازی می­‌کند. گام­های الگوریتم فرا ابتکاری SA برای این مسأله به شرح ذیل هستند:

گام 1- دمای اولیه، تابع سرمایش، شرط خاتمه و تابع احتمال پذیرش جواب­های بد (تابع بولتزمان) را تعیین کنید.

گام 2- یک جواب اولیه برای ورودی الگوریتم در نظر بگیرید.

گام 3- با استفاده از عملگر­ تعویض، تعداد K همسایگی­ برای جواب فعلی ایجاد کنید.

گام 4- اگر مقدار بهترین همسایگی به‌دست آمده از جواب فعلی بهتر باشد، آن را جایگزین جواب فعلی کنید؛ در‌ غیر ‌این‌صورت یک عدد تصادفی بین صفر و یک ایجاد کنید. اگر این عدد از مقدار تابع بولتزمان کمتر باشد، بهترین همسایگی را جایگزین جواب فعلی کنید؛ در غیر ‌این‌صورت آن را رد کنید. تابع بولتزمان به‌صورت  است، در آن ∆f میزان تفاوت تابع هدفِ بهترین همسایگی ایجاد‌شده و جواب فعلی وT میزان دما در هر مرحله است.

گام 5- با تابع سرمایش دما را کاهش دهید. دمای جدید به‌صورت Tnew=(𝛼)Told محاسبه می­شود.

گام 6- اگر معیار خاتمه محقق شد، الگوریتم پایان می­یابد، در ‌غیر ‌این‌صورت به گام 3 بازگردید.

با استفاده از روش تاگوچی پارامترهای الگوریتم SA به‌صورت جدول 3 تعیین شدند.

 

جدول 3- پارامترهای الگوریتم SA

مقدار

پارامتر

10000

دمای اولیه

10

دمای نهایی

7/0

α

20

K

رسیدن به دمای نهایی

معیار خاتمه

 

الگوریتمPSA: برای حل مسأله مذکور، از ترکیب دو الگوریتم قبلی، روشی جدید با نام PSA ارائه می­شود. گام­های الگوریتم PSA برای این مسأله به‌شرح ذیل هستند:

گام 1- پارامترهای الگوریتم نظیر اندازۀ جمعیت اولیه (PopSize)، تعداد همسایگی (K)، دمای اولیه، تابع سرمایش، شرط خاتمه و تابع احتمال پذیرش، جواب‌های بد (تابع بولتزمان) را تعیین کنید.

گام2- به‌اندازۀ جمعیت اولیه، تعدادی کرومزو­م­ تصادفی ایجاد کنید.

گام3- برای هر کرومزوم، K همسایگی­ با استفاده از عملگر­ تعویض، ایجاد کنید.

گام4- بهترین و بدترین جواب هر جمعیت همسایگی را پیدا کنید.

گام5- برای هر کرومزوم با استفاده از عملگر تلفیق بر روی بهترین همسایگی آن کرومزوم و بهترین همسایگی (PopSize-1) کرومزوم دیگر اجرا کنید. همین عمل را یک‌بارِ دیگر برای بدترین همسایگی­ها نیز انجام داده و جواب­های تولید‌شده را به جمعیت همسایگی همان جامعه اضافه کنید.

گام6- از بین کل همسایگی‌های ایجاد‌شده برای هر کرومزوم، اگر مقدار تابع هدف بهترین همسایگی از مقدار تابع هدف خود کرومزوم بهتر است، آن را جایگزین کرومزوم فعلی کنید؛ در ‌غیر ‌این‌صورت با ‌استفاده از تابع بولتزمان دربارۀ جایگزینی یا رد آن تصمیم­گیری کنید.

گام 7- با تابع سرمایش، دما را کاهش دهید.

گام 8- اگر معیار خاتمه محقق شد، الگوریتم را پایان دهید، در‌ غیر ‌این‌صورت به گام 3 بازگردید.

 

شبه کد الگوریتم PSA

1: Procedure populated simulated Annealing

2: for i=1:population size do

3:          pop(i)←produce feasible solution;

4:         fit(i)←pop(i) fitness;

5:          Globalbestfit=Inf;

6: end for

7: while T>=TF do

8:           for i=1:population size do

                        %% neighborhood population(i)

9:                     for j=1:neighborhood size do

10:                               g=1;

11:                               check=0;

12:                               while check==0 && g<=G do

13:                                           newpop(j,i)←pop(i) neighborhood;

14:                                           if newpop(j,i) is feasible do

15:                                                       check=1;

16:                                           end if

17:                                           g=g+1;

18:                               end while

19:                               if check==0 do

20:                               newpop(j,i)←produce feasible solution;

21:                               end if

22:                               newfit(j,i)←newpop(j,i) fitness;

23:                   end for

24:                   best(i)←best of neighborhood population(i);

25:                   bestfit(i)←best(i) fitness;

26:          worst(i)←worst of neighborhood pop(i);

27:       end for

28:       for i=1:population size do

29:                   kk=1;

30:                   for k =1: population size , k≠i do

31:                    crossover [best(i) & best (k)]

                          newpop(j+kk,i) , newpop(j+kk+1,i) ↵ ;

32:                    crossover [worst (i) & worst (k)]

                          newpop(j+kk+2,i) , newpop(j+kk+3,i) ↵ ;

33:                    kk=kk+4;

34:                   end for

35:       end for

36:       for i=1:population size do

37:                   newbest(i)←best of new neighbor pop(i);

38:                   newbestfit(i)←fitness of newbest(i);

39:                   if newbestfit(i)<fit(i) do

40:                               fit(i)←newbestfit(i);

41:                               pop(i)←newbest(i);

42:                               if fit(i)do

43:                                           Globalbestfit←fit(i);

44:                                           Globalbestpop←pop(i);

45:                               end if

46:                   else do

47:                               pr=exp(-(k*(newbestfit(i)-fit(i)))/T);

48:                               if random number ∈(0,1)do

49:                                           fit(i)←newbestfit(i);

50:                                           pop(i)←newbest(i);

51:                               end if

52:                   end if

53:       end for

54:       T=∝ ∈(0,1) × T;

55: end while

56: [Finalfit , index]=min(Globalbestfit);

57: Finalpop= Globalbestpop(index);

58: end procedure

 

با استفاده از روش تاگوچی پارامترهای الگوریتم PSA به‌صورت جدول 4تعیین شدند.

 

جدول 4- پارامترهای الگوریتم PSA

مقدار

پارامتر

10000

دمای اولیه

10

دمای نهایی

7/0

α

20

K

10

اندازۀ جمعیت اولیه

رسیدن به دمای نهایی

معیار خاتمه

 نتایج محاسباتی

در این بخش، اعتبار الگوریتم PSA سنجیده می‌شود. به‌این‌منظور، ابتدا نتایج حاصل از الگوریتم با الگوریتم SA و توسعۀ الگوریتم DGA ارائه‌شده در پژوهش ذگردی و بهشتی نیا (2009) برای مسأله بررسی‌شده در این پژوهش، مقایسه می­شود. این مقایسه به‌ازای مسائل تصادفی با ابعاد مختلف انجام می‌شود. الگوریتم SA ساختاری مشابه ساختار الگوریتم استفاده‌شده در PSA دارد؛ با این تفاوت که از یک جواب اولیه برای جستجوی فضای جواب استفاده می­کند.

در ادامه با ریلکس‌کردن فرضِ وجود زمان حمل‌های متفاوت بین تأمین‌کنندگانِ مختلف، مسأله را تبدیل به مسأله بررسی‌شده در پژوهش ذگردی و بهشتی نیا می‌کند و عملکرد PSA و DGA را با هم مقایسه می‌کند.

سپس نتایج به دست آمده از الگوریتم PSA برای مسائل با ابعاد کوچک با حل دقیق مقایسه می­شود. در انتها نیز حساسیت روی برخی پارامترهای اصلی مسأله، تحلیل می‌شود.

تولید مسائل تصادفی: برای مقایسۀ الگوریتم PSA با الگوریتم های GA و SA، ابتدا تعدادی مسائل تصادفی با ابعاد مختلف ایجاد و با هریک از این الگوریتم ها حل می­شوند. سپس با استفاده از آزمون فرض، عملکرد الگوریتم PSA با دو الگوریتم دیگر مقایسه می­شود. برای تولید مسائل تصادفی سه پارامتر اصلی مسأله شامل تعداد سفارش، تعداد وسیله نقلیه و تعداد تأمین­کننده انتخاب و برای هریک از آنها 3 حالت در نظر گرفته شد. برای سایر پارامترها نیز توزیع یکنواختی در نظر گرفته شد و مقادیر آنها از توزیع‌های مربوطه تعیین شد. جدول 5 پارامترهای مسأله و مقادیر در نظر گرفته شده برای هریک از آنها را نشان می­دهد.

 

جدول 5- مقادیر مختلف پارامترها

 

سطح پایین

سطح متوسط

سطح بالا

تعداد سفارش‌ها

10

50

100

تعداد تأمین­کنندگان

1

5

10

تعداد وسایل نقلیه

5

10

15

زمان پردازش سفارش‌ها

 

U [20 , 30]

 

زمان­های حمل

 

U [20 , 30]

 

حجم سفارش‌ها

 

U [1 , 5]

 

ظرفیت ماشین

 

U [5 , 20]

 

 

مقایسه با سایر الگوریتم­ها: از ترکیب حالات مختلف برای پارامترهای مسأله، 27 مسأله تصادفی ایجاد می‌شود. این 27 حالت در جدول 6 نشان داده شده‌اند. باتوجه‌به تصادفی‌بودن ماهیت الگوریتم­های فرا ابتکاری، ممکن است در هر‌بار اجرا، نتایج متفاوتی به ‌‌دست آید.

بنابراین برای انجام آزمون فرض، همۀ 27 مسأله شکل‌گرفته به تعداد 20 مرتبه با هر سه الگوریتم حل شده­اند. بهرای آزمون فرضِ تست برابری­ میانگین نتایجِ به ‌دست آمده از الگوریتم PSA با الگوریتم­های دیگر، از آزمون T استفاده شده است. به‌ازای هریک از 27 مسأله، دو آزمون فرض تشکیل می‌شود (در مجموع 54 آزمون). فرض‌های آزمون‌ها به‌صورت زیر هستند:

فرض H0: میانگین نتایج به ‌دست‌ آمده از PSA برابر با میانگین نتایج به ‌دست ‌آمده از SA (توسعه DGA) یکسان است.

فرض H1: میانگین نتایج به ‌دست ‌آمده از PSA کوچکتر از میانگین نتایج به ‌دست ‌آمده از SA (توسعه DGA) است.

سطح اطمینان همۀ آزمون­ها برابر با 95 درصد در نظر گرفته می­شود. در حالت‌هایی که فرض H0 رد شود؛ یعنی در آن حالت‌ها، عملکرد الگوریتم PSA بهتر از الگوریتمِ مقایسه‌شده است.

جدول 6 برای هریک از الگوریتم‌ها و به‌ازای هر‌حالت، مقادیر میانگین جواب‌ها، بهترین جواب و میانگین زمان‌های حل (بر حسب ثانیه) را نمایش می­دهد. همچنین در این جدول مقدار p-value حاصل از انجام آزمون‌های فرض نشان داده شده است. نتایج نشان می­دهد، در 73 آزمون از 74 آزمون انجام‌شده، مقدار p-value کمتر از 05/0 است. این نتیجه، برتری PSA را نسبت به دو الگوریتم دیگر، نشان می‌دهد.

 

جدول 6- نتایج آزمون فرض مقایسه PSA، SA و توسعه DGA

P-Value (PSA-DGA)

P-Value (PSA-SA)

توسعه DGA

SA

PSA

تعداد تأمین­کننده

تعداد وسیله نقلیه

تعداد سفارش

مسأله

Mean CPU

Time (Second)

Avrg

Best

Mean CPU

Time (Second)

Avrg

Best

Mean CPU

Time (Second)

Avrg

Best

0/0019

4E-04

10/49934

1242/214

940

0/2725

969/2

900

2/4955

923/425

894

5

1

10

1

0/0066

2E-05

12/98639

1167/667

822

0/2739

938/475

847

2/5418

882/55

837

10

1

10

2

0/0914

1E-05

15/0869

906

774

0/2795

884/825

830

2/5899

839/625

798

15

1

10

3

0/0014

6E-08

13/73476

805/3143

526/8

0/2619

620/675

571

2/6167

582/175

566

5

5

10

4

5E-06

3E-04

10/3199

557/35

510/2

0/2663

521/175

471

2/6520

491

470

10

5

10

5

ادامه جدول 6- نتایج آزمون فرض مقایسه PSA، SA و توسعه DGA

P-Value (PSA-DGA)

P-Value (PSA-SA)

توسعه DGA

SA

PSA

تعداد تأمین­کننده

تعداد وسیله نقلیه

تعداد سفارش

مسأله

Mean CPU

Time (Second)

Avrg

Best

Mean CPU

Time (Second)

Avrg

Best

Mean CPU

Time (Second)

Avrg

Best

0/0001

2E-06

8/516931

603/5538

479/4

0/2745

510/725

456

2/7087

460/75

447/5

15

5

10

6

0/0001

8E-06

8/420395

545/6

475/6

0/2734

547/9

488

2/7233

495/575

473/5

5

10

10

7

0/0012

2E-09

8/744494

526/2722

347/8

0/2744

471/1

432

2/7381

415/75

388/5

10

10

10

8

0/0128

6E-06

7/544638

461/9375

372/6

0/2776

461/8

399

2/7705

402/575

384/5

15

10

10

9

0

1E-07

49/78044

29940/15

28469

0/6544

19005/83

16411

6/5157

17110/6

16303/5

5

1

50

10

0

9E-07

56/48805

35206/95

33507

0/6986

19710

18463/5

6/9562

18433/8

17261

10

1

50

11

0

3E-04

56/94595

40666/35

37781

0/7542

22573/13

21173/5

7/4890

22042/6

21553

15

1

50

12

0

4E-05

46/73573

13754/79

12503/2

0/6854

11364/98

10508/5

6/8011

10631/4

10292

5

5

50

13

0

1E-07

46/3756

10032/36

9463/6

0/6905

7810/325

7270

6/8656

7213/625

6829/5

10

5

50

14

0

1E-04

48/31572

11311/82

10733/2

0/7280

6794/65

6325/5

7/2042

6396/45

6083

15

5

50

15

ادامه جدول 6- نتایج آزمون فرض مقایسه PSA، SA و توسعه DGA

P-Value (PSA-DGA)

P-Value (PSA-SA)

توسعه DGA

SA

PSA

تعداد تأمین­کننده

تعداد وسیله نقلیه

تعداد سفارش

مسأله

Mean CPU

Time (Second)

Avrg

Best

Mean CPU

Time (Second)

Avrg

Best

Mean CPU

Time (Second)

Avrg

Best

0

9E-05

47/59226

12306/77

11924/1

0/6934

9733/925

9220

6/8746

9321/3

8787/5

5

10

50

16

0

3E-06

47/40448

7658/14

7229/3

0/7010

6429

6081/5

7/0473

6139/4

5974

10

10

50

17

0

7E-06

41/37457

6434/675

6057/9

0/7272

5097/325

4811

7/2885

4878/975

4702/5

15

10

50

18

0

9E-05

136/5124

136043/7

129407

1/2172

89621/73

79775/5

12/2027

82594/35

78315/5

5

1

100

19

0

1E-06

151/9474

139136

132513

1/2883

75534/4

70795

12/8782

71508/75

67816

10

1

100

20

0

1E-05

153/4768

144074/6

138891

1/3844

76375

70830/5

13/8396

73036/28

70260

15

1

100

21

0

1E-05

140/3293

59201/69

57282

1/1823

48486/13

44248

11/8391

45882/18

43673/5

5

5

100

22

0

5E-08

134/3929

48223/57

46671/8

1/3165

32393/48

29371/5

13/2143

29876/3

28423

10

5

100

23

0

2E-06

135/3733

36763/84

35794/2

1/3683

26119/65

24847/5

13/6273

24582/2

23502

15

5

100

24

0

2E-06

155/521

51735/81

50087/7

1/2401

41799/38

39922

12/5001

39908/9

38165/5

5

10

100

25

0

2E-05

133/8641

32432/35

30418/1

1/3201

25379/78

23336

13/0454

24218/85

23383/5

10

10

100

26

0

3E-04

131/2939

26355/01

25251/6

1/3898

19855.98

18620/5

13/7473

19074/45

18565

15

10

100

27

اگر تأمین­کنندگان به چند ناحیۀ جغرافیایی تقسیم شوند، به‌نحوی که زمان­های حمل بین تأمین­کنندگان داخل یک ناحیه برابر صفر و زمان­های حمل بین تأمین­کنندگان نواحی مختلف برابر با عددی بسیار بزرگ باشد، مسأله تبدیل به مسأله در نظر گرفته شده شده در پژوهش ذگردی و بهشتی نیا (2009) می‌شود. همان‌گونه که اشاره شد، آنها برای حل مسأله از یک الگوریتم ژنتیک به نام DGA استفاده کرده‌اند. برای مقایسات بیشتر، با قرار‌دادن زمان‌های حمل بین تأمین­کنندگان، نتایج الگوریتم PSA با الگوریتم DGA مقایسه و نتایج در جدول 7 نشان داده شده است. این جدول نشان می­دهد، در سطح اطمینان 95 درصد در 23 مورد فرض H0 رد شده است؛ بنابراین نتیجه می‌شود، الگوریتم PSA نسبت به الگوریتم DGA برتر است.

 

جدول 7- نتایج آزمون فرض مقایسه PSA و DGA

P-Value

(PSA-DGA)

DGA

PSA

تعداد تأمین­کننده

تعداد وسیله نقلیه

تعداد سفارش

مسأله

Mean CPU

Time

(Second)

Avrg

Best

Mean CPU

Time

(Second)

Avrg

Best

0/001

6/9154

816/2722

800

2/5423

646

615

5

1

10

1

0/1

6/1378

590

590

2/5669

557

526

10

1

10

2

0

5/5737

700

700

2/5281

475

475

15

1

10

3

0/2

5/9147

523/8495

501

2/5927

515/265

508

5

5

10

4

0/01

7/6267

473/667

470

2/5607

445/75

428

10

5

10

5

0

6/3275

510

510

2/6500

373/575

365

15

5

10

6

0/047

6/4174

496/9475

490

2/6002

486/667

462

5

10

10

7

0/4

11/0356

408/35

375

2/6252

406

368

10

10

10

8

0/2

5/6685

403

399

2/6624

400/4490

367

15

10

10

9

0

63/1954

19130

18450

6/3335

12314/33

11553

5

1

50

10

0

31/3519

23250

23200

6/9025

12334

12025

10

1

50

11

0

43/7746

38450

37750

7/4604

18264/67

18000

15

1

50

12

0

43/7193

12282/67

12141

6/5105

9778/4

9526

5

5

50

13

0

45/8000

7423/79

7365

6/5993

6076/625

5992

10

5

50

14

0/001

47/7909

10643/35

10418

7/0693

4909/8

4812

15

5

50

15

0

47/3132

11877

11825

6/7708

9067/175

8920

5

10

50

16

0

44/6692

6847/85

6756

6/9445

5444/45

5343

10

10

50

17

0/004

41/4965

5030/77

4894

7/2237

4141/975

3984

15

10

50

18

0

127/1550

90285/6

89018

12/0653

56272

53962

5

1

100

19

0

155/3321

71221/81

70982

12/6816

40807/75

40213

10

1

100

20

0

144/7372

85423/7

84410

13/5174

43485

43080

15

1

100

21

0

145/7896

51314

50374

11/6298

40860

40021

5

5

100

22

0/001

136/0949

40217

40002

12/9068

24938/28

24288

10

5

100

23

0/011

124/1126

22656

22625

13/2039

18019

17282

15

5

100

24

0

144/2747

48732/69

48250

12/3114

38520/45

37832

5

10

100

25

0/001

139/1752

27347

27305

12/9807

22050/18

21634

10

10

100

26

0

133/7707

21251/57

20719

13/3741

16465

16183

15

10

100

27

مقایسه با حل دقیق: به‌علت NP-Hard بودن مسأله، به دست آوردن جواب بهینه برای مسائل با ابعاد متوسط و بزرگ در زمان معقول امکان پذیر نیست؛ بنابراین برای مقایسه با حل دقیق، تعدادی مسأله با ابعاد کوچک ایجاد و با الگوریتم PSA حل شده­اند. نتایج به‌دست آمده با الگوریتم PSA با جواب بهینۀ محاسبه‌شده با نرم­افزار GAMS مقایسه و در جدول 8 نشان داده شده است. همان‌طور که در این جدول نشان داده شده است، PSA در برخی مسائل جواب دقیق را ارائه داده است و در برخی مسائل جواب به ‌دست‌ آمده با جواب بهینه فاصله دارد؛ اما این اختلاف ناچیز است. همچنین زمان حل الگوریتم PSA از نرم­افزار GAMS بسیار کمتر است.

 

جدول 8- مقایسه با حل دقیق

مسأله

سفارش

تأمین­کننده

وسیله نقلیه

GAMS

PSA

درصد

اختلاف نسبی

تابع هدف

زمان

تابع هدف

زمان

1

4

2

3

249

472/7

249

1/07

0

2

4

3

2

240

334/1

240

0/97

0

3

4

3

3

195

295/41

195

0/97

0

4

4

4

4

185

275/32

185

0/97

0

5

6

2

3

448

5694/95

450

1/06

0/44

6

6

3

2

381

4061/67

381

1/09

0

7

6

3

3

394

3741/35

394

1/12

0

8

6

4

4

310

3532/73

310

1/06

0

9

7

3

3

486

6853/98

497

1/2

2.21

10

7

4

4

398

6231/34

402

1/06

1

 

تحلیل حساسیت: در ادامه برای تحلیل بیشتر، حساسیت روی سه پارامتر اصلی تحلیل می‌‌شود؛ به‌همین دلیل سه پارامتر اصلی شامل، تعداد سفارش‌ها، تعداد تأمین‌کنندگان و تعداد وسایل نقلیه، انتخاب و با تغییر مقادیر آنها به‌صورت صعودی (ضمن ثابت نگه داشتن مقدار سایر پارامترها) تغییرات مقدار تابع هدف، بررسی می‌شود. جدول 9 مقادیر در‌ نظر گرفته‌ شده برای هر پارامتر و نتایج به ‌دست آمده در هر حالت را نشان می­دهد.

شکل­های 7، 8، 9 و نمودارهای تغییر تابع هدف و زمان حل برای تغییرات تعداد سفارش، تعداد وسیلۀ نقلیه و تعداد تأمین­کننده را نشان می­دهند.

شکل 7 نشان می­دهد، با افزایش تعداد سفارش‌ها میزان تابع هدف و زمان حل نیز افزایش می­یابد؛ زیرا سفارش‌های بیشتری باید به تعداد ثابتی از تأمین‌کنندگان و وسایل نقلیه تخصیص یابد و در‌نتیجه به‌طور متوسط بارِ کاری تأمین­کنندگان و وسایل نقلیه افزایش و زمان تحویل سفارش‌ها طولانی‌تر خواهد شد. در‌صورتی ‌که افزایش زمان­های تحویل در این حالت برای مدیریت خوشایند نباشد، پیشنهاد می­شود با استفاده از سیاست خرید قطعاتِ آماده از بازار، تعداد سفارش‌ها را برای برنامه­ریزی کاهش داده و میانگین زمان‌های تحویل را به مقدار هدف رساند. شکل 8 وشکل 9 نشان می­دهند با افزایش تأمین­کنندگان و وسایل نقلیه روند نمودار نزولی می‌شود و تابع هدف کاهش می­یابد؛ زیرا سفارش‌های مشخصی به تأمین­کنندگان و وسایل نقلیۀ مختلفی تخصیص داده‌شده و به‌طور متوسط بارِ کاری هریک از آنها کمتر و زمان­های تحویل کوتاه‌تر می‌شود؛ اما زمان حل، همچنان به‌دلیل افزایش فضای جواب، افزایش می­یابد. اگر میانگین زمان­های تحویل برای مدیریت، خوشایند نباشد، پیشنهاد می‌شود، تعداد تأمین‌کنندگان طرف قرارداد یا تعداد وسایل نقلیۀ استفاده‌شده افزایش و متوسط بارکاری روی هریک از تأمین‌کنندگان و وسایل نقلیه کاهش یابد؛ درنتیجه میانگینِ زمان­های تحویل به مقدار هدف برسد.

جدول 9- تحلیل حساسیت برای سه پارامتر اصلی

مسأله

وسیله نقلیه

تأمین­کننده

سفارش

تابع هدف

زمان

1

1

5

5

300

2/0263

2

10

868

2/5442

3

20

4183

3/8011

4

40

10082

5/4608

5

60

24661/5

7/8221

6

80

65106/5

10/8836

7

100

78959/5

12/4856

8

200

322002/5

24/9518

مسأله

وسیله نقلیه

تأمین­کننده

سفارش

تابع هدف

زمان

1

1

5

40

10619/5

5/6323

2

5

6586/9

5/8654

3

10

6440/3

6/0014

4

15

6032/55

6/1427

5

20

5621/7

6/2791

6

25

5407

6/417

7

30

5544/75

6/4522

8

40

5101/45

6/6379

مسأله

وسیله نقلیه

تأمین­کننده

سفارش

تابع هدف

زمان

1

10

5

20

1669

3/8341

2

10

1176

3/8105

3

15

1107

3/9099

4

20

995/5

4/0057

5

25

985

4/0674

6

30

956/5

4/1550

7

40

955

4/4846

8

50

973

4/8187

 

 

 

 

شکل 7- تغییرات تعداد سفارش

 

شکل 8- تغییرات تعداد وسیله نقلیه

 

 

شکل 9- تغییرات تعداد تأمین­کننده

 

خلاصه، نتیجه­گیری و زمینۀ پژوهش‌های آتی

در این مقاله زمان‌بندی وسایل نقلیه در زنجیره تأمین با در نظر ‌گرفتن اثرات متقابل بین بخش حمل‌و‌نقل و بخش تولید، بررسی شده است. زنجیره تأمین بررسی‌شده، شامل مجموعه­ای از تأمین­کنندگان است. در این زنجیره، یک ناوگان حمل­ونقل مشترک، سفارش‌های تخصیص داده شده به خود را به یک شرکت سازندۀ محصولات نهایی منتقل می­کند. این مجموعه از تأمین­کنندگانِ مستقر در نقاط جغرافیایی مختلف، قابلیت پردازش تمامی سفارش‌ها را ندارند و با‌توجه‌به توانایی­های خود، بخشی از آنها را پردازش می‌کنند. همچنین ناوگان حمل‌و‌نقل، متشکل از چندین وسیلۀ نقلیه با ظرفیت بارگیری محدود و میانگین سرعت متفاوت است، این میانگینِ سرعت، در کل دورۀ برنامه‌ریزی ثابت است. هدف، نحوۀ تخصیص سفارش‌ها به تأمین­کنندگان و تعیین توالی ساخت آنها در هر تأمین­کننده به‌همراه تخصیص سفارش‌ها به وسایل نقلیه و تعیین توالی حمل آنها است؛ به قسمی که مجموع زمان تحویل سفارش‌ها حداقل شود. این مسأله تاکنون در ادبیات موضوع بررسی نشده‌ است. ابتدا برای این مسأله یک مدل ریاضی عدد صحیح مختلط ارائه شد و برای حل آن سه الگوریتم ژنتیک، شبیه سازی تبرید و شبیه سازی تبرید جمعیتی (ترکیبی از دو الگوریتم GA و SA)، ارائه شد. برای بررسی کیفیت جواب­های PSA، ابتدا تعدادی مسأله تصادفی با ابعاد مختلف ایجاد شد و نتایج آن با الگوریتم SA و توسعۀ الگوریتم DGA ارائه‌شده مقایسه شد. سپس با ریلکس‌کردن فرضِ وجود مسافت بین تأمین­کنندگان موجود در یک ناحیۀ جفرافیایی، مسأله تبدیل به مسأله‌ای شد که ذگردی و بهشتی­نیا (2009) آن را مطرح کرده‌اند و نتایج PSA در این حالت با نتایج DGA ارائه‌شدۀ آنها، مقایسه شد. نتایج نشان می‌دهد در همۀ مقایسه‌ها الگوریتم PSA برتر است. برای اثبات برتری الگوریتم­ PSA، از آزمون فرض استفاده شده است. به‌علاوه به ازای مسائل با ابعاد کوچک، نتایج الگوریتم PSA با جواب بهینه مقایسه شد. نتایج مقایسه‌شده نشان از کارایی بالای الگوریتم PSA دارد. درنهایت با انجام تحلیل حساسیت روی پارامترهای اصلی (تعداد سفارش‌ها، تعداد تأمین‌کنندگان و تعداد وسایل نقلیه) تأثیر تغییرات آنها بر تغییرات تابع هدف و زمان حل نشان داده شد.

در انتها نیز چند زمینه برای پژوهش‌های آتی به‌شرح زیر پیشنهاد می­شود:

  • بسط مسأله بررسی‌شده در این پژوهش در حالتی که چند شرکت سازندۀ محصول نهایی و چند پایانۀ حمل­ونقل در نقاط مختلف جغرافیایی قرار داشته باشند.
  • اضافه کردن محدودیت ظرفیت تولید در تأمین­کنندگان.
  • اضافه کردن فرضیاتی مانند وجود حالت ساخت و مونتاژ در شرکت سازنده مرکزی.
  • ارایه روش‌های حل دیگر، مانند الگوریتم زنبور عسل[xxxix] و جستجوی ممنوعه برای این مسأله.


[ii]- Dantzig & Ramser

[iii]- Chang & Lee

[iv]- Wang & Cheng

[v]- Yimer & Demirli

[vi]- Mixed integer linear program

[vii]- Scholz-Reiter, Frazzon, & Makuschewitz

[viii]- Liu & Chen

[ix]- Mehravaran & Logendran

[x]- Tabu search

[xi]- Kuo & Wang

[xii]- Osman & Demirli

[xiii]- Ullrich

[xiv]- Parallel machine

[xv]- Kabra, Shaik, & Rathore

[xvi]- Averbakh & Baysan

[xvii]- Ren, Du, & Xu

[xviii]- Thomas, Venkateswaran, Singh, & Krishnamoorthy

[xix]- Column generation

[xx]- Sawik

[xxi]- Selvarajah & Zhang

[xxii]- Ray, Soeanu, Berger, & Debbabi

[xxiii]- Archetti, Jabali, & Speranza

[xxiv]- Outsourcing

[xxv]- Planning production

[xxvi]- Zegordi & Beheshti Nia

[xxvii]- Populated Simulated annealing

[xxviii]- Genetic algorithm

[xxix]- Simulated Annealing

[xxx]- Holland

[xxxi]- First generation

[xxxii]- Crossover

[xxxiii]- Mutation

[xxxiv]- Selection

[xxxv]- Coding

[xxxvi]- Genotype

[xxxvii]- Phenotype

[xxxviii]- Kirkpatrick & Vecchi

[xxxix]- Bee colony

ذگردی، سیدحسام الدین.، بهشتی­نیا، محمدعلی، (1388). یکپارچگی زمان‌بندی حمل‌و‌نقل در زنجیره تامین با وسائط نقلیه دارای ظرفیت‌های متفاوت. پژوهشنامه حمل و نقل، 3.

نخعی کمال آبادی، عیسی.، نیکبخش جوادیان, مهری گوران, مهدوی., ا. (1386). یکپارچه‌سازی زمان‌بندی و حمل‌و‌نقل در زنجیرۀ تأمین چندکارخانه‌ای. نخستین کنفرانس بین‌المللی مدیریت زنجیرۀ تامین و سیستم‌های اطلاعات.

Archetti, C., Jabali, O., & Speranza, M. G. (2015). "Multi-period vehicle routing problem with due dates". Computers & Operations Research, 61, 122-134.

Averbakh, I., & Baysan, M. (2013). "Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem". Operations Research Letters, 41(6), 710-714. doi: http://dx.doi.org/10.1016/j.orl.2013.10.002

Chang, Y.-C., & Lee, C.-Y. (2004)."Machine scheduling with job delivery coordination". European Journal of Operational Research, 158 (2): 470-478 doi: http://dx.doi.org/10.1016/S0377-2217(03)00364-3

Dantzig, G. B., & Ramser, J. H. (1959). "The truck dispatching problem". Management science, 6(1), 80-91.

Holland, J. H. (1975). "Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence: U Michigan Press.

Kabra, S., Shaik, M. A., & Rathore, A. S. (2013). "Multi-period scheduling of a multi-stage multi-product bio-pharmaceutical process". Computers & Chemical Engineering, 57(0), 95-103. doi: http://dx.doi.org/10.1016/j.compchemeng.2013.03.009

Kirkpatrick, S., & Vecchi, M. (1983). "Optimization by simmulated annealing". science, 220(4598), 671-680.

Kuo, Y., & Wang, C.-C. (2012)." A variable neighborhood search for the multi-depot vehicle routing problem with loading cost". Expert Systems with Applications, 39(8), 6949-6954.

Liu, S.-C., & Chen, A.-Z. (2012). "Variable neighborhood search for the inventory routing and scheduling problem in a supply chain". Expert Systems with Applications, 39(4), 4149-4159.

Mehravaran, Y., & Logendran, R. (2012). "Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times". International Journal of Production Economics, 135(2), 953-963.

Osman, H., & Demirli, K. (2012). "Economic lot and delivery scheduling problem for multi-stage supply chains". International Journal of Production Economics, 136(2), 275-286. doi: http://dx.doi.org/10.1016/j.ijpe.2011.12.001

Ray, S., Soeanu, A., Berger, J., & Debbabi, M. (2014.(The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. Knowledge-Based Systems, 71, 238-265.

Ren, J., Du, D., & Xu, D. (2013). "The complexity of two supply chain scheduling problems". Information Processing Letters, 113(17), 609-612. doi: http://dx.doi.org/10.1016/j.ipl.2013.05.005

Sawik, T. (2014). "Joint supplier selection and scheduling of customer orders under disruption risks: Single vs. dual sourcing". Omega, 43(0), 83-95. doi: http://dx.doi.org/10.1016/j.omega.2013.06.007

Scholz-Reiter, B., Frazzon, E. M., & Makuschewitz, T. (2010). "Integrating manufacturing and logistic systems along global supply chains". CIRP Journal of Manufacturing Science and Technology, 2(3), 216-223.

Selvarajah, E., & Zhang, R. (2014). "Supply chain scheduling at the manufacturer to minimize inventory holding and delivery costs". International Journal of Production Economics, 147, Part A(0), 117-124. doi: http://dx.doi.org/10.1016/j.ijpe.2013.08.015

Thomas, A., Venkateswaran, J., Singh, G., & Krishnamoorthy, M. (2014). "A resource constrained scheduling problem with multiple independent producers and a single linking constraint: A coal supply chain example". European Journal of Operational Research, 236(3), 946-956. doi: http://dx.doi.org/10.1016/j.ejor.2013.10.006

Ullrich, C. A. (2013). "Integrated machine scheduling and vehicle routing with time windows". European Journal of Operational Research, 227(1), 152-165. doi: http://dx.doi.org/10.1016/j.ejor.2012.11.049

Wang, X., & Cheng, T. E. (2009). "Production scheduling with supply and delivery considerations to minimize the makespan". European Journal of Operational Research, 194(3), 743-752.

Yimer, A. D., & Demirli, K. (2010). "A genetic approach to two-phase optimization of dynamic supply chain scheduling". Computers & Industrial Engineering, 58(3), 411-422.

Zegordi, S., & Beheshti Nia, M. (2009). "Integrating production and transportation scheduling in a two-stage supply chain considering order assignment". The International Journal of Advanced Manufacturing Technology, 44(9-10), 928-939. doi: 10.1007/s00170-008-1910-x.