Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.

2 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.

Abstract

The use of an Electric Vehicle (EV), particularly in different operations of goods distribution is a solution for salvaging the crowded cities of the world from air and noise pollutions as well as Green House Gas (GHG) emission. This paper presents a Multi-Depot Electric Vehicle Routing Problem (MD-EVRP) with recharging stations by considering the expected penalty of fuzzy time windows in pickup/delivery. Since the MD-EVRP with Fuzzy Time Windows and Pickup/Delivery (MD-EVRP-FTW-PD) constraints is an NP-hard problem, three meta-heuristics (i.e., Simulated Annealing (SA), Variable Neighborhood Search (VNS) and a hybrid of SA and VNS (VNS-SA)) are used to solve such a hard problem. The parameters of these algorithms are measured by the Taguchi experimental design method. The proposed hybrid VNS-SA algorithm is more efficient in comparison with other algorithms.

Keywords

Main Subjects

[1]       Energy and Air Pollution (2016). Retrieved August 20, 2020, from https://www.iea.org/reports/energy-and-air-pollution.
[2]       Fallah, M., Tavakkoli-Moghaddam, R., Alinaghian, M., & Salamatbakhsh-Varjovi, A. (2019). A robust approach for a green periodic competitive VRP under uncertainty: DE and PSO algorithms. Journal of intelligent & fuzzy systems36(6), 5213-5225.
[3]       Looking for something? (n.d.). Retrieved August 14, 2020, from https://www.iea.org/publications/freepublications/publication/co2-emissions-from-fuel-combustion-highlights-2016.html
[4]       Sperling, D. (2018). Three revolutions: steering automated, shared, and electric vehicles to a better future. Island Press, Washington, DC, the USA.
[5]       Giechaskiel, B., Joshi, A., Ntziachristos, L., & Dilara, P. (2019). European regulatory framework and particulate matter emissions of gasoline light-duty vehicles: A review. Catalysts, 9(7), 586.
[6]       Yong, J. Y., Ramachandaramurthy, V. K., Tan, K. M., & Mithulananthan, N. (2015). A review on the state-of-the-art technologies of electric vehicle, its impacts and prospects. Renewable and sustainable energy reviews, 49, 365-385.
[7]       Zhao, Y., Noori, M., & Tatari, O. (2016). Vehicle to Grid regulation services of electric delivery trucks: Economic and environmental benefit analysis. Applied energy, 170, 161-175.
[8]       International Energy Agency. (2018). Key world energy statistics 2018. OECD Publishing.
[9]       Zhang, S., Chen, M., Zhang, W., & Zhuang, X. (2020). Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations. Expert systems with applications, 145, 113-123.
[10]   Truck Voucher Incentive Program. (2015). Retrieved August 15, 2020, from https://www.nyserda.ny.gov/All%20Programs/Programs/Truck%20Voucher%20Program
[11]   Hannisdahl, O. H., Malvik, H. V., & Wensaas, G. B. (2013, November). The future is electric! The EV revolution in Norway—explanations and lessons learned. 2013 world electric vehicle symposium and exhibition (EVS27) (pp. 1-13). IEEE.
[12]   Foltyński, M. (2014). Electric fleets in urban logistics. Procedia-social and behavioral sciences151, 48-59.
[13]   Patar, K. B., Kumar R. H, P., Jain, R. R. K., & Pati, S. (2018). Methodology for retrofitting electric power train in conventional powertrain-based three-wheeler. Journal of applied research on industrial engineering5(3), 263-270.
[14]   Liu, B. D. (2004). Uncertainty theory: an introduction to its axiomatic foundations. New York: Springer-Verlag Berlin Heidelberg.
[15]   Çatay, B. (2010). A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert systems with applications, 37(10), 6809-6817.
[16]   Fan, J. (2011). The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction. Procedia engineering, 15, 5284-5289
[17]   Wang, C., & Qiu, Y. (2011). Vehicle routing problem with stochastic demands and simultaneous delivery and pickup based on the cross-entropy method. In Advances in automation and robotics, Vol. 2 (pp. 55-60). Springer, Berlin, Heidelberg.
[18]   Setak, M., Azizi, V., & Karimi, H. (2015). Multi depots capacitated location-routing problem with simultaneous pickup and delivery and split loads: formulation and heuristic methods. Journal of industrial engineering research in production systems, 2(4), 67-81.
[19]   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.
[20]   Laporte, G. (2009). Fifty years of vehicle routing. Transportation science, 43, 408-416.
[21]   Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
[22]   Tavakkoli-Moghaddam, R., Meskini, M., Nasseri, H., & Tavakkoli-Moghaddam, H. (2019, September). A multi-depot close and open vehicle routing problem with heterogeneous vehicles. 2019 international conference on industrial engineering and systems management (IESM) (pp. 1-6). IEEE.
[23]   Thibbotuwawa, A., Bocewicz, G., Nielsen, P., & Banaszak, Z. (2020). Unmanned aerial vehicle routing problems: a literature review. Applied sciences, 10(13), 4504.
[24]   Zaker, M., Kheirkhah, A., & Tavakkoli-Moghaddam, R. (2020). Solving a multi-depot location-routing problem with heterogeneous vehicles and fuzzy travel times by a meta-heuristic algorithm. International journal of transportation engineering, 7(4), 415-431.
[25]   Zarandi, M. H. M., Hemmati, A., & Davari, S. (2011). The multi depot capacitated location routing problem with fuzzy travel times. Expert systems with applications, 38(8), 10075–84.
[26]   Du, J. M., Li, X., Yu, L., Dan, R., & Zhou, J. D. (2017). Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming. Information sciences, 399, 201-218.
[27]   Nadizadeh, A. (2017). The fuzzy multi-depot vehicle routing problem with simultaneous pickup and delivery: formulation and a heuristic algorithm. International journal of industrial engineering & production research, 28(3), 325-345.
[28]   Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega76, 85-99.
[29]   Zheng, J. (2020). A vehicle routing problem model with multiple fuzzy windows based on time-varying traffic flow. IEEE access8, 39439-39444.
[30]   Rajak, S., Parthiban, P., & Dhanalakshmi, R. (2020). Multi-depot vehicle routing problem based on customer satisfaction. International journal of services technology and management, 26(2-3), 252-265.
[31]   Artmeier, A., Haselmayr, J., Leucker, M. & Sachenbacher, M. (2010). The shortest path problem revisited: Optimal routing for electric vehicles. Annual conference on artificial intelligence (pp. 309-316). Berlin, Heidelberg: Springer.  
[32]   Lin, J., Zhou, W., & Wolfson, O. (2016). Electric vehicle routing problem. Transportation research procedia, 12, 508-521.
[33]   Mart´ınez-Lao, J., Montoya, F. G., Montoya, M. G. & Manzano-Agugliaro, F. (2017). Electric vehicles in Spain: an overview of charging systems. Renewable & sustainable energy reviews, 77, 970–983.
[34]   Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation research part C: emerging technologies, 65, 111-127.
[35]   Yang, J., & Sun, H. (2015). Battery swap station location-routing problem with capacitated electric vehicles. Computers & operations research, 55, 217-232.
[36]   Schiffer, M., Walther, G. (2017). The electric location routing problem with time windows and partial recharging. European journal of operational research, 260(3), 995-1013.
[37]   Li, Y., Zhang, P. W., & Wu, Y. F. (2018). Public recharging infrastructure location strategy for promoting electric vehicles: a bi-level programming approach.  Journal of cleaner production, 172, 2720-2734.
[38]   Hof, J., Schneider, M., & Goeke, D. (2017). Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops. Transportation research part B: methodological, 97, 102-112.
[39]   Paz, J. C., Granada-Echeverri, M., & Escobar, J. W. (2018). The multi-depot electric vehicle location routing problem with time windows. International journal of industrial engineering computations, 9(1), 123–136.
[40]   Keskin, M. & Çatay, B. (2018). A metaheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & operations research100, 172-188.
[41]   Pelletier, S., Jabali, O. & Laporte, G. (2016). 50th anniversary invited article-goods distribution with electric vehicles: Review and research perspectives. Transportation science, 50(1), 3-22.
[42]   Molla- Alizadeh-Zavardehi, S., Nezhad, S. S., Tavakkoli-Moghaddam, R., & Yazdani, M. (2013). Solving a fuzzy fixed charge solid transportation problem by metaheuristics. Mathematical and computer modelling, 57(5-6), 1543-1558.
[43]   Liou, T. S., & Wang, M. J. (1992). Ranking fuzzy numbers with integral value. Fuzzy sets and systems, 50(3), 247-255.
[44]   Niakan, F., & Rahimi, M. (2015). A multi-objective healthcare inventory routing problem; a fuzzy possibilistic approach. Transportation research part E: logistics and transportation review, 80, 74-94.
[45]   Jiménez, M. (1996). Ranking fuzzy numbers through the comparison of its expected intervals. International journal of uncertainty, fuzziness and knowledge-based systems4(4), 379-388.
[46]   Das, S. K., & Mandal, T. (2017). A new model for solving fuzzy linear fractional programming problem with ranking function. Journal of applied research on industrial engineering, 4(2), 89-96.
[47]   Mahmoudi, F., & Nasseri, S. H. (2019). A new approach to solve fully fuzzy linear programming problem. Journal of applied research on industrial engineering, 6(2), 139-149.
[48]   McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems.Mathematical programming10(1), 147-175.
[49]   Zhang, D., Liu, Y., M’Hallah, R., & Leung, S. C. (2010). A simulated annealing with a new neighborhood structure-based algorithm for high school timetabling problems. European journal of operational research, 203(3), 550-558.
[50]   Fallah, M., Tavakkoli-Moghaddam, R., Salamatbakhsh-Varjovi, A., & Alinaghian, M. (2019). A green competitive vehicle routing problem under uncertainty solved by an improved differential evolution algorithm. International journal of engineering32(7), 976-981.
[51]   Mladenović, N., & Hansen, P., (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097-1100.
[52]   Montgomery, D.C. (1997).Design and analysis of experiments. John Wiley & Sons, New York, the USA.