Minimizing Energy Consumption and Travel Time in a Vehicle Routing Problem with Time-Dependent Speeds Using an Imperialist Competitive Algorithm

Document Type : Research Paper

Authors

University of Tehran

Abstract

In this paper, a new mathematical model for vehicle routing problem is presented. The objectives are to minimize the energy consumption and the travel times in which speeds varied in different hours of the day. Since the vehicle routing problem belongs to the category of NP-hard problems, to solve the problem, a method based on the imperialist competitive algorithm (ICA) is proposed. Finally, the associated results are compared with the results obtained by particle swarm optimization (PSO) on the well-known benchmark problems.     

Keywords

Main Subjects


[1]     Malandraki, C., (1989). Time dependent vehicle routing problems: Formulations, solution algorithms and computations experiments. Ph.D. Dissertation, Northwestern University, Evanston, III.
[2]     Malandraki, C., Daskin, MS., (1992). Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transport Science 26(3): 185–200.
[3]     Malandraki, C., Dial, R.B., (1996). A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research 90: 45–55.
[4]     Ichoua, S., Gendreau, M., Potvin, JY., (2003). Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2): 379–396.
[5]     Fleischmann, B., Gietz, M., Gnutzmann, S., (2004). Time-varying travel times in vehicle routing. Transportation Science, 38(2): 160–173.
[6]     Figliozzi, M. A., (2009). A route improvement algorithm for the vehicle routing problem with time dependent travel times. Proceedings of the 88th Transportation Research Board annual meeting, Washington DC, USA.
[7]     Cooke, K.L., Halsey, E., (1966). The shortest route through a network with time-dependent inter nodal transit times. Journal of Mathematical Analysis and Applications, 14: 492–498.
[8]     Maden, W., Eglese, R.W., Black, D., (2010). Vehicle routing and scheduling with time varying data: a case study. Journal of the Operational Research Society, 61(3): 515–522.
[9]      Palmer, A. (2007). The Development of an integrated routing and carbon dioxide emissions model for goods vehicles. Ph.D. Thesis, Cranfield University, School of Management.
[10] Haghani, A., Jung, S., (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11): 2959–2986.
[11] Lucas, C., Nasiri-Gheidari, Z., Tootoonchian, F. (2010). Application of an imperialist competitive algorithm to the design of a linear induction motor. Energy Conversion and Management, 51(7): 1407–1411.
[12]  نوروزی، ن.، صادق عمل‌نیک، م.، توکلی مقدم، ر. 1394. کاهش انرژی مصرفی در مساله مسیریابی وسائط نقلیه با در نظر گرفتن سرعت‌های سفر وابسته به زمان توسط الگوریتم رقابت استعماری، یازدهمین کنفرانس بین‌المللی مهندسی صنایع، تهران، ایران.
[13] Christofides, N., Mingozzi, A., Toth, P., (1979). The vehicle routing problem. In: Christo- fides, N., Mingozzi, A., Toth, P., Sandi, C. editors. Combinatorial optimization. Chichester, UK: Wiley. 315–318.