Solving the Electric Vehicle Routing Problem Considering the Vehicle Volume Limitation Using a Simulated Annealing Algorithm

Document Type : Original Article

Authors

1 Master of Science in Industrial Engineering, Qazvin Research Branch, Islamic Azad University.

2 Associate Professor, Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University.

Abstract

This study investigates the problem of electric vehicles routings with a limit on the volume of vehicles capacity. In this regard, the fleet which includes some electric vehicles with given limited battery capacities, should also be taken into account in the planning of distribution. To this end, recharge points are provided in the transmission network to recharge the cars and complete their routes if a battery needs to be recharged. As electric vehicles are only used in the distribution of goods, other aspects should also be considered. One of the important aspects of cargo volume limitation is the relatively low cargo space. Sometimes the goods assigned to a vehicle may be justified by the weight limit but the total volume of goods may exceed the freight volume. Thus, in this research, a mathematical programming model for the problem is presented. Then, several problem instances are designed to validate the model. Then a simulated annealing based algorithm is developed to solve large-scale problems for real world applications.

Keywords


  1. Ceschia, S., Schaerf, A., & Stützle, T. (2013). Local search techniques for a routing-packing problem. Computers & industrial engineering66(4), 1138-1149.
  2. Errico, F., Desaulniers, G., Irnich, S., & Schneider, M. (2015). Branch-price-and-cut algorithms for electric vehicle-routing Problems with time Windows (No. 77209). Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
  3. Farazmand, M., & Pishvaee, M. (2018). Multimodal Transportation Network Design Model under Uncertainty Conditions (Case Study: Cement Transportation in Iran). Industrial Management Perspective31, 115-139 (in Persian).
  4. Felipe, Á., Ortuño, M. T., Righini, G., & Tirado, G. (2014). A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review71, 111-128.
  5. Feng, W., & Figliozzi, M. (2013). An economic and technological analysis of the key factors affecting the competitiveness of electric commercial vehicles: A case study from the USA market. Transportation Research Part C: Emerging Technologies26, 135-145.
  6. Figliozzi, M. (2010). Vehicle routing problem for emissions minimization. Transportation Research Record2197(1), 1-7.
  7. Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A tabu search algorithm for a routing and container loading problem. Transportation Science40(3), 342-350.
  8. Hiermann, G., Puchinger, J., Ropke, S., & Hartl, R. F. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research252(3), 995-1018.
  9. Iori, M., & Martello, S. (2010). Routing problems with loading constraints. Top18(1), 4-27.
  10. Junqueira, L., Oliveira, J. F., Carravilla, M. A., & Morabito, R. (2013). An optimization model for the vehicle routing problem with practical three‐dimensional loading constraints. International Transactions in Operational Research20(5), 645-666.
  11. Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies65, 111-127.
  12. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science220(4598), 671-680.
  13. Macrina, G., Pugliese, L. D. P., Guerriero, F., & Laporte, G. (2019). The green mixed fleet vehicle routing problem with partial battery recharging and time windows. Computers & Operations Research101, 183-199.
  14. Montoya, A., Guéret, C., Mendoza, J. E., & Villegas, J. (2015). The electric vehicle routing problem with partial charging and nonlinear charging function (Doctoral dissertation, LARIS).
  15. Mortazavi, S., & Seifbargi, M. (2018). Two-Objective Modeling of Location-Allocation Problem in a Green Supply Chain Considering Transportation System and CO2 Emission. Industrial Management Perspective29, 163-185 (In Persian).
  16. Rad, A., Sadeghi, A., & Ghasemi, B. (2016). Mathematical Modeling of Two-Echelon with Multiple Manufacturers and Transportation in the Supply Chain. Industrial Management Perspective23, 77-100 (in Persian).
  17. Revesz, R. L., Howard, P. H., Arrow, K., Goulder, L. H., Kopp, R. E., Livermore, M. A., ... & Sterner, T. (2014). Global warming: Improve economic models of climate change. Nature News508(7495), 173.
  18. Sassi, O., Cherif-Khettaf, W. R., & Oulamara, A. (2015). Iterated tabu search for the mix fleet vehicle routing problem with heterogenous electric vehicles. In Modelling, Computation and Optimization in Information Systems and Management Sciences (pp. 57-68). Springer, Cham.
  19. Sbihi, A., & Eglese, R. W. (2007). Combinatorial optimization and green logistics. 4OR5(2), 99-116.
  20. Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science48(4), 500-520.
  21. Tarantilis, C. D., Zachariadis, E. E., & Kiranoudis, C. T. (2009). A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems10(2), 255-271.
  22. Vega‐Mejía, C. A., Montoya‐Torres, J. R., & Islam, S. M. (2019). A nonlinear optimization model for the balanced vehicle routing problem with loading constraints. International Transactions in Operational Research26(3), 794-835.
  23. Yang, J., & Sun, H. (2015). Battery swap station location-routing problem with capacitated electric vehicles. Computers & Operations Research55, 217-232.
  24. Zhang, S., Gajpal, Y., Appadoo, S. S., & Abdulkader, M. M. S. (2018). Electric vehicle routing problem with recharging stations for minimizing energy consumption. International Journal of Production Economics203, 404-413.