Interesting research directions that emerged as a result of the project are:
- Theoretical time complexity transitions NP -> P -> NP in the continuum of
mixed routing - scheduling problems as we move from shop scheduling to
vehicle routing by removing types of constraints. Can there be
other cyclic time complexity transitions? Is this phenomenon unique or can
it be observed in other problem classes?
- Transformations of associated graphs. We observed that
there can be graph transformations that influence the
behaviour of algorithms for finding solutions to the VRP and JSP.
Can we come up with classes of such transformations, not
just single examples? If these classes exist, can we optimize the desired
output of the transformations?
- Symmetry and Local Search.
A deeper understanding needs to be
developed of how symmetry influences
the quality of local search techniques for scheduling problems.
- Reformulation of algorithms. Are there analogies elsewhere
to the demonstrated similarity of arc consistency and the Gale
Shapley algorithm for Stable Marriage?
History for more details.