حل مسأله مسیریابی وسائط نقلیه ناهمگن چندقرارگاهی با پنجره زمانی توسط الگوریتم تکامل دیفرانسیلی چند هدفه: مطالعه موردی

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

نویسندگان

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

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

چکیده

مسأله مسیریابی وسائط نقلیه چندقرارگاهی با در نظر گرفتن پنجره زمانی و وسائط نقلیه متفاوت1، یکی از انواع مسایل مسیریابی وسائط نقلیه2 است. وسائط نقلیه دارای ظرفیتهای متفاوتی هستند و به قرارگاه‏های متفاوتی تخصیص داده می‏شوند. بنابراین، این مسأله شامل طراحی یک مجموعه از مسیرهایی است که در آن وسائط نقلیه با ظرفیت‌های متفاوت از یک قرارگاه شروع به حرکت می‌کنند، به مجموعه‏ای از مشتریان که دارای تقاضای معینی هستند سرویس‌دهی کرده و در نهایت به همان قرارگاه باز می‌گردند. بیشتر مسایلی که در این زمینه مطرح شده‏اند، مربوط به مسایل تک هدفه با هدف کمینه کردن هزینه هستند، اما پیچیدگی‌های مسایل واقعی عموما کاربرد مسایل تک هدفه را به چالش می‌کشد. از این رو در این مقاله برای انطباق مسایل با دنیای واقعی، در ابتدا یک مدل چند هدفه ارائه می‌گردد که در آن علاوه بر کمینه کردن هزینه‏های کل، عدم توازن حجم کاری بر حسب مسافت طی شده توسط وسائط نقلیه، همچنین بار قابل حمل آنها نیز مد نظر قرار گرفته است و از آنجایی که این مسأله جزء مسائل NP-hard است، استفاده از الگوریتم‌های فراابتکاری الزامی‏است، به همین منظور برای حل مدل ارائه شده، روش فراابتکاری تکامل دیفرانسیلی چند هدفه3 پیشنهاد شد و برای نشان دادن کارآیی الگوریتم پیشنهادی، جوابهای به دست آمده در ابعاد کوچک با جوابهای به دست آمده از روش محدودیت اپسیلون4 مقایسه شد. نتایج به دست آمده، نشان می‌دهند که درصد خطای توابع هدف نسبت به روش دقیق در تمامی‏مسایل حل شده کمتر از 3.2% است که نشانگر کارآیی روش پیشنهادی است و در نهایت به بررسی این موضوع در یک شرکت پخش روغن نباتی پرداخته شده است که نتایج حاصل، نشان دهنده کاهش قابل توجه هزینه‏های آن شرکت است.

کلیدواژه‌ها

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

Solving a Multi-Depot Routing Problem with Time Windows and Heterogeneous Vehicles by Multi-objective Differential Evolution Algorithm: A Case Study

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

  • Shaghayegh Masoudi 1
  • Hasan Javanshir 1
  • Reza Tavakkoli-Moghaddam 2
1
2
چکیده [English]

A Multi-depot Heterogeneous Vehicle Routing Problem with Time Windows (MDHVRPTW) is a variant of the Vehicle Routing Problem (VRP), in which the vehicles do not necessarily have the same capacity and they belong to different depots. Therefore, the MDHVRPTW involves designing a set of vehicle routes, each starting and ending at the depot, for a heterogeneous fleet of vehicles which services a set of customers with known demands. Most problems presented in this field are single-objective problems with the aim of minimizing the cost; however, the complexity of real problems usually doubts the use of single-objective problems. This paper considers not only the minimum travel cost, but also the distance travelled by the used vehicles and their loads. Since this problem is NP-hardness, the use of a meta-heuristic algorithm is obligatory. Therefore a meta-heuristic algorithm based on Multi-Objective Differential Evolution (MODE) is proposed. In addition, to show the efficiency of the proposed MODE, a number of test problems in small and large sizes are considered and then solved. The associated results are evaluated with the results obtained by the ε-constraint method and results showed that the gained function gap was less than 3.5% in all the solved problems. Furthermore, to run the proposed MODE, a real-case study in an oil distribution company is carried out. Finally, the obtained results are reported and discussed.

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

  • Multi-objective vehicle routing problem
  • Time window
  • Multi-depot
  • ∊-constraint
  • Differential evolution

مراجع

- Bae, T. S., Hwang, H. S., Cho, G. S. and Goan, M. J. (2007) “Integrated GA-VRP solver for multi-depot system”, Computers & Industrial Engineering, Vol. 53, No. 2, pp. 233-240.
- Baños, R., Ortega, J., Gil, C, Márquez, A. L. and de 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.  
- Bettinelli, A., Ceselli, A. and Righini, G. (2010) “A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows”. Transportation Research - Part C, Vol. 19, No. 5, pp. 723-740.
- Chen, H .K., Hsueh, C. F. and Chang, M. S. (2009) “Production scheduling and vehicle routing with time windows for perishable food products”. Computers & Operations Research, Vol. 36, pp. 2311-2319.
- Clarke, G. and Wright, J. W. (1964) “Scheduling of vehicles from a central depot to a number of delivery points”. Operations Research, Vol. 12, pp. 568–589.
- Dantzig, G. and Ramser, J. H. (1959) “The truck dispatching problem”, Management Science, Vol. 6, pp. 80-91.
 - Fazel Zarandi, M. H., Hemmati, A. and Davari, S. (2011) “The multi-depot capacitated location- routing problem with fuzzy travel times”. Expert Systems with Applications Vol. 38, pp. 10075–10084.
- Gnoni, M. G., Lavagnilio, R. Mossa, G., Mommolo, G. and Leva, A. D. (2003) “Production of a multisite manufacturing system by hybrid modeling: A case study from the automotive industry”, International Journal of Production Economics, Vol. 5, pp. 251-262.
- Ghannadpour, S. F., Noori, S. and Tavakkoli-Moghaddam, R. (2014) “A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority”, Journal of Combinatorial Optimization, Accepted for publication, Vol. 28, No. 2, pp. 414-466
- Giosa, I. D., Tansini, I. L.and Viera, I. C. (2002) “New assignment algorithms for multi-depot vehicle routing problem”. Journal of Operational Research Society, Vol. 53, No. 9, pp. 977-984.
- Ghoseiri, K. and Ghannadpour, S. F. (2010) “Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm”, Applied Soft Computing, Vol. 10, No. 4, pp. 1096-1107.
- Gulczynski, D., Golden, G. and Wasil, E. (2011) “The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems and computational results”, Computers & Industrial Engineering, Vol. 61, No. 3, pp. 794-804.
- Khaled Ahsan Talukder, A. K. Kirley M. and, Buyya,  M. B. (2009) “Multiobjective differential evolution for scheduling workflow applications on global grids”, Concurrency and Computation: Practice and Experience, Vol. 21, No. 13, pp. 1742-1756.
- Kritikos, M. N. and Ioannou, G. (2013) “The heterogeneous fleet vehicle routing problem with overloads and time windows”. Int. J. Production Economics, Vol. 144, No. 1, pp. 68-75.
- Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981) “Complexity of vehicle and scheduling problem”, Networks, Vol. 11, pp. 221–227.
- Mirabi, M., FatemiGhomi, S. M. t. and Jolai, F. (2010) “Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem”, Robotics and Computer-Integrated Manufacturing, Vol. 26, No. 6, pp. 564–569.
- Nagy, G. and Salhi, S. (2005) “Heuristic algorithms for the single and multiple depot vehicle routing problems with pickups and deliveries”, European Journal of Operational Research, Vol. 162, No. 1, pp. 126-141.
- Noori, S. and Ghannadpour, S. F. (2012) “High-level relay hybrid metaheuristic method for Multi-depot Vehicle routing problem with time windows”, Journal of Math. Model Algor., Vol. 11, pp. 159–179.tt
- Storn, R. and Price, K.V. (1996) “Minimizing the real functions of the ICEC’96 contest by differentian evolution”. IEEE International Contrence on Evolutionary Computation,Vol. 14, pp. 824 844.
-Tavakkoli-Moghaddam, R., Safaei, N. and Gholipour, Y. (2006) “A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length”, Applied Mathematics and Computation, Vol. 176, pp. 445–454.
- توکلی مقدم، ر.، نوروزی، ن.، سلامت بخش، ع.ر.، علینقیان، م.، (1390)، "مسأله مسیریابی وسائط نقلیه با در نظر گرفتن ایجاد توازن در توزیع کالاها با استفاده از الگوریتم بهبود یافته بهینه سازی انبوه ذرات"، پژوهشنامه حمل و نقل، سال هشتم، شماره 4، زمستان 1390، ص. 375-363.
- توکلی مقدم، ر.، علینقیان، م.، نوروزی، ن.، سلامت بخش، ع. ر. (1391) "حل یک مدل جدید برای مسأله مسیریابی وسائط نقلیه با در گرفتن ایمنی در حمل و نقل مواد خطرناک"،  فصلنامه مهندسی حمل و نقل، سال دوم، شماره 3، بهار 1390، ص. 237-223.

فایل ها

سابقه مقاله

  • تاریخ دریافت: 14 آذر 1392
  • تاریخ پذیرش: 10 خرداد 1393

هم رسانی

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

آمار