TSP with Time Windows

I have created a genetic argorithm that creates routes for workers.
Most work can be completed at any point, however some of the work has
appointment windows (complete 15 minute job between 2-3PM) A normal
route consists of around 40 stops and normally there are a few
appointments (1-5 /max 16)

My first approach was as follows: If appointments are present the
fitness evaluation is based on total completion time for the route
with a waited penalty for wait and late times for appointment work.
When there are less than 3 appointments in the route, the solution is
good. However as more appointments are added to the route, the
solution deteriorates. By adjusting the weights I can improve on this,
however there is a trade off between traveling time and honoring
appointments. Depending on the route distribution and the number of
appointments in the route the weighting has to be adjusted and it is
difficult to determine what optimal weights should be for a particular
route.

Some of the reading I have been done suggests exploring Pareto front.
My second attempt involved implemented a Multi-Objective evolver but
my results were not promising. After reflection my thinking now is
that the appointment work sequence is critical, and any alteration in
the appointment orders destroys the solution. In other words there was
not a trade off from one criteria to another, change a route slightly
could move the solution drastically away from the Pareto front. (Some
chromosome sub-sequences were more important than others)

My second approach was to implement two phases. Phase one optimized
for meeting appointments, shortest distance was also involved in the
fitness evaluation but the weight favored meeting appointment. Phase
two took the best solution's appointments sequence and seeded new
chromosome with it appointment sub-sequences. The sub-sequences were
marked as unmovable within the chromosome and then the new population
was bred for shortest distance (without changing the sequence of the
appointment work).

I was surprised to find that my solution from the first phase was
consistently a better solution then my second phase solution.

A possibly explanation for this is that I explored a more diverse
population with less breeding constraints in my first phase. I'm still
not totally convinced of this but this premise in now motivating my
third approach. My third approach will be to collect the best no
violation appointment solutions from phase 1 and use these to seed my
phase two breeding, again with the constraint of not moving
appointment work.

My question is this, is there anyone out there with experience with a
similar problem. Does this sound like a promising approach or am I
going down an incorrect path? Is there a better approach to this
problem?

Regards
-Peter

.