The Electric Autonomous Dial-a-Ride Problem (E-ADARP) is defined as the problem of operating a fleet of electric autonomous vehicles (EAVs) that provides ride-sharing services to users that specify the origins, destinations, and preferred arrival time under a series of operational constraints. We propose a hybrid column generation algorithm that integrates a deterministic annealing algorithm to solve E-ADARP. Efficient heuristics are embedded in the column generation to recognize negative reduced cost columns. Extensive experiments are conducted to demonstrate the efficiency of the hybrid scheme and the algorithm performance. Three different energy restriction levels are considered, representing the minimum energy level that vehicles should maintain at the end of the route. For each scenario, adapted benchmark instances from the literature are tested. Compared to the best reported results in the literature, the proposed algorithm improves the computational efficiency by up to 27.81%, and the average gap between best-obtained solutions and state-of-art solutions is 0.89%. Several new best solutions are found on previously unsolved instances with the proposed algorithm, demonstrating the performance of the algorithm.