ELECTRIC VEHICLE ROUTING PROBLEM USING ADAPTIVE SIMULATED ANNEALING

Prayoga Yudha Pamungkas, Rifdah Zahabiyah, Nadiah Ghina Shabrina

Abstract


Road transport is a major CO2 emission contributor globally. To tackle the challenge of reducing world carbon emissions, alternative technologies for the automobile industry are widely researched. The automotive industry has started to shift from Internal combustion engine (ICE) vehicles to electric vehicles (EVs), where EVs are the future of the automotive industry in terms of reducing greenhouse gas emissions and air pollution. EV manufacturers are continuously looking for opportunities to optimize the supply chain processes, aiming for supply chain resilience.  In this study, we present an Electric Vehicle Routing Problem (EVRP) to achieve the best decision, which is an extension of the traditional Vehicle routing problem (VRP) which in particular finding the shortest route for electric vehicles. The objective function is to find the best travel route that minimizes travel distance. Each route serves a set of customer nodes that starts and ends at a given depot node. We take battery capacity and charging stations as the constraints. In addition, the use of homogenous fleets and single depot are considered in this paper. A hybrid metaheuristic approach is used to find the best solution with the Adaptive Simulated Annealing algorithm. The use of adaptive in simulated annealing generates a higher probability of finding the best operators, which results in better solutions. A comparison of results from various metaheuristic methods is also presented in this paper to get the best method for the EVRP based on a benchmark dataset. This paper ends with recommendations for creating a routing plan that is resilient to disruptions to distribution.


Keywords


Electric Vehicle Routing Problem; Adaptive Simulated Annealing; Metaheuristic

Full Text:

PDF

References


M. Mavrovouniotis, C. Menelaou, S. Timotheou, Christos Panayiotou, G. Ellinas, M. Polycarpou. Benchmark Set for the IEEE WCCI-2020 Competition on Evolutionary Computation for the Electric Vehicle Routing Problem, Technical Report 2020, KIOS CoE, University of Cyprus, Cyprus, March 2020.

Jing, W., Yan, Y., Kim, I., & Sarvi, M. (2016). Electric vehicles: A review of network modelling and future research needs. Advances in Mechanical Engineering, 8(1), doi:10.1177/1687814015627981

Kucukoglu, I., Dewil, R., & Cattrysse, D. (2021). The electric vehicle routing problem and its variations: A literature review. Computers and Industrial Engineering, 161(August), 107650. https://doi.org/10.1016/j.cie.2021.107650

Biswas, T. K., Abbasi, A., & Chakrabortty, R. K. (2021). An MCDM integrated adaptive simulated annealing approach for influence maximization in social networks. Information Sciences, 556, 27–48. https://doi.org/10.1016/j.ins.2020.12.048

Greene, J. W., & Supowit, K. J. (1986). Simulated Annealing Without Rejected Moves. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 5(1), 221–228. https://doi.org/10.1109/TCAD.1986.1270190

Erdogan, N., Kucuksari, S., & Murphy, J. (2022). A multi-objective optimization model for EVSE deployment at workplaces with smart charging strategies and scheduling policies. Energy, 254, 124161. https://doi.org/10.1016/j.energy.2022.124161

Carey, N., & Steitz, C. (2021, July 14). EU proposes effective ban for new fossil-fuel cars from 2035. Reuters. https://www.reuters.com/business/retail-consumer/eu-proposes-effective-ban-new-fossil-fuel-car-sales-2035-2021-07-14/

Cheramin, M., Saha, A. K., Cheng, J., Paul, S. K., & Jin, H. (2021). Resilient NdFeB magnet recycling under the impacts of COVID-19 pandemic: Stochastic programming and Benders decomposition. Transportation Research Part E: Logistics and Transportation Review, 155, 102505. https://doi.org/10.1016/j.tre.2021.102505

Mehrotra, S., Rahimian, H., Barah, M., Luo, F., & Schantz, K. (2020). A model of supply-chain decisions for resource sharing with an application to ventilator allocation to combat COVID-19. Naval Research Logistics (NRL), 67(5), 303–320. https://doi.org/10.1002/nav.21905

Erdoĝan, S., & Miller-Hooks, E. (2012). A Green Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100–114. https://doi.org/10.1016/j.tre.2011.08.001

Schneider, M., Stenger, A., Goeke, D. (2014). The electric vehicle routing problem with time windows and recharging stations. Transportation Science. 48 (4), 500–520. http: //dx.doi.org/10.1287/trsc.2013.0490.

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. https://doi.org/10.1016/j.trc.2016.01.013

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. https://doi.org/10.1016/j.tre.2014.09.003

Comert, S. E., & Yazgan, H. R. (2023). A new approach based on hybrid ant colony optimization-artificial bee colony algorithm for multi-objective electric vehicle routing problems. Engineering Applications of Artificial Intelligence, 123(April), 106375. https://doi.org/10.1016/j.engappai.2023.106375

Bruglieri, M., Pezzella, F., Pisacane, O., & Suraci, S. (2015). A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics, 47, 221–228. https://doi.org/10.1016/j.endm.2014.11.029

Bruglieri, M., Mancini, S., Pezzella, F., Pisacane, O., & Suraci, S. (2017). A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges. Electronic Notes in Discrete Mathematics, 58, 95–102. https://doi.org/10.1016/j.endm.2017.03.013

Bruglieri, M., Paolucci, M., & Pisacane, O. (2023). Computers and Operations Research A matheuristic for the electric vehicle routing problem with time windows and a realistic energy consumption model. 157(April).

Fisher, M. L. (1994). Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees. Operations Research, 42(4), 626-642. doi:10.1287/opre.42.4.626.

Glover, F., & Kochenberger, G. A. (2003). Handbook of Metaheuristics. New York: Kluwer Academic Publisher.

Braekers, K., Ramaekers, K., & Nieuwenhuyse, I. V., The vehicle routing problem: state of the art classification and review, Computers & Industrial Engineering, vol. 99, pp. 300-313, 2015.




DOI: https://doi.org/10.21776/ub.jemis.2023.011.01.4

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.