This paper presents VBEA, the Voting-Based Evolutionary Algorithm, that efficiently solves multi-objective path planning problems with voting and iterative evolutionary improvement. VBEA uses problem decomposition to create an initial population of candidate solutions that are each optimal in a single objective or randomly generated. VBEA then applies social choice theory through voting as a fitness function for the evolutionary algorithm. Each objective is a voter that evaluates the candidate solutions and assigns each of them a score or ranking depending on the voting method used. Voting identifies the top candidates and they are used to create the next generation of solutions. VBEA’s novel hybrid approach combines the ability of voting mechanisms to balance multiple perspectives and priorities with the ability of evolutionary algorithms to iteratively improve solutions to form a dense and diverse Pareto-front approximation. Extensive evaluation in difficult and complex environments demonstrates VBEA’s efficiency and performance.