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

Document Type : Scientific - Research

Authors

1 K.N.Toosi University of technology

2 k.N.Toosi University of technology

3 Assistant professor of GIS department, Faculty of geodesy and geomatic engineering, K.N.Toosi university of technology

Abstract

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

Keywords

Main Subjects

References

- 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.
Quarterly Journal of Transportation Engineering
Volume 7, Issue 4
July 2016
Pages 665-678

Files

History

  • Receive Date: 22 June 1393
  • Revise Date: 15 October 1394
  • Accept Date: 19 October 1394

Share

How to cite

Statistics