An Electric Vehicle Routing Problem with Battery Swap and Battery Recharge Approach

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Semnan University, Semnan, Iran.

2 Department of Industrial Engineering, Semnan University, Semnan, Iran

10.22070/jqepo.2021.5270.1140

Abstract

This study integrates the problem of locating and routing electric and conventional vehicles besides considering greenhouse gases emission. This problem is a subset of the problems of locating and routing and the green routing problem in which a combination of electric and conventional vehicles is used. The advantage of this model is the aid of the utilization of electric vehicle technology to reduce the elimination of greenhouse gases. This model can be used in the design of the transport and logistics system of organizations and companies. Many models have been developed and applied concerning electric vehicles. However, this type of composition and its use is subject to environmental requirements to reduce greenhouse gas emissions. We also assumed the capability of recharging and battery replacement in the model. The model for different samples was solved using GAMS software and a multi-objective particle swarm optimization (MOPSO) algorithm. Besides, the impact of increasing the tax on greenhouse gas (GHG) emissions was tested on electric vehicle usage, amount of GHG emissions, and system costs. The results show that the model can be used to design the transport and logistics systems of organizations to impose the least charges besides emitting the least greenhouse gases.

Keywords

References

(EPA), E. P. A. 2020. https://www.epa.gov/regulations-emissions-vehicles-and-engines/regulations-greenhouse-gas-ghg-emissions[Online].  [Accessed].
AFRODITI, A., BOILE, M., THEOFANIS, S., SDOUKOPOULOS, E. & MARGARITIS, D. 2014. Electric vehicle routing problem with industry constraints: trends and insights for future research. Transportation Research Procedia, 3, 452-459.
APAYDIN, O. & GONULLU, M. T. 2008. Emission control with route optimization in solid waste collection process: A case study. Sadhana, 33, 71-82.
ARCHETTI, C. & SPERANZA, M. G. 2012. Vehicle routing problems with split deliveries. International transactions in operational research, 19, 3-22.
ASADI-GANGRAJ, E., NAYERI, S. J. I. J. O. O. R. & SYSTEMS, I. 2018. A Hybrid Approach Based on LP Metric Method and Genetic Algorithm for the Vehicle-Routing Problem with Time Windows, Driver-Specific Times, and Vehicles-Specific Capacities. 9, 51-67.
BEKTAŞ, T. & LAPORTE, G. 2011. The pollution-routing problem. Transportation Research Part B: Methodological, 45, 1232-1250.
BERBEGLIA, G., CORDEAU, J.-F., GRIBKOVSKAIA, I. & LAPORTE, G. 2007. Static pick-up and delivery problems: a classification scheme and survey. Top, 15, 1-31.
BRÄYSY, O. & GENDREAU, M. 2005a. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation science, 39, 104-118.
BRÄYSY, O. & GENDREAU, M. 2005b. Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation science, 39, 119-139.
CAMPBELL, A. M. & WILSON, J. H. 2014. Forty years of periodic vehicle routing. Networks, 63, 2-15.
ÇATAY, B. & KESKIN, M. The impact of quick charging stations on the route planning of electric vehicles.  2017 IEEE Symposium on Computers and Communications (ISCC), 2017. IEEE, 152-157.
CHEN, X., FENG, L. & SOON ONG, Y. J. I. J. O. S. S. 2012. A self-adaptive memeplexes robust search scheme for solving stochastic demands vehicle routing problem. 43, 1347-1366.
ÇIMEN, M., SOYSAL, M. J. T. R. P. D. T. & ENVIRONMENT 2017. Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm. 54, 82-98.
COELLO, C. A. C., LAMONT, G. B. & VAN VELDHUIZEN, D. A. 2007. Evolutionary algorithms for solving multi-objective problems, Springer.
COELLO, C. A. C. C. & PULIDO, G. T. A micro-genetic algorithm for multi-objective optimization.  International Conference on Evolutionary Multi-Criterion Optimization, 2001. Springer, 126-140.
COMMISSION, E. 2020. https://ec.europa.eu/clima/policies/transport/vehicles/regulation_en [Online].  [Accessed].
CREVIER, B., CORDEAU, J.-F. & LAPORTE, G. J. E. J. O. O. R. 2007. The multi-depot vehicle routing problem with inter-depot routes. 176, 756-773.
DANTZIG, G., FULKERSON, R. & JOHNSON, S. 1954. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2, 393-410.
DEB, K., PRATAP, A., AGARWAL, S. & MEYARIVAN, T. J. I. T. O. E. C. 2002. A fast and elitist multi-objective genetic algorithm: NSGA-II. 6, 182-197.
DESAULNIERS, G., ERRICO, F., IRNICH, S. & SCHNEIDER, M. J. O. R. 2016. Exact algorithms for electric vehicle-routing problems with time windows. 64, 1388-1405.
EBERHART, R. C. & SHI, Y. J. I. T. O. E. C. 2004. Guest editorial special issue on particle swarm optimization. 8, 201-203.
 
ERDOĞAN, S. & MILLER-HOOKS, E. 2012. A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48, 100-114.
ERDOĞAN, S., MILLER-HOOKS, E. J. T. R. P. E. L. & REVIEW, T. 2012. A green vehicle routing problem. 48, 100-114.
ERERA, A. L., MORALES, J. C. & SAVELSBERGH, M. J. T. S. 2010. The vehicle routing problem with stochastic demand and duration constraints. 44, 474-492.
EUCHI, J. 2017. Genetic scatter search algorithm to solve the one-commodity pick-up and delivery vehicle routing problem. Journal of Modelling in Management, 12, 2-18.
FAGERHOLT, K. 1999. Optimal fleet design in a ship routing problem. International transactions in operational research, 6, 453-464.
FELIPE, Á., ORTUÑO, M. T., RIGHINI, G. & TIRADO, G. 2014a. 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.
FELIPE, Á., ORTUÑO, M. T., RIGHINI, G., TIRADO, G. J. T. R. P. E. L. & REVIEW, T. 2014b. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. 71, 111-128.
GLOCK, C. H. & KIM, T. 2015. Coordinating a supply chain with a heterogeneous vehicle fleet under greenhouse gas emissions. The International Journal of Logistics Management, 26, 494-516.
GOLDBERG, D. E. J. S. T. A. O. G.-G. A. F. D. W. S. O. C. I. E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley, Reading, MA.
GOLDEN, B. L., MAGNANTI, T. L. & NGUYEN, H. Q. 1977. Implementing vehicle routing algorithms. Networks, 7, 113-148.
GOVINDAN, K., SOLEIMANI, H. & KANNAN, D. J. E. J. O. O. R. 2015. Reverse logistics and closed-loop supply chain: A comprehensive review to explore the future. 240, 603-626.
HIERMANN, G., PUCHINGER, J., ROPKE, S. & HARTL, R. F. J. E. J. O. O. R. 2016. The electric fleet size and mix vehicle routing problem with time windows and recharging stations. 252, 995-1018.
HOF, J., SCHNEIDER, M. & GOEKE, D. 2017a. 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.
HOF, J., SCHNEIDER, M. & GOEKE, D. J. T. R. P. B. M. 2017b. Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops. 97, 102-112.
HSUEH, C.-F. 2016. The green vehicle routing problem with stochastic travel speeds. CICTP 2016.
KARA, I., KARA, B. Y. & YETIS, M. K. Energy minimizing vehicle routing problem.  International Conference on Combinatorial Optimization and Applications, 2007. Springer, 62-71.
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.
 
KESKIN, M., ÇATAY, B., LAPORTE, G. J. C. & RESEARCH, O. 2020. A Simulation-Based Heuristic for the Electric Vehicle Routing Problem with Time Windows and Stochastic Waiting Times at Recharging Stations. 105060.
KESKIN, M., ÇATAY, B. J. C. & RESEARCH, O. 2018. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. 100, 172-188.
KNOWLES, J. D. & CORNE, D. W. J. E. C. 2000. Approximating the nondominated front using the Pareto archived evolution strategy. 8, 149-172.
KUO, Y. 2010. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59, 157-165.
LAPORTE, G. 2009. Fifty years of vehicle routing. Transportation Science, 43, 408-416.
LENSTRA, J. K. & KAN, A. R. 1981. Complexity of vehicle routing and scheduling problems. Networks, 11, 221-227.
LI, X., SHI, X., ZHAO, Y., LIANG, H. & DONG, Y. J. A. S. 2020. SVND Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem. 10, 441.
LI, Y., LIM, M. K. & TSENG, M.-L. 2019. A green vehicle routing model based on modified particle swarm optimization for cold chain logistics. Industrial Management & Data Systems, 119, 473-494.
LIAO, C.-S., LU, S.-H. & SHEN, Z.-J. M. 2016. The electric vehicle touring problem. Transportation Research Part B: Methodological, 86, 163-180.
LIN, C., CHOY, K. L., HO, G. T., CHUNG, S. H. & LAM, H. 2014a. Survey of green vehicle routing problem: past and future trends. Expert systems with applications, 41, 1118-1138.
LIN, C., CHOY, K. L., HO, G. T., CHUNG, S. H. & LAM, H. J. E. S. W. A. 2014b. Survey of green vehicle routing problem: past and future trends. 41, 1118-1138.
LIN, J., ZHOU, W. & WOLFSON, O. 2016. Electric vehicle routing problem. Transportation Research Procedia, 12, 508-521.
MADEN, W., EGLESE, R. & BLACK, D. 2010. Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, 61, 515-522.
MARAŠ, V. 2008. Determining optimal transport routes of inland waterway container ships. Transportation Research Record, 2062, 50-58.
MCKINNON, A. 2007. CO2 Emissions from Freight Transport in the UK. Commission for Integrated Transport, London.
MONTOYA-TORRES, J. R., FRANCO, J. L., ISAZA, S. N., JIMÉNEZ, H. F. & HERAZO-PADILLA, N. 2015. A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115-129.
MONTOYA, A., GUÉRET, C., MENDOZA, J. E. & VILLEGAS, J. G. 2017. The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103, 87-110.
MOUHRIM, N., ALAOUI, A. E. H. & BOUKACHOUR, J. Vehicle routing problem with mixed fleet of electric and conventional vehicles under emissions allowances.  2018 4th International Conference on Logistics Operations Management (GOL), 2018. IEEE, 1-5.
NAKATA, T. 2000. Analysis of the impact of hybrid vehicles on energy systems in Japan. Transportation Research Part D: Transport and Environment, 5, 373-383.
NANTHAVANIJ, S., BOONPRASURT, P., JARUPHONGSA, W. & AMMARAPALA, V. Vehicle routing problem with manual materials handling: flexible delivery crew-vehicle assignments.  Proceeding of the 9th Asia Pacific industrial engineering and management system conference, Nusa Dua, Bali, Indonesia, 2008.
PALMER, A. 2007. The development of an integrated routing and carbon dioxide emissions model for goods vehicles.
PAZ, J., GRANADA-ECHEVERRI, M. & ESCOBAR, J. J. I. J. O. I. E. C. 2018. The multi-depot electric vehicle location routing problem with time windows. 9, 123-136.
PELLETIER, S., JABALI, O., LAPORTE, G. & VENERONI, M. J. T. R. P. B. M. 2017. Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. 103, 158-187.
PELLETIER, S., JABALI, O. & LAPORTE, G. J. T. R. P. B. M. 2018. Charge scheduling for electric freight vehicles. 115, 246-269.
PELLETIER, S., JABALI, O. & LAPORTE, G. J. T. S. 2016. 50th anniversary invited article—goods distribution with electric vehicles: review and research perspectives. 50, 3-22.
PILLAC, V., GENDREAU, M., GUÉRET, C. & MEDAGLIA, A. L. 2013. A review of dynamic vehicle routing problems. European Journal of Operational Research, 225, 1-11.
POURAZARM, S. & CASSANDRAS, C. G. 2015. System-centric minimum-time paths for battery-powered vehicles in networks with charging nodes. IFAC-PapersOnLine, 48, 111-116.
RABBANI, M., POURREZA, P., FARROKHI-ASL, H. & NOURI, N. 2018. A hybrid genetic algorithm for multi-depot vehicle routing problem with considering time window repair and pick-up. Journal of Modelling in Management, 13, 698-717.
RAHMAN, I., VASANT, P. M., SINGH, B. S. M., ABDULLAH-AL-WADUD, M. & ADNAN, N. 2016. Review of recent trends in optimization techniques for plug-in hybrid, and electric vehicle charging infrastructures. Renewable and Sustainable Energy Reviews, 58, 1039-1047.
RAMSEUR, J. L. & LEGGETT, J. A. 2019. Attaching a Price to Greenhouse Gas Emissions with a Carbon Tax or Emissions Fee: Considerations and Potential Impacts.
SALIMIFARD, K., SHAHBANDARZADEH, H. & RAEESI, R. Green transportation and the role of operation research.  Int. Conf. Traffic Transp. Eng.(ICTTE 2012), 2012. 74-79.
SAMBRACOS, E., PARAVANTIS, J. A., TARANTILIS, C. D. & KIRANOUDIS, C. T. 2004. Dispatching of small containers via coastal freight liners: The case of the Aegean Sea. European Journal of Operational Research, 152, 365-381.
SBIHI, A. & EGLESE, R. W. 2007. Combinatorial optimization and green logistics. 4OR, 5, 99-116.
SCHIFFER, M. & WALTHER, G. 2017. The electric location routing problem with time windows and partial recharging. European Journal of Operational Research, 260, 995-1013.
SCHNEIDER, M., STENGER, A. & GOEKE, D. J. T. S. 2014. The electric vehicle-routing problem with time windows and recharging stations. 48, 500-520.
SHAO, S., GUAN, W., RAN, B., HE, Z. & BI, J. J. M. P. I. E. 2017. Electric vehicle routing problem with charging time and variable travel time. 2017.
TARANTILIS, C. D., ZACHARIADIS, E. E. & KIRANOUDIS, C. T. J. I. J. O. C. 2008. A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. 20, 154-168.
TILLMAN, F. A. J. T. S. 1969. The multiple terminal delivery problem with probabilistic demands. 3, 192-204.
TIWARI, A. & CHANG, P.-C. J. I. J. O. P. E. 2015. A block recombination approach to solve green vehicle routing problem. 164, 379-387.
VINCENT, F. Y., REDI, A. P., HIDAYAT, Y. A. & WIBOWO, O. J. J. A. S. C. 2017. A simulated annealing heuristic for the hybrid vehicle routing problem. 53, 119-132.
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, 1419-1431.
YANG, J., SUN, H. J. C. & RESEARCH, O. 2015. Battery swap station location-routing problem with capacitated electric vehicles. 55, 217-232.
ZHANG, S., CHEN, M. & ZHANG, W. J. J. O. C. P. 2019. A novel location-routing problem in electric vehicle transportation with stochastic demands. 221, 567-581.
Journal of Quality Engineering and Production Optimization
Volume 5, Issue 2
December 2020
Pages 1-20

Files

Share

How to cite

Statistics