I am no shure to have well understand your problem. (My english is very far away in my mind...) But I think that valuated the nodes is perhaps not the good solution.

You can valuate the branches...

This can be done by adding a weight on the branches of the tree.

A weight can be constituted as a vector, wich allow as many dimension as you want, but produce a final result in term of "cost".

Let me give you an example wich is always about roads.

In france we have very small road call "chemin vicinal" with are close to lane. After we have "route departementale" wich is a step over managing by the department (equivalent of state in US), after we get "route nationale" wich are deliver and manage by the country and over we have "autoroute" wich are speedway.

The speed is limit as :

Type of road Km/h Average reduce factor

Vicinal 50 0,8

Departementale 90 0,9

Nationale 90 0,9

Nationale 4 ways 110 0,95

Autoroute 130 0,98

Then we can have some factors that are about where the road is : mountain, or flat land

Flat : 1

Small mountains : 0,85

Heavy mountains : 0,75

Then we can have some factors that are about the quality of surface of the road :

Flat : 1

Small holes : 0,9

Bad surface : 0,75

All thoses factors can be specify for all the branches of the tree. Then we can calculate the real travel time, and deduce that a Mac Truck model 125477 will cost 5444$ to go from Paris to Toulouse with 23t of duties

Is that transposable to your model ?

Thanks