> [...] and with a lot of stops inbetween. The new route [...] has at most 3 stops.

I think this explains a lot. Adding a couple of stops adds a lot of time to the total!