Vehicle routing is a major concern for a distribution channel of any supply chain. It plays a crucial role in attaining a competitive advantage for a company by being cost efficient or responsive. Transportation as a key logistics activity represents a relevant component (generally from 10% to 20%) of the final cost of goods, and one third to two thirds of the cost of logistics. The literature recently shifted towards the use of more energy efficient vehicles. Electric vehicles are characterized by being energy efficient, and do not produce polluting gas emissions such as carbon dioxide. However, the electric vehicles suffer from the limited capacity of the battery and the large charging time. In this paper, the dispatching and routing of battery-operated electric vehicles is considered. The vehicles can move at variable speeds when moving from a customer to another. When the speed is fast, the charge is depleted fast and small number of customers are served in a route. While when the speed is slow, the charge is depleted slowly, and more customers can be accommodated in a route. A genetic algorithm is developed to solve the problem. A piece linear range function based on finite speeds is proposed, as the average speed is used in planning for a given route in real life. A proposed genetic algorithm is proposed and applied on many cases from the literature. The results show that the model is able to optimize the performance and that the model behavior is consistent.