TSP with time constraints

[rodj59]

There is another dimension to the TSP in that constraints may exist as to time intervals during which particular nodes or even arcs must be visited or traversed. There may also exist ordering constraints in respect of subsets of visited nodes.

I'm thinking along the lines of dynamically prioritising the nodes & using a constraint satisfaction system which would adjust the costs (distinct from current fields) of arc traversals dynamically in order to satisfy as many of the constraints as possible. There is a process I have used before which simply sums the costs associated with inconsistencies at (inconsistent) conclusion & makes adjustments to priorities to restart the satisfaction cycle in the hope of achieving a more consistent result. The ability of a constraint to force a change in its state is determined by its priority relative the cumulative priority of other constraints either way.

This process is essentially void of heuristics, but seems plausible for this task. Does anyone have any alternate ideas for this problem?

[rodj59]

Every journey starts with the first step. A quick search yielded the idea that a good starting position is to arrange the path so that at each step, the destination added is the one which is closer to a destination already on the path than any other destination not already on the path. This seems to be intuitively what a person would probably do.
The mechanism currently used for distance calculations is a bit simplistic. For serious application the actual travel distance by road is needed since, for example, rivers with limited crossing points may make two destinations appear closer together than they are. My preference,unless there are any better ideas, is to pass a distance calculation function into the tsp() function which it can then use to compute distances.

A note which should maybe be elsewhere, the gaul functions seem to crash if seeded too often on a small dataset, particularly for 3 destinations. I limited it to min(N*(N-1)-1,15) for N destinations.

[rodj59]

You wouldn't want to use it this way but this is the idea.

[rodj59]

TSP_rjm.sql models a typical point-to-point transport operation. Presently only two basic types of job are supported : hourly and point-2-point. P2p jobs can be scheduled to overlap. Hourly jobs cannot. There is no facility at present for multi-stage point-2-point jobs. Presently all changes are made by moving only one destination at a time: hence path_links records must be created for all possibilities(even those not finally consistent). This is developers-only quality code.

[rodj59]

Still not clear whether this is viable. It would be possible to eliminate need for some temporarily inconsistent move options if path segmente of more than one destination at a time were also considered among the options.

Concurrency is possible, though probably not at the path_dest node level since backtracking choices are essentially serial: concurrency here invites conflict. The exploration of costs of considered options may benefit more, through a fork & join type of concurrency.

[rodj59]

I don't have any more time for this. There are some obvious bugs in the last snapshot posted. The need is to make the priority assessment hone in on a solution more rapidly. The other option is to implement similar functions to scale the scoring function in the gaul-based TSP, though I suspect there will be too much time wasted on futile evolutionary search.