مسأله مسیریابی وسایل نقلیه سبز و کاهش انتشار آلودگی

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

نویسندگان

1 دانشجوی دکتری‌، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

2 دانشیار، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

3 استادیار، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

چکیده

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

کلیدواژه‌ها


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

Green Vehicle Routing Problem and Emissions Minimization

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

  • B Abdoli 1
  • S.A. Mirhassani 2
  • F. Hooshmand 3
1 Ph.D. Student, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
2 Associate Professor, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.
3 Assistant Professor, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
چکیده [English]

The vehicle emissions mainly depend on the amount of consumed fuel, type of fuel and traveled distance. One way to combat with greenhouse gases and air pollution associated with oil consumption is to use alternative energy sources. However, the lack of infrastructures such as refueling stations is one of the major barriers to the adoption of alternative-fuel vehicles. In this study, as an operational approach for transition period, we propose a model to extend the vehicle routing problem to green vehicles. This is a NP-Hard problem, and consequently it is very difficult to solve the real-world instances. Therefore, we propose a solving method based on benders decomposition that equipped with a set of valid inequalities. Implementation of proposed algorithm on randomly generated problems leads to acceptable results in a reasonable time.
 
 

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

  • Green Vehicle Routing Problem
  • Alternative Fuel Vehicles
  • Greenhouse Gases
  • Valid Cuts
  • Benders Decomposition
-Andreas, A. K. & Smith, J. C., (2009), "Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network. Networks", Volume 53(2),
pp. 91-103.
-Benders, J. F., (1962), "Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik", Volume 4(1), pp. 238-252.
-Bisschop, J., (2012), "AIMMS-optimization Modeling". Harlem: Paragon Decision Technology., s.l.: s.n.
-Canhong Lin, et al., (2014), "Survey of Green Vehicle Routing Problem: Past and future trends". Expert Systems with Applications, Volume 41, pp. 1118–1138.
 
-Cordeau, J. F., Pasin, F. & Solomon, M. M., (2006), "An integrated model for logistics network design". Annals of Operations Research, Volume 144(1), pp. 59-82.
Cordeau, J. F., Soumis, F. & Desrosiers, J., (2000), "A Benders decomposition approach for the locomotive and car assignment problem". Transportation Science, Volume 34(2), pp. 133-149.
-Cote, G. & Laughton, M., (1984), "Large-scale mixed integer programming: Benders-type heuristics". European Journal of Operational Research, Volume 16,
pp. 327-333.
-Erdogan, S. & MillerHooks, E., (2012), "A Green Vehicle Routing Problem". Transportation Research Part E, Volume 48, pp. 100-114.
-Gleesonand, J. & Ryan, J., (1990), "Identifying Minimally Infeasible Subsystems of Inequalities". ORSA Journal on Computing, 2(1), pp. 61-63.
-Jin, M., Liu, K. & Bowden, R., (2007), "A two stage algorithm with valid inequalities for the split delivery vehicle routing problem". International journal of production economics, Volume 105, pp. 228-242.
-Kara, I., Kara, B. & Yetis, M., (2007), Energy minimizing vehicle routing problem. Lecture notes in computer science, Volume 4616,
pp. 62-71.
-Kuo, Y., (2010), "Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem". Computers & Industrial Engineering, Volume 59(1), pp. 157-165.
-Magnanti, T. & Wong, R., (1981), Accelerating Benders decomposition algorithmic enhancement and model selection criteria. Operational Research, Volume 29,
pp. 464-484.
-McDaniel, D. & Devine, M., (1977),
"A modified Benders partitioning algorithm for mixed integer programming". Management Science, Volume 24, pp. 312-319.
-Parker, M. & Ryan, J., (1996), "Finding the Minimum Weight IIS Cover of an Infeasible System of Linear Inequalities". Ann. Math. Artificial Intelligence, Volume 17,
pp. 107-126.
-Rei, W., Gendreau, M., Cordeau, J. F. & Soriano, P., (2006), "Accelerating Benders decomposition by local branching". Montreal, s.n.
-Rojowski, R. & Pinto, J. M., (2004), "Efficient MILP Formulations and Valid Cuts for Muliproduct Pipeline Scheduling". Computers and Chemical Engineering, Volume 28, No. 8, pp. 1511-1528.
-Saharidis, G. K. D. , Boile, M. & Theofanis, S., (2011), "Initialization of the Benders master problem using valid inequalities applied to fixed-charge network problems". Expert Systems with Applications, Volume 38(6),
pp. 6627-6636.
-Saharidis, G. K. D. & Ierapetritou, M. G., (2013), Speed-up Benders decomposition using maximum density cut (MDC) generation. Ann Oper Res, Volume 210, pp. 101-123.
-Saharidis, G. K. D. , Minoux, M. & Ierapetritou, M. G., (2010), "Accelerating Benders method using covering cut bundle generation". International Transactions in Operational Research, Volume 17,
pp. 221-237.
-Saharidis, G. K. D. & Ierapetritou, M. G., (2009a), "Resolution method for mixed integer bi-level linear problems based on decomposition technique. Journal of Global Optimization, Volume 44(1), pp. 29-51.
-Saharidis, G. K. D. & Ierapetritou, M. G., (2009b), "Scheduling of loading and unloading of crude oil in a refinery with optimal mixture preparation. Industrial & Engineering Chemistry Research, Volume 48(5),
pp. 2624-2633.
-Salimifard, K., Shahbandarzadeh, H. & Raeesi, R., (2012), "Green transportation and the role of operationS research". Singapore, s.n.
-Sbihi, A. & Eglese, R. W., (2007a), Combinatorial Optimization and green logistics. 4OR: A Quarterly Journal of Operations Research, Volume 5, pp. 99-116.
-Sbihi, A. & Eglese, R. W., (2007b), "The relationship between vehicle routing and scheduling and green logistics – a literature survey". Working paper, Department of Management Science, Lancaster University Management School, LA14YX, UK.
-Schneider, M., Stenger, A. & Goeke, D., (2012), "The electric vehicle routing problem with time windows and recharging stations, Kaiserslautern, Germany", Technical Report, University of Kaiserslautern.
-Van Roy, T. J., (1983), "Cross decomposition for mixed integer programming". Mathematical Programming, Volume 25, pp. 46-63.
-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, Volume 39(7), pp. 1419-1431.
-Zakeri, G., Philpott, A. B. & Ryan, D. M., (1998), "Inexact cuts in Benders decomposition". SIAM Journal on Optimization, Volume 10(3), pp. 643-657.