Is-it possible to run Travelling Sales Person (TSP) in pgRouting (I've got 2.3... installed) with constraints?

A general TSP algorythm or those I've identified in pgRounting solve the TSP problem visiting each nodes (cities) to create the shortest cost path at the end.

I need a more sophisticated solution that enables adding constraints before the calculated related to node (city) order.

Eg.: Say we have 5 points to reach like A B C D and E.

In a regular TSP when starting from A it would answer A -> D -> E -> C -> B [-> A].

Let's assume that we have a package to carry meanwhile from C to E, so C must precede E on that day of traveling.

So, a constraint comes up like: C -> E

The full definition of the call would be:

Do TSP with

  • A B C D E
    • Starting from A (and also finishing here)
    • CONSTRAINT: visit C before E (and maybe more...)

Is there a solution, algorithm, program like this?

  • Welcome to GIS StackExchange ! Please add more context, documentation, links, etc. I've done a little search on web and found : docs.pgrouting.org/2.3/en/src/tsp/doc/… . Is that answer your question ? I think not, it's not so simple, so, add more context. – J. Monticolo May 20 at 10:52
  • To J. Monticolo: There is plenty of context, no need to ask for documentation (?), links etc. pgRouting doesn't support that kind of optimization, only basic TSP. I develop and sell a software package called FleetEngine, which supports more complex constraints. OP can have a look at it, if he likes too. – Uffe Kousgaard May 21 at 5:54
  • pgRouting has an optimization function VRP with Time Windows. Could that help? docs.pgrouting.org/2.6/en/pgr_gsoc_vrppdtw.html#pgr-gsocvrppdtw – dkastl May 21 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.