کاهش انرژی مصرفی و زمان سفر در مساله مسیریابی وسائط نقلیه با در نظر گرفتن سرعت‌های سفر وابسته به زمان توسط الگوریتم رقابت استعماری

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

نویسندگان

دانشگاه تهران

چکیده

در این مقاله، مساله مسیریابی وسائط نقلیه با هدف کاهش انرژی مصرفی و زمان‌های طی مسیر در شرایطی که سرعت‌های سفر وابسته به زمان هستند مورد بررسی قرار می‌گیرد. این مساله به تعیین مسیرهای بهینه برای ناوگانی از وسائط نقلیه می‌پردازد به طوری‌که زمان طی مسیر میان نقاط (مشتریان) به زمانی از روز که سفر در آن نقطه آغاز می‌شود وابسته است. زمان دقیق سفر با دانستن زمان عزیمت و یک تخمین دقیق از سرعت متوسط وسیله نقلیه در آن مسیر محاسبه می‌شود. از این رو در ادامه به ارائه‌ی یک مدل ریاضی جدید برای کاهش زمان طی مسیر می‌پردازیم و از آنجایی که مساله مسیریابی وسائط نقلیه مورد بررسی از نوع مسایل NP-Hard است ازروش فراابتکاری رقابت استعماری (ICA) استفاده می‌شود. به همین جهت تعدادی از مسایل با در نظر گرفتن سرعت‌های سفر متغیر در بازه‌های زمانی مختلف موردبررسی قرار گرفته است و سپس برای نشان دادن کارایی الگوریتم طراحی شده جواب‌های به دست آمده با روش بهینه‌سازی انبوه ذرات (PSO) مقایسه می‌شوند.

کلیدواژه‌ها

موضوعات


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

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

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

  • Narges Norouzi
  • Reza Tavakkoli-Moghaddam
University of Tehran
چکیده [English]

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.     

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

  • Vehicle routing problem
  • Energy Consumption
  • Imperialist competitive algorithm
  • Particle Swarm Optimization

[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.