This paper deals with the car-call allocation problem in vertical transportation in buildings. We have made a wide comparison of different metaheuristic optimization algorithms to identify those with a better performance dealing with the problem. The tested approaches are Differential Evolution (DE), Simulated Annealing with Random Starts (SAR), Artificial Bee Colony (ABC), Bat Algorithm (BA), Bacterial Foraging Optimization Algorithm (BF), Particle Swarm Optimization (PSO), Genetic Algorithm (GA), and Tabu Search (TS). Each algorithm was tested in high-rise building simulations of 10 to 24 floors, with car configurations of 2 to 6 cars. Results proved that the ABC and TS algorithms generally result in better average journey times compared to other methods. It has to be noted that we introduced a new version of the Simulated Annealing, Simulated Annealing with Restarts (SAR), which ranked as the third best algorithm.