This paper addresses a novel variant of the Vehicle Routing Problem that integrates two modern logistics problems: the use of electric vehicles and the optimisation of profit through zone-based pricing. The proposed problem, referred to as the Electric Vehicle Routing Problem with Zone-based Pricing, involves planning routes that maximise the profit, defined as the revenue obtained from serving a subset of customers that accept the service minus the travel energy costs. To tackle this complex problem, we propose two evolutionary algorithms as solution methods: a Genetic Algorithm, which searches directly in the space of potential routing solutions, and Genetic Programming, which evolves constructive heuristics that generate solutions. Experimental results demonstrate that Genetic Programming outperforms the Genetic Algorithm in all problem instances considered.