Algorithms for the location problem of electric vehicles charging stations

Authors

  • Yngrith Soares da Silva Universidade Federal do Espírito Santo.
  • Mário Mestria Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo

DOI:

https://doi.org/10.14488/1676-1901.v19i1.3324

Keywords:

Electric vehicles. Optimization. Metaheuristics. Chemical Reaction Optimization. Greedy algorithm.

Abstract

The Problem of Location of Electric Vehicle Charging Stations (PLEVCS) is an important problem in transportation, logistics and involves the determination of an efficient network that guarantees for all customers to access its stations with the minimum travel distance. The problem is NP-hard and complex because involving a number of the constraints and the scale of real-world applications. Thus, the heuristic methods to solve the PLEVCS are fundamental and this paper presents algorithms using an adapted optimization model from the literature. The model selects a set of charging stations to place from the candidate location sites. The objective is to minimize the charging station fixed cost and the electric vehicles travel cost. The model was applied to a metropolitan region using straight-line and realistic trips. The results showed that the algorithms for the PLEVCS found feasible solutions at a low computational time. The proposed algorithms were performed on the existing literature database.

Downloads

Download data is not yet available.

Author Biographies

Yngrith Soares da Silva, Universidade Federal do Espírito Santo.

Mestranda na Universidade Federal do Espríto Santo no Curso de Pós-Graduação em Engenharia Elétrica. Graduada no Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo em Engenharia Elétrica

Mário Mestria, Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo

Doutor em Computação pela Universidade Federal Fluminense. Atualmente é professor titular do Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo. Leciona na Coordenadoria do Curso de Engenharia Elétrica e no Mestrado em Tecnologias Sustentáveis.

References

BAI, R.; WOODWARD, J. R.; SUBRAMANIAN, N.; CARTLIDGE, J. Optimisation of transportation service network using κ-node large neighbourhood search. Computers & Operations Research, v. 89, p. 193-205, 2018. http://dx.doi.org/10.1016/j.cor.2017.06.008

BAOUCHE, F., BILLOT, R., El FAOUZI, N.-E e TRIGU. Efficient allocation of electric vehicles charging stations: optimization model and application to a dense urban network. IEEE Intelligent Transportation Systems, p. 33-43, Paris, 2014.

http://dx.doi.org/10.1109/MITS.2014.2324023

BARBOSA, L. W. G; GAMARANO, C. G.; PEREIRA, A. L. C.; POLICARPO, R. V. S.; MAPA, S. M. S. A Pesquisa em Trade-Offs de Custos Logísticos: Estudo Bibliométrico no Período de 2006 a 2016. Revista Produção Online, v.18, n. 2, p. 641-664, 2018.

http://dx.doi.org/10.14488/1676-1901.v18i2.2882

BASTOS, E. A. Otimizaçao de Seções Retangulares de Concreto Armado Submetidas à Flexo-Compressao Oblíqua Utilizando Algoritmos Genéticos. 2004. 168 f. Dissertação (Mestrado em Engenharia Civil). Universidade Federal do Rio de Janeiro, Rio de Janeiro, 2004.

BEASLEY, J. E. OR-LIBRARY. Disponível em: http://people.brunel.ac.uk/~mastjjb/jeb/info.html. Acesso em: 20 set 2017.

BNEF - Blombeerg New Energy Finance. Disponível em: https://about.bnef.com/. Acesso em: 20 jun. 2017.

CHIYOSHI, F., GALVÃO, R. D. A statistical analysis of simulated annealing applied to the p-median problem. Annals of Operation Research, v. 96, n. 4, p. 61-74, 2000.

http://dx.doi.org/10.1023/A:1018982914742

CHRISTOFIDES, N.; BEASLEY, J. E. A tree search algorithm for the p-median problem. European Journal of Operational Research, v.10, p. 196 – 204, 1982. https://doi.org/10.1016/0377-2217(82)90160-6

COSTA, C. E. S. Aplicação de técnicas de pesquisa operacional na determinação de setores de atendimento de uma concessionária de energia. 2005. 146 f. Dissertação (Mestrado em Métodos Numéricos em Engenharia).Universidade Federal do Paraná, Curitiba, 2005.

CPU Benchmarks. Disponível em: https://www.cpubenchmark.net/cpu_list.php. Acesso em: 23 jul. 2018.

DASKIN, M. S.; MAASS, K. L. Chapter 2 - The p-Median Problem. Springer International Publisinhg Switzerland. 26 f. Suíça, 2015. http://dx.doi.org/DOI 10.1007/978-3-319-13111-5_2

DENATRAN – Departamento Nacional de Trânsito. Disponível em: http://www.denatran.gov.br/estatistica/257-frota-2015. Acesso em:16 abr. 2017.

EDP Portugal. Disponível em: https://www.edp.pt/pt/sustentabilidade/ ied/Pages/veiculoseletricos.aspx. Acesso em: 02 abr. 2017

FEO, A. T.; RESENDE, M., Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, n. 2, p. 109-133. 1995. http://dx.doi.org/10.1007/BF01096763

FUCHIGAMI, H. Y.; MOURA, M. A. S.; BRANCO, F. J. C. Modelos Matemáticos para Programação de Job Shop com Tempos de Setup Independentes da Sequência. Revista Produção Online, v.17, n. 1, p. 245-267, 2017. http://dx.doi.org/10.14488/1676-1901.v17i1.2504

GOOGLE MAPS. Disponível em: https://www.google.com.br/maps. Acesso em: 20 fev. 2017.

GOMES, F. M.; PEREIRA, F. M.; MARINS, F. A. S.; SILVA, M. B. Estudo comparativo entre os métodos gradiente reduzido generalizado e algoritmo genético em otimização com múltiplas respostas. Revista Produção Online, v.17, n. 2, p. 592-619, 2017.

http://dx.doi.org/10.14488/1676-1901.v17i2.2566

HANSEN, P.; MLADENOVIC, N.; PEREZ-BRITOS, D. Variable neighborhood decomposition search. Journal of Heuristics. v. 7, n. 4, p. 335-350, 2001. http://dx.doi.org/10.1023/A:1011336210885

HÖRNER, D. Resolução do problema das p-medianas não capacitado: comparação de algumas técnicas heurísticas. 2009. 104 f. Dissertação. (Mestrado em Engenharia de Produção). Universidade Federal de Santa Catarina, Florianópolis, 2009.

LAM, A. Y. S., Leung Y-W., Chu, X. Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions. IEEE Transactions on Smart Grid, v. 5, n. 6, p. 2846-2856, nov, 2014. http://dx.doi.org/10.1109/TSG.2014.2344684

LAM, A. Y. S.; LI, V. O. K. Chemical-reaction-inspired metaheuristic for optimization. IEEE Transactions on Evolucionary Computacion, v. 14, n. 3, p. 391-399, June, 2010.

http://dx.doi.org/10.1109/TEVC.2009.2033580

MESTRIA, M. A Hybrid heuristic algorithm for the clustered traveling salesman problem. Pesquisa Operacional, Rio de Janeiro, v. 36, n. 1, p. 113-132, 2016.

http://dx.doi.org/10.1590/0101-7438.2016.036.01.0113.

OLIVEIRA, M. G. Sistema de localização de facilidades: uma abordagem para mensuração de pontos de demanda e localização de facilidades. 2012. 91f. Dissertação (Mestrado em Ciências da Computação).Universidade Federal de Goiás, Goiás, 2012.

OSORIO, V. A. G. Carregamento ótimo de veículos elétricos considerando as restrições das redes de distribuição de média tensão. 2013. Dissertação (Mestrado em Engenharia Elétrica). Universidade Estadual Paulista, São Paulo, 2013.

RIECHI, J. L.; TORMOS, B.; HILLEBRAND, M. V. J. Otimização dos custos de frota urbana com uso de modelo combinado de life cycle cost e simulação de Monte Carlo. Revista Produção Online, v.17, n. 2, p. 667-691, 2017. http://dx.doi.org/10.14488/1676-1901.v17i2.2627

ROCHA, A; DORINI, L. B. Algoritmos gulosos: definições e aplicações. Campinas, SP, 53 pp, 2004.

SILVA NETO, C. A.; SOUZA, J. C. S.; SCHILLING, M. T.; SANTOS, M. G. Melhoria da Segurança Dinâmica baseada em análise estocástica e metaheurística. Revista Controle e Automação. V. 23, n. 2, p. 216-230. 2012. Disponível em: http://www.scielo.br/pdf/ca/v23n2/v23n2a08. Acesso em: 08 set 2017.

http://dx.doi.org/10.1590/S0103-17592012000200008

SOUZA, M. J. F. Notas de aula. Universidade Feral de Ouro Preto, Departamento de Computação, Ouro Preto, MG, 2008. Apostila. Disponível em: http://www.inf.ufpr.br/aurora/disciplinas/topicosia/tabu/InteligenciaComputacional.pdf. Acesso em: 13 nov. 2016.

STEINER, M. T. A. Notas de aula. Universidade Federal do Paraná, Programa de Pós-Graduação em Métodos Numéricos em Engenharia, Curitiba, PR, 2003. Apostila.

TRAGANTALERNGSAK, S.; HOLT, J.; RÖNNQVIST, M. An exact method for the twoechelon, single-source, capacited facility location problem. European Journal of Operational Research, Amsterdam, v. 123, p. 473-489, 1999. http://dx.doi.org/10.1016/S0377-2217(99)00105-8

UOL – UNIVERSO ONLINE. São Paulo, Outubro, 2018. Disponível em: https://carros.uol.com.br/noticias/redacao/2018/10/19/bndes-libera-r-67-milhoes-para-fazer-rede-de-recarga-de-carros-eletricos.htm. Acesso em: 19 out 2018.

Downloads

Published

2019-03-15

How to Cite

da Silva, Y. S., & Mestria, M. (2019). Algorithms for the location problem of electric vehicles charging stations. Revista Produção Online, 19(1), 290–320. https://doi.org/10.14488/1676-1901.v19i1.3324

Issue

Vol. 19 No. 1 (2019)

Section

Papers

License

The Journal reserves the right to make spelling and grammatical changes, aiming to keep a default language, respecting, however, the style of the authors.

The published work is responsibility of the (s) author (s), while the Revista Produção Online is only responsible for the evaluation of the paper. The Revista Produção Online is not responsible for any violations of Law No. 9.610 / 1998, the Copyright Act.

The journal allows the authors to keep the copyright of accepted articles, without restrictions


 
This work is licensed under a Creative Commons License .