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

References

  1. Ceschia, S., Schaerf, A., & Stützle, T. (2013). Local search techniques for a routing-packing problem. Computers & industrial engineering, 66(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 Perspective, 31, 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 Review, 71, 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 Technologies, 26, 135-145.
  6. Figliozzi, M. (2010). Vehicle routing problem for emissions minimization. Transportation Research Record, 2197(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 Science, 40(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 Research, 252(3), 995-1018.
  9. Iori, M., & Martello, S. (2010). Routing problems with loading constraints. Top, 18(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 Research, 20(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 Technologies, 65, 111-127.
  12. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(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 Research, 101, 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 Perspective, 29, 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 Perspective, 23, 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 News, 508(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. 4OR, 5(2), 99-116.
  20. Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(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 Systems, 10(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 Research, 26(3), 794-835.
  23. Yang, J., & Sun, H. (2015). Battery swap station location-routing problem with capacitated electric vehicles. Computers & Operations Research, 55, 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 Economics, 203, 404-413.

Files

Share

How to cite

Statistics