مسئله مسیریابی وسایل نقلیه ناهمگن با چند جایگاه پخش همراه بامحدودیت بازه‌های زمانی مختص به کالاهای فاسدشدنی

بابایی تیرکلایی, عرفان; سائیل پور, سعید; میرمحمدی, سیدحمید

مسئله مسیریابی وسایل نقلیه ناهمگن با چند جایگاه پخش همراه بامحدودیت بازه‌های زمانی مختص به کالاهای فاسدشدنی

نویسندگان

دانشگاه صنعتی اصفهان

چکیده

این مقاله به بررسی مسئله مسیریابی وسایل نقلیه ناهمگن با چند جایگاه پخش، همراه با محدودیت بازه های زمانی مختص به کالاهای فاسدشدنی می پردازد. هدف در مسئله مورد بررسی، کمینه سازی مجموع زمان مورد نیاز جهت سرویسدهی کل مشتریان متناسب با هزینه کل است. محصولات توسط ناوگانی از وسایل حمل ناهمگن با ظرفیت محدود و محدودیت زمانی تعریف شده به مشتریان تحویل داده می‌شوند. با توجه به اینکه مورد بررسی این مقاله، یک مسئله NP-Complete و نمونه پیچیده‌تر مسئله مسیریابی وسیله نقلیه است، بنابراین مسئله ما نیز در دسته مسائل NP-Complete قرار دارد و روش های دقیق برای حل آن در ابعاد واقعی، کارآمد می باشند. در ضمن برای حل تقریبی مسئله الگوریتم فراابتکاری مورچگان بیشینه-کمینه ارائه شده است و دلایل استفاده از آن در ادامه مقاله تشریح می شود. در نهایت، نتیجه بررسی‌ها در مقایسه با نمونه‌های مشهور بیانگر آن است که الگوریتم پیشنهادی در یک زمان عملیاتی کوتاه، عملکرد مناسبی دارد.

کلیدواژه‌ها

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

The Multi-depot Vehicle Routing Problem of Heterogeneous Fleet of Vehicles with Time Windows for Perishable Commodities

چکیده [English]

This paper discusses the multi-depot vehicle routing problem of heterogeneous fleet of vehicles with time windows for perishable commodities. The objective of the problem is to minimize the total time required for servicing all customers that is equivalent to the total cost. Commodities are delivered to the customers with defined time windows by a fleet of heterogeneous vehicles, which have limited capacities. The mentioned problem is a more general version of vehicle routing problem (VRP), hence it belongs to NP-complete complexity class and we present a Max-Min ant colony algorithm to solve the model approximately in practical dimensions. Finally, the experimental results have shown that the presented algorithm has appropriate performance in comparison with well-known instances in a reasonable time.

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

Multi-Depot VRP
Perishable Commodities
Max-Min Ant System
Time Windows
Heterogeneous Fleet of Vehicles

مراجع

[1] P. Toth and D. Vigo. “The Vehicle Routing Problem”. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 2002.

[2] G. B. Dantzig and J. H. Ramser. “The Truck Dispatching Problem”. Management Science, 6:80-91, 1959.

[3] L. Tansini, M. Urquhart, O. Viera. “Comparing Assignment Algorithms for the Multi-Depot VRP”. Computers and Operations Research,20(7), 783–791.

[4] B. Crevier, J. F. Cordeau, G. Laporte. “The multi-depot vehicle routing problem with inter-depot routes”. Eurpean Journal of Operational Research, 176:756-773, 2007.

[5] T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, W. Rei. “A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problem”. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, 2011.

[6] Malandraki, C., &Daskin, M. S.,“Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms”. TransportationScience, 26(3), 185–199,1992.

[7] Tarantilis, C. D., &Kiranoudis, C. T.,“A meta-heuristic algorithmfor the efficient distribution of perishable foods”. Journal of FoodEngineering, 50, 1–9,2001.

[8] Prindezis, N., Kiranoudis, C. T.,&Marinos-Kouris, D.,“A business-to-business fleet management service provider for central food market enterprises”. Journal of Food Engineering, 60(2), 203–210,2003.

[9] Chaug-Ing Hsu, et al.,“Vehicle routing problem with time-windows for perishable food delivery”. Journal of Food Engineering 80 (2007) 465-475,2007.

[10] Osvald A, Stirn L.,“A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food”. J Food Eng 85(2):285–295,2008.

[11] Dorigo, M., "Optimization, Learning and natural algorithms", Ph.D. Thesis, Dip.Electtronica e Informazion, Politecnico di,1992.

[12] F. Cano Sevilla, C. Simo’n de Blas, “vehicle routing problem with time windows and intermediate facilities”,in:S.E.I.O_.03 Edicions de la Universitat de Lleida, pp. 3088-3096, 2003.

[13] J.-F. Cordeau, G. Laporte, and A. Mercier.“Improved tabu search algorithm forthe handling of route duration constraints in vehicle routing problems with time windows”. Journal of the Operational Research, 55(5):542_546, May 2004.