بررسی مقایسه‌ای الگوریتم‌های فرا ابتکاری برای مسیریابی وسیله نقلیه پویا به منظور بهره‌وری وکارایی سیستم‌های حمل ‌و نقل

مدیریت بهره‌وری

مقاله 10، دوره 11، 1(40)بهار، خرداد 1396، صفحه 287-310   

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

نویسندگان

نازیلا مصیب زاده¹؛ فرزین مدرس خیابانی^{* 2}

¹دانش آموخته کارشناسی ارشد، گروه ریاضی، دانشگاه آزاد اسلامی واحد تبریز، تبریز، ایران

²گروه ریاضی، واحد تبریز، دانشگاه آزاد اسلامی تبریز، ایران

چکیده

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

کلیدواژه‌ها

الگوریتم‌های فرا ابتکاری؛ الگوریتم ژنتیک؛ مسأله مسیریابی وسایل نقلیه؛ بهره‌وری

مراجع

Blanton, J. L., & Wainwright, R. L. (1993). Multiple vehicle routing with time and capacity constraints using Genetic Algorithms in Forrest. Proceedings of the 5^th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 452-9.

Christophides, N., & Beasley, J. (1984). The period routing problem. Networks, 14, 237-256.

Davis, L. (1991). Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold.

Falkenauer, E. (1998). Genetic Algorithms and Grouping Problems, Wiley: Chichester.

Fisher, M. L. (1995). Vehicle routing. Handbooks Oper Res Manage Sci 8.

Fleischmann, B., Gnutzmann, S., & Sandvob, E. (2004). Dynamic vehicle routing based on online traffic information. Transportation Science, 38(4), 420-433.

Gendreau, M., & Potvin, J. Y. (1998). Dynamic vehicle routing and dispatching. Translate  by: T. G. Crainic, & G. Laporte, Boston: Fleet Management and Logistics, Kluwer.  

Ghiani, G., Guerriero, F., Laporte, G., & Musmanno, R. (2003). Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. Research Report, Center of Excellence for High Performance Computing, University of Calabria, Arcavacata di Rende.

Glover, F. (1990). Tabu search-part II. Orsaj Comput, 2(1), 4-32.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley.

Hanshar F.T., & Ombuki-Berman. B.M. (2007).  Dynamic vehicle routing using genetic algorithms. Appl. Intell. 27, 89-99.

Holland, J. H. (1992). Adaptation in natural and artificial systems university of michigan press Second Edition. MIT Press.

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems-An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The University of Michigan Press, Ann Arbor, MI.

Jaw, J. J., Odoni, A. R., Psaraftis, H. N., and Wilson, N. H. M. (1986). A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research, 20(2), 243-57.

Kilby P, Prosser P, Shaw, P. (1998). Dynamic VRPs: astudy of scenarios. Technical Report APES-0-1998, University of Strathclyde.

Kopfer, H., Pankratz, G., & Erkens, E. (1994). Die entwicklung eines hybriden genetischen algorithmus fu¨r das tourenplanungsproblem. OR Spektrum, 16, 21-32.

Li, H., & Lim, A. (2001). A metaheuristic for solving the pickup and delivery problem with time windows, in IEEE Computer Society (Ed.), Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), IEEE Computer Society, Los Alamitos.

Mitchell, M. (1996). Anintroduction to genetic algorithms. MIT Press.

Montemanni, R., Gambardella L. M., Rizzoli A. E., & Donati, A. V. (2005). A new algorithm for a dynamic vehicle routing problem based on Ant colony system. Jcomb Optim, 10, 327–343.

Pankratz, G. (2005). A grouping genetic algorithm for the pickup and delivery problem with time windows. Operations Research Spectrum, 27, 21-41.

Pankratz, G. (2005). Dynamic vehicle routing by means of a genetic algorithm. International Journal of Physical Distribution & Logistics Management 35(5), 362-383.

Psaraftis, H. N. (1988). Dynamic vehicle routing problems, North-Holland, Amsterdam.

Savelsbergh, M. W. P., & Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29, 17-29.

Taillard, E. D. (1994). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.

Yang, J., Jaillet, P., & Mahmassani, H. S. (2004). Study of a real-time multi-vehicle truckload pickup-and-delivery problem. Transportation Science, 38(2).