On the approximability and energy-flow modeling of the electric vehicle sharing problem

Autor(es)

Silva, Welverton R. ; Usberti, Fabio L. ; Schouery, Rafael C. S.

• Tipo de documento: Artigo Científico
• Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 192, p. 16-pg., 2024-05-08.

Resumo

The electric vehicle sharing problem (EVSP) arises from the planning and operation of one-way electric carsharing systems. It aims to maximize the total rental time of a fleet of electric vehicles while ensuring that all the demands of the customer are fulfilled. In this paper, we first show that the EVSP is NP -hard to approximate to within a factor of n(1-epsilon )in polynomial time, for any epsilon > 0 , where n denotes the number of customers. In addition, we also show that the problem does not have a monotone structure, which can be detrimental to the development of heuristics employing constructive strategies. Moreover, we propose a novel approach for modeling the EVSP based on energy flows. Based on this new model, we propose a relax-and-fix strategy and an exact algorithm. Our computational results show that our formulation outperforms the previous best-performing formulation in the literature in the number of optimal solutions obtained, optimality gaps, and computational times. Previously, 32.7% of the instances remained unsolved (within a time limit of one hour), while our formulation obtained optimal solutions for all instances. To stress our approaches, two more challenging new sets of instances are generated, for which we can solve 49.5% of the instances, with an average optimality gap of 2.91% for those not solved optimally. (AU)

• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático