Formulation of a linear programming model

[-A-]

Ok, so the title didn't allow me to be too descriptive. Basically, I'm trying to formulate a variant of the time constrained traveling salesman problem. I read a paper "An Exact Algorithm for the Time-Constrained Traveling Salesman Problem" by Edward Baker which formulated this problem of a traveling salesman, who has to visit every given city or node in the graph, with the constraint of each node having an entry and exit time, between which the visit must take place. The objective function minimized the total distance.

My question was what if I had a number of salesmen and I wanted them to visit the cities, each of which have some time constraints. I want to find out how many salesmen I will need for a given graph.

I understand this can be seen as a variant of the vehicle routing problem, My problem is, is it possible to frame this as a linear programming problem with an objective function and constraints?

Thanks.

 

[jambaugh]

I don't think there's a generic way to map the discrete distance function for your problem into a, not only continuous, but linear function over parameters.

As you're trying a discrete to continuous I don't think there is a "natural" way to do this.

Given what I recall about the computational complexity of the traveling salesman problem and the simplicity of linear programming solutions,
I'm going to guess that the short answer to your question is an unqualified NO!.