مسأله‌ مسیر‌یابی وسائط نقلیه دوره‌ای با پنجره‌ زمانی در حالت رقابتی با روش شبیه‌سازی تبرید بهبودیافته

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

چکیده

در این مقاله، حالت جدیدی از ترکیب مسأله مسریابی دوره‌ای با در نظر گرفتن پنجره‌ زمانی در حالت رقابتی مورد بررسی قرار می‌گیرد.  با توجه به دنیای واقعی، همیشه، چندین توزیع کننده به منظور خدمت‌دهی به مشتریان وجود دارد. بر این اساس همیشه رقابت بین رقبا و تمایل به دسترسی سریع تر به مشتریان با ارزش بالا برای کسب نقدینگی بیشتر علاوه بر یافتن مسیرهای کوتاه وجود دارد. به همین جهت، هدف این مقاله ارایه مدلی است که با کوتاه ترین مسیر و کمترین هزینه، در زود‌ترین زمان ممکن و زود‌تر از رقبا به مشتریان سرویس‌دهی کند تا حداکثر سود را کسب کنند. به دلیل کاربرد فراوان این مدل در توزیع دوره ای محصولات، مسأله مسیریابی وسائط نقلیه دوره‌ای در حالت رقابتی در این مقاله مورد توجه قرار گرفته است.  با توجه به اینکه مسأله مورد نظر حالتی از مسیریابی وسائط نقلیه است، این مسأله جزء مسایل  NP-Hard  قرار می‌گیرد.  از همین رو در این مقاله، از روش شبیه‌سازی تبرید (SA) و روش شبیه‌سازی تبرید‌ بهبود یافته(ISA)‌  جهت حل مدل پیشنهادی استفاده می شود. از این رو تعدادی مسأله در ابعاد متنوع تولید شده و سپس برای نشان دادن کارآیی الگوریتم‌های ارایه شده پاسخ‌های به دست آمده با الگوریتم دقیق شاخه و کران مقایسه می شود و پاسخ‌های به دست آمده مورد تجزیه و تحلیل قرار می گیرد. نتایج نشان دهنده‌ آن است که درصد خطای روش SA و ISA   در ابعاد کوچک به طور میانگین به ترتیب ا درصد و صفر درصد است که کارآیی الگوریتم‌های پیشنهادی را نشان می‌دهد. علاوه بر این، زمان حل مسایل در روشهای فرا ابتکاری نشان دهنده خطی بودن افزایش زمان رسیدن به پاسخ با افزایش ابعاد مسأله است، ولی مدت زمان رسیدن به پاسخ توسط روش دقیق با افزایش ابعاد مسأله به صورت نمایی افزایش می‌یابد. در ابعاد بزرگ به طور میانگین از  نظر زمانی الگوریتم ISA   تقریبا 20 درصد کند تر از روش SA عمل می‌کند، اما کیفیت پاسخ‌های الگوریتم به طور میانگین ISA   3 درصد بهتر از الگوریتم SA است.  همچنین حداکثر میزان  بهبود روش ISA   نسبت به SA نیز 7 درصد بوده است. این امر نشان می‌دهد که بهبود ایجاد شده در الگوریتم  SA تاثیر مناسبی در بهبود پاسخ‌ها داشته است.

کلیدواژه‌ها


-  توکلی مقدم، رضا، ربانی، مسعود، شریعت، محمد علی و صفائی، نیما (1385) " حل مسایل مسیریابی وسایط نقلیه با پنجره‌های زمانی نرم با استفاده از یک الگوریتم فرا ابتکاری  تلفیقی" نشریه فنی دانشگاه تهران، جلد 40، شماره 4، مهر 1385، ص. 476-469.
-  ربانی، یوسف، سپهری،  محمدمهدی، ذگردی، سید حسام الدین (1387)" مسأله مسیریابی وسیله نقلیه متصل به حمل ونقل چند وجهی رویکرد یکپارچه" پژوهشنامه حمل و نقل، سال پنجم، شماره چهارم، زمستان 1387 ص. 307-318.
-  سپهری، محمد مهدی و حسینی مطلق، سید مهدی (1387) "‌مسیر‌یابی بهینه‌ سیستم‌های حمل و نقل در انبار‌های اتوماتیک"، پژوهشنامه حمل و نقل، سال پنجم، شماره 2،  ص. 127-144.
-        Alegre, J., Laguna, M. and Pacheco, J. (2007) "Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts", European Journal of Operational Research, Vol. 179, No. 3‌, June, pp.‌736–746.
 
-        Beltrami, E.J. and Bodin, L.D. (1974)‌ "Networks and vehicle routing for municipal waste collection", Networks‌, Vol. 4, No. 1, pp. 65–94.
 
-        Carter, M.W, Farvolden, J. M. Laporte, G and Xu, J. (1996) "Solving an integrated logistics problem arising in grocery distribution". INFOR, Vol. 34, No. 4, ‌pp. 290–306.
 
-        Chang, C.T. and Chang C. C. (2000) "A linearization method for mixed 0–1 polynomial programs", Computers & Operations Research, Vol. 27, No. 10, September, ‌pp.1005–1016.
 
-        Chao, I. M., Golden, B. L. and Wasil, E.A. (1995)‌ "An improved heuristic for the period vehicle routing problem",   Networks‌, Vol. 26, No. 1, pp. 25–44.
 
-        Christofides, N. and Beasley, J. E. (1984)‌ "The period routing problem", Networks, Vol. 14, No.1, pp. 237–256.
 
-        Claassen, G.D.H. and Hendriks, T. H. B. (2007)"An application of Special Ordered Sets to a periodic milk collection problem". European Journal of Operational Research, Vol.‌ 180, No. 2, July, pp. 754–769.
 
-        Clarke, G. and Wright, J. (1964) ‌ "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research‌, Vol.‌ 12, No. 4, July, pp. 568–581.
 
-        Cordeau, F., Gendreau, M. and Laporte, G.‌ (1997) "A tabu search heuristic for periodic and multi-depot vehicle", Journal routing problems, Networks, Vol. 30, No. 2, pp.105-119.
 
-        Drummond, L.‌M.A., Ochi, L.S. and Vianna, D.S. (2001) "An asynchronous parallel metaheuristic for the period vehicle routing problem", Future Generation Compute Systems‌, Vol. 17, No. 4‌, pp.‌379–386.
 
-        Gaur, V.‌ and Fisher, M. L. (2004) "A periodic inventory routing problem at a supermarket chain", Operations Research, Vol. 52, No. 6‌, pp.‌813–822.  
 
-        Golden, B. L. and Wasil, E.A.  (1987) "Computerized vehicle routing in the soft drink industry". Operations Research, Vol. 35, No. 1‌, pp.6–17.
 
-        Fisher, M. L. and Jaikumar, R. (1981)‌ "A generalized assignment heuristic for vehicle  routing problems", Networks, Vol. 11, No. 2, pp.109–124.
 
-        Francis, P. M., Smilowitz, K.R. and Tzur, M. (2006) "The period vehicle routing problem with service choice", Transportation Science‌, Vol. 40, No. 4, October, ‌pp. 439–454.
 
-        Gaudioso, M. and Paletta, G. (1992) ‌ “A heuristic for the period vehicle routing problem” Transportation Science,  Vol. 26, No. 2, pp. 86–92.
 
-        Glover F. and Woolsey, L. (1974) "Converting the 0–1 polynomial programming problem to a 0–1 linear program", Operation Research, Vol. 22, No. 1, January, ‌pp. 180–182.
 
-        Golden, B.L., Magnanti, T. L. and Nguyen, H. Q. (1977)‌ "Implementing vehicle routing algorithms", Networks, Vol. 7, No. 2, pp. 113–148.
 
-        Hajek, B. (1985) "Cooling schedules for optimal annealing", Mathematics of Operations Research, Vol. 13, No. 2, May, ‌pp. 311–329.
 
-        Hemmelmayr, V., Doerner, K. and Hartl, R. (2009) "A variable neighborhood search heuristic for periodic routing problems", European Journal of Operational Research, Vol. 195, No. 3‌, June, pp. 791–802.
 
-        Kirkpatrick, F., Gelatt, C. and Vecci, M. (1983) "Optimization by simulated annealing", American Association for the Advancement of Science, Vol. 220, No. 4598, May, ‌pp. 671–680.
 
-        le Blanc, H. M., F. Cruijssen, H. A. Fleuren, and M. B. M. de Koster. Factory gate pricing: An analysis of the Dutch retail distribution. Working paper; http://econpapers.repec.org/paper/dgreureri/30001575.htm. (2004).
 
-        Lin, S. and Kernighan, B.W.  (1973) "An effective heuristic for the traveling salesman problem" Operations Research‌, Vol. 21, No. 2, March, pp. 498–516.
 
-        Mourgaya, M. and Vanderbeck, F. (2006) "Column generation based heuristic for tactical planning in multi-period vehicle routing", European Journal of Operational Research, Vol. 183, No. 3‌, pp. 1028–1041.
 
-        Norouzi, N., Tavakkoli-Moghaddam, R., Ghazanfari, M., Alinaghian, M. and salamatbakhsh, A. (2012) "A new multiobjective competitive open vehicle routing problem solved by particle swarm optimization", Networks and Spatial Economics, Vol. 14, No.4, ‌pp. 603–633.
 
-            Parthanadee, P. and Logendran, R. (2006) "Periodic product distribution from multi-depots under limited supplies", IIE Transactions, Vol. 38, No. 11, pp. 1009–1026.
 
-        Russell, R. A. (1977) "An effective heuristic for the M-tour traveling salesman problem with some side conditions" Operations Research, Vol. 25, No. 3, pp. 517–524.
 
-        Russell, R. A. and Gribbin, D. (1991)‌ "A multiphase approach to the period routing problem", Networks‌, Vol. 21, No‌. 7‌, pp.‌ 747–765.
 
-        Russell, R. A. and Igo, W. (1979) "An assignment routing problem", Networks, Vol. 9, No. 1, pp. 1–17.
 
-          Tan, C. C. R. and Beasley, J. E. (1984)‌ "A heuristic algorithm for the period vehicle routing problem", Omega, Vol. 12, No. 5, pp. 497–504.
 
-        Tavakkoli-Moghaddam, R., Ghazanfari, M., Alinaghian, M., salamatbakhsh, A. and Nourozi, N. (2011) "A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing", Journal of Manufacturing Systems, Vol. 30, No. 2, ‌pp. 83–92.
 
-       Toth, P. and Vigo, D. (2002) "The vehicle routing problem", University Degli Studi di Bologna, Italy.