R.Cordone, R.Wolfler Calvo
"Note on Time Window Constraints in Routing Problems"
96-005.

This note introduces and formalizes some ideas which represent an improvement and an effective generalization of a known methodology to deal with time windows in routing problems. The main one is the concept of  macronode and its properties. The macronode is a collapse of whatever sequence of nodes into a single one easier to handle. Thus, the graph's dimension is hugely reduced and we prove that dealing with solutions as chains of macronodes permits to evaluate their properties (feasibility and objective values) in an extremely simple and fast way. A brief discussion about the tractability of some objective functions closes the paper.
 

[email protected],