Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Formulation of a linear programming model

  1. Jul 18, 2011 #1


    User Avatar

    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?

  2. jcsd
  3. Jul 18, 2011 #2


    User Avatar
    Science Advisor
    Gold Member

    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!.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook