Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (Assuming sizes between 8x8 and 30x30. Using C or C++ if that matters) Or, is this so complex that it would take way longer?

There is an area, where an automated traveler follows a shortest path algorithm at all times. Playing the builder, find the way to maximize the number of points the traveler must visit.

The area is typically between 8x8 and 30x30, given in the form:

.F......
......a.
........
........
.....1X.
........
.A......
........
..O.....
.X......
..X.....
..X.....

Where there is:

• Always a single O, the starting point

• Always a single F, the ending point

• Always many ., empty points that can either be traveled or built on

• Sometimes X, points designating they are blocked for traveling or building

• Sometimes pairs of letters (i.e. A and a, but never F, O, or X), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter

• Sometimes numbers (i.e. 1), designating waypoints

The automated traveler follows a shortest path algorithm at all times. It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point. The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination. If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots. The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken. (Otherwise, can choose any of the multiple s

Just a note: even the simpler version without waypoints and teleports is NP-hard:

Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3, and $X$s are placed "around" them (the dots are "corridors"). Put the $O$ in a corner and the $F$ near it with a dot in the middle.

Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a "corridor", i.e. it removes an edge of $G$).

StackExchange Computer Science Q#105509, answer score: 2