بهینه سازی سیستم حمل و نقل ادارات با خوشه بندی به روش k میانگین و ترکیب الگوریتم saving و جستجوی ممنوع

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

نویسندگان

1 دانشگاه صنعتی خواجه نصیرالدین طوسی

2 استادیار گروه سیستم های اطلاعات مکانی و عضو قطب علمی مهندسی فناوری اطلاعات مکانی، دانشگاه صنعتی خواجه نصیرالدین طوسی

چکیده

یکی از راه‌های کاهش حجم ترافیک و میزان مصرف سوخت، استفاده از سرویس‌های حمل و نقل برای کارکنان ادارات و شرکت‌های بزرگ و کارخانه‌هاست. برنامهریزی و تخصیص خودروها به کارکنان سازمانها و تعیین مسیرهای جمع آوری آنها از مسائل اصلی این پژوهش می‌باشد. اینگونه مسائل را "مسئله مسیریابی وسایل نقلیه" می‌گویند که در دسته مسائل پیچیده بهینه‌سازی چند هدفه قرار می‌گیرند. هدف اصلی این مقاله ارائه روشی برای تجزیه این مسئله به چند مسئله تک هدفه و نیز ارائه روشی جدید برای مسیریابی می‌باشد. لذا در این مقاله ابتدا با استفاده از الگوریتم k میانگین بهبود یافته، مسئله ی مورد تحقیق تبدیل به چند مسئله تک هدفه گردیده و سپس با تلفیق الگوریتم saving و الگوریتم جستجوی ممنوع، کوتاه‌ترین مسیر محاسبه می گردد. نتایج نشان می‌دهد که استفاده از تلفیق الگوریتم saving و جستجوی ممنوع، نتایج بهتری نسبت به استفاده از الگوریتم جستجوی ممنوع به تنهایی دارد. والگوریتم تلفیقی سرعت بیشتری در رسیدن به پاسخ نهایی دارد.

کلیدواژه‌ها

موضوعات


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

Optimization Of office Transportation System by using Clustering k-means method and Saving and Tabu Search Hybrid Algorithm

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

  • hosein shurvarzi 1
  • ahid naeimi 1
  • mohamad taleai 2
1 K.N.Toosi University of technology
2 Assistant professor of GIS department, Faculty of geodesy and geomatic engineering, K.N.Toosi university of technology
چکیده [English]

abstract: Taking the advantage of transportation services for employees corporate, offices and factories is one of the outstanding solutions to reduce traffic congestion and fuel consumption. In this way planning and allocation of vehicles to passengers and also determining the transportation routes are major problems. Such problems are known as Vehicle Routing Problem (VRP) that fall into category of complex multi-purpose optimization problem. This paper attempts to simplify the problem by breaking it into several simple and single-purpose problems and also to propose a novel approach for path finding. At first, VRP converts to several single-purpose problems, using improvement k-means algorithm. Then, a hybrid method based on Saving and Tabu Search algorithms is developed to find shortest path. Results show that hybrid method of Saving and Tabu Search algorithms is better and faster than using only Tabu. Keywords: Vehicle Routing Problems (VRP), Tabu Search Algorithm, Saving Algorithm, K-means Algorithm, GIS

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

  • Vehicle Routing Problems (VRP)
  • Tabu Search Algorithm
  • Saving Algorithm
  • K-means Algorithm
  • GIS
- Bochtis, D. D. and Sorensen, C. G. (2010) "The vehicle routing problem in field logistics: Part II," vol. 105, February 2010, pp. 180-188.
- Brandão, José (2011) "A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem," vol. 38, January 2011, pp. 140-151.
- Chen, Kai (2011) "Mitigating congestion by integrating time forecasting and realtime information aggregation in cellular networks", Florida International University.
- Chen, Ping, Huang, Hou-kuan and Dong, Xing-Ye (2010). "Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem", Expert Syestems with Applications, Vol. 37, No. 2,March 2010, pp, 16201627.
- Cordeau, Jean-Francois and Maischberger, Mirko (2012) "A parallel iterated tabu search heuristic for vehicle routing problems,", Computers and Operations Research, vol. 39, No. 9, September 2012, pp. 2033-2050.
- Du, Lingling and He, Ruhan (2012) "Combining nearest neighbor search with tabu search for largescale vehicle routing problem", International Conferecne on Solid State Devices and Materials Science, April 1-2, 2012, Macao, pp. 1536-1546.
- Fatahi, Parviz (2009) "Metaheuristic algorithms", Hamedan: Bu-Ali Sina University Press.
- Glover, Fred and Laguna, Manuel (1997) "Tabu search", USA: Kluwer Academic.
- Jayaswal, Sachin(2012) "A Comparative Study of Tabu Search and Simulated Annealing for Traveling Salesman Problem," University of Waterloo. Khabar khodro (2007) "News organization automobile and related industries", http://khabarkhodro.com .
- Kuo, Yiyo and Wang, Chi-Chang (2012) "A variable neighborhood search for the multi-depot vehicle routing problem with loading cost", Expert Syestems with Applications, vol. 39, June 2012, pp. 6949-6954.
- Lysgaard, Jens (1997) "Clarke & Wright's Savings Algorithm", The Aarhus School of Business, Aarhus.
- Mirzaei Ali, Hossein Nakhai Kamalabadi, Isa and Zegordi, Hesamedin (2012) "A new algorithm for solving the inventory routing problem with direct shipment", Journal of Production & Operations Management, Vol 2, Fall 2012, pp. 1-28 .
- Modares, Abdohamid (2010) "A Tabu search algorithm for optimization in distribution plan, institute for humanities and cultural studies," Journal of Transportation, vol 4, Winter 2010, pp. 351-365.
- Motieyan, Hamid, Mesgari, Mohammad Sadi and Naeimi, Ahid (2012) "Optimization of office transportation system by using clustering and genetic algorithms", Journal of Transportation Engineering, vol 3, Summer 2012, pp. 365-378.
- Riera-Ledesma, Jorge and Salazar-Gonzalez, Juan-Jose (2012) "Solving school bus routing using the multple vehicle traveling purchaser problem: A branch-and-cut approach,", Computers and Opeerations Research, vol. 39, No. 2, February 2012, pp. 391-404.
- Ren, Yingtao, Dessouky, Maged and Ordóñez, Fernando (2010) "The multi-shift vehicle routing problem with overtime", University of Southern California, January 2010.
-Tandise, Mohsen and Rezaie, Mohammad Reza (2013) "Strategic planning for sustainable urban transport in the metropolis of Iran (Case Study: Mashhad City)," Journal of Transportation Engineering, vol 5, No 1, Fall 2013, pp. 1-18.
- Xindong, Wu, Kumar, V., Ross Quinlan, J. Ghosh, Joydeep , Yang, Qiang, Motoda, Hiroshi , J.McLachlan, Geoffrey Ng, Angus , Liu, Bing, Philip, S. , Zhi-Hua Zhou, Yu, Steinbach, Michael (2007) "Top 10 algorithms in data mining", Knowledge Information System, Vol. 14, vol. 14, pp. 1-37.
- Xu, Jiuping, Yan, Fang and Li, Steven. (2011). "Vehicle routing optimization with soft time windows in a fuzzy random environment,"http://www.sciencedirect. com/science/article/ 47, March 2011, pp. 1075- 1091.
- Yousefi Khoshbakht, M. and Sedighpour, M. (2011) "A modified elite ant colony algorithm for solving multiple travelling salesman problem", Journal of Operational Research and ITS applications (Journal of applied mathematics), Vol 8, No 3, Fall 2011, pp. 83-96.