The pathfinding for trains and road vehicles is, in my last profiles at least, relatively insignificant. There are things that waste more time. The following are the top 10 most consuming methods in a 'random' game (PSG132 final). This game had roughly 600 trains, 600 road vehicles, 60 ships and 30 aircraft.
23.83 DeterministicSpriteGroup::Resolve(ResolverObject*) const
7.99 VehicleGetVariable(Vehicle*, ResolverObject const*, unsigned char, unsigned int, bool*)
3.59 Md5::Process(unsigned char const*)
3.26 Vehicle::ShowVisualEffect() const
2.81 GetNewVehiclePos(Vehicle const*)
2.62 GetGlobalVariable(unsigned char, unsigned int*, GRFFile const*)
2.43 GetCustomEngineSprite(unsigned short, Vehicle const*, Direction, EngineImageType)
2.26 Blitter_8bppOptimized::Draw(Blitter::BlitterParams*, BlitterMode, ZoomLevel)
2.20 TrainLocoHandler(Train*, bool)
In total they represent 50% of OpenTTD's running time. I ran this for about a minute which is why MD5 processing is still in the list, which is done when scanning the NewGRFs. Roughly 4% was spent on scanning NewGRFs. All pathfinding combined takes about 0.25%!
The updating of the state of the game takes 80%. Another 5% is from starting OpenTTD, meaning that the actual drawing takes 15% of the CPU time. Most of this 15% is spent pushing graphics to the video card, which is done in a seperate thread so you won't bother OpenTTD's game loop.
In this game roughly 50% of CPU is spent determining the (new) image to draw for the vehicles by querying the NewGRF. Improving that is where you can get a significant speed improvement. Not by splitting pathfinding or drawing or vehicle moving to a seperate threads.
So please, before saying X or Y is slow, please do some profiling to at least get an idea what is actually slow and what isn't.