  The electric vehicle sharing problem (EVSP) arises from the planning and
operation of one-way electric car-sharing 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 expand the knowledge
on the complexity of the EVSP by showing that it is NP-hard to approximate it
to within a factor of $n^{1-\epsilon}$ in polynomial time, for any $\epsilon >
0$, where $n$ denotes the number of customers, unless P = NP. 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 the modeling of the EVSP based on
energy flows in the network. Based on the new model, we propose a relax-and-fix
strategy and an exact algorithm that uses a warm-start solution obtained from
our heuristic approach. We report computational results comparing our
formulation with the best-performing formulation in the literature. The results
show that our formulation outperforms the previous one concerning 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) by the best-performing formulation in the literature, while our
formulation obtained optimal solutions for all instances. To stress our
approaches, two more challenging new sets of instances were generated, for
which we were able to solve $49.5\%$ of the instances, with an average
optimality gap of $2.91\%$ for those not solved optimally.
