استفاده از جستجوی همسایگی انطباقی برای حل مساله مسیریابی وسیله نقلیه سبز با گذاشت و برداشت همزمان و پنجره زمانی سخت

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

نویسندگان

دانشگاه علم و صنعت ایران

چکیده

   در اکثر مسایل کلاسیک مسیریابی وسیله نقلیه، هدف اصلی، کمینه کردن کل زمان سفر یا مسافت طی شده است. درحالی­که مساله مسیریابی سبز علاوه­بر اهداف ذکر شده، به مینیمم کردن هزینه‌های سوخت و انتشار گازهای گلخانه‌ای از جمله دی اکسید کربن نیز می‌پردازد. در این مقاله نوعی از مسأله مسیریابی سبز با هدف کاهش هزینه‌های سوخت و انتشار با استفاده از یکی از مدل‌های تخمین مصرف سوخت تحت عنوان مدل یکپارچه انتشار همراه با در نظر گرفتن محدودیت گذاشت و برداشت همزمان و پنجره زمانی سخت توسعه داده شده است. در این مدل زمان سفر ثابت نبوده و سرعت وسایل نقلیه در حرکت بین مشتریان متغیر بوده و با توجه به پنجره زمانی مشتریان تعیین می‌شود. برای حل مدل، روشی ابتکاری مبتنی بر روش جستجوی همسایگی بزرگ انطباقی ارائه شده است. که در این روش، یک الگوریتم ساخت جواب اولیه با معیار انتخاب مشتریان متناسب با محدودیت‌های گذاشت و برداشت همزمان و پنجره زمانی و با فرض متغیر بودن سرعت وسایل نقلیه ارائه شده است. نتایج آزمایشات عددی کارآمدی رویکرد ارائه شده را در حل این مسأله تأیید می‌کند.

کلیدواژه‌ها

موضوعات


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

An Adaptive Large Neighborhood Search Heuristic for the Green Vehicle Routing Problem with Simultaneously Pickup and Delivery and Hard Time Windows

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

  • Setareh Majidi
  • Seyyed-Mahdi Hosseini-Motlagh
  • Saeed Yaghoubi
  • Abbas Jokar
Iran University of Science & Technology
چکیده [English]

The classical models of vehicle routing generally focused on minimizing total distance and travel time, however in green vehicle routing problem the main objective is minimizing total emissions and fuel consumption besides the other objects.
In this paper, extension of GVRP with minimizing fuel and emission costs presented that considered pickup and delivery constraints with hard time windows. Travel time in this model is not constant and speed of vehicles would be determined in regards to customers’ time widows. In this paper, a heuristic based adaptive large neighborhood search proposed for solving the model. Construction algorithm in this method is heuristic based algorithm with proposed criterion according to pick up and delivery constrains and time windows with assumption of variable speed. Computational results confirms efficiency of this algorithm.

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

  • Green vehicle routing problem
  • fuel consumption
  • simultaneously pickup and delivery
  • adaptive large neighborhood search

[1]       Salimifard, K., Shahbandarzadeh, H.,  Raeesi, R. (2012). Green transportation and the role of operation research, international conference on traffic and transportation engineering.

[2]       Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles, PhD thesis. Bedford, United Kingdom:Cranfield University.

[3]       Kara et al. (2007). Energy minimizing vehicle routing problem, Combinatorial optimization and applications, 4616: 62-71.

[4]       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: 515-522.

[5]       Ubeda, S., Arcelus, F. J., Faulin, J. (2011). Green logistics at Eroski: A case study, International Journal of Production Economics, 131(1): 44–51.

[6]       Suzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and pollutants emission, Transportation Research Part D: Transport and Environment, 16(1): 73–77.

[7]       Bektaş, T., Laporte, G. (2011). pollution routing problem, Transportation Research Part B, 45(8): 1232–1250.

[8]       Faulin, J., Juan, A., Lera, F., Grasman, S. (2011). Solving the capacitated vehicle routing problem with environmental criteria based on real estimations in road transportation: a case study", Procedia – Social and Behavioral Sciences, 20: 323–334.

[9]       Xiao, Y., Zhao, Q., Kaku, I., Xu, Y. (2012). "Development of a fuel consumption optimization model for the capacitated vehicle routing problem", Computers & Operations Research, 39(7): 1419–1431.

[10]   Erdoğan, S.,  Miller-Hooks, E. (2012). A green vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review, 48: 100–114.

[11]   Demir, E., Laporte, G. (2012). An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research, 223: 346–359.

[12]   Ramos, T., Oliveira, R. (2011). Delimitation of service areas in reverse logistics networks with multiple depots, Journal of the Operational Research Society, 62: 1198–1210.

[13]   Taha, M., Fors, M. N., Shoukry, A. A. (2014). An Exact Solution for a Class of Green Vehicle Routing Problem, in International Conference on Industrial Engineering and Operations Management.

[14]   Kopfer, H. W., Schönberger, J., Kopfer, H. (2013). Emissions Minimization Vehicle Routing Problem in Dependence of Different Vehicle Classes,  Dynamics in Logistics: 49-58.

[15]   Demir, E., Bektaş, T., Laporte, G. (2014). The bi-objective Pollution-Routing Problem, European Journal of Operational Research, 232: 464–478.

[16]   Çatay, B. (2010). A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Expert Systems with Applications , 10(37): 6809-6817.

[17]   Fan, J. (2011). The Vehicle Routing Problem with Simultaneous Pickup and Delivery Based on Customer Satisfaction, Procedia Engineering, 15: 5284-5289.

[18]   Petersen, H. L., Ropke, S. (2011). The pickup and delivery problem with cross-docking opportunity, Computational Logistics Springer Berlin Heidelberg: 101-113.

[19]   Coelho, I. M. Munhoz, P.L.A. Haddad, M.N., Souza, M.J.F. Ochi, L.S. (2012). A hybrid heuristic based on General Variable Neighborhood Search for the Single Vehicle Routing Problem with Deliveries and Selective Pickups, Electronic Notes in Discrete Mathematics, 39: 99-106.

[20]   Wang, C. Qiu, Y. (2012). Vehicle Routing Problem with Stochastic Demands and Simultaneous Delivery and Pickup Based on the Cross-Entropy Method, Advances in Automation and Robotics, Springer Berlin Heidelberg, 2: 55-60.

[21]   Wang, H. F. Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window, Computers & Industrial Engineering, 62(1): 84–95.

[22]  ستاک مصطفی، عزیزی وحید، کریمی حسین (1393). مساله مکان یابی و مسیریابی چنددپویی ظرفیت دار با برداشت و تحویل همزمان و بارهای برش یافته: مدلسازی و حل ابتکاری، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، شماره 4: 67-81.

[23]   Barth, M., Younglove, T., Scora, G. (2005). Development of a heavy-duty diesel modal emissions and fuel consumption model, California PATH Research Report.

[24]   Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems, in Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming., New York.

[25]   Pisinger, D.R.S. (2007). A General Heuristic for Vehicle Routing Problems, Computers & Operations Research, 34(8): 2403–2435.

[26]   Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum,  23: 79-96.