Travelling Problem with Constraints

Question

Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.

You start your travel at a given node, say $1$, and end your travel at a given node, say $12$. Your travel has $T$ time steps. At time step $t=1$ you must visit one of nodes $\{1,7,4\}$, at time step $t=2$ you must visit one of the nodes $\{7,3,45,9\}$, and so on. In other words, at a given time step, you are given a set with at minimum $1$ and at maximum $K\leq N$ nodes. Choose the nodes for all time steps such that the cumulative distance is minimized.

Am I correct, that such problem is NP hard? Given $T$ time steps and that at most $K$ nodes are possible at each time step, the complexity would be $O(K^T)$, right?

What algorithms could be applicable or useful for such a problem? In my scenario, $T$ can be very large (up to 20,000) but $K$ is rather low (10 on average, at most 100).

(Edit) - I encountered the problem in a diary of a traveller. For example, you know that a traveller started his journey at some location. For every journey entry, besides the raw text, the writer in the title writes a date and a location name.

The problem is there often exist several different coordinates for a location name (i.e., multiple locations exists with the same name). An (I think reasonable) assumption I have come to, is that the shortest possible path (from start to finish) should approximate the travelled route quite well. I have a data set of multiple travellers with diaries like this and want to plot the routes onto a map (and hope to display a travelled route approximately in the way which in it was really travelled).

I have not yet come up with any good and general solution (besides brute-force computing the distance of every possible route, which may be impossible because there exist tons of diary entries and so many location names have multiple possible coordinates).