StellarGraph

TSP and VRP (Vehicle Routing Problem) with constraints

Hi
I am trying to solve routing problems with network distance (not euclidian) and constraints such as Time Window and Capacity.
There are some papers around TSP and VRP but they do not implement those requirements.

Can StellerGraph support such settings easily?

If yes, what are the requirements?
Thanks!

Hi,

thanks for you interesting in our work.

Currently, StellarGraph does not support algorithms for TSP/VRP.

Can you please point me to the papers you mention? I’ll have a look and let you know if the proposed algorithms are suitable for addition to StellarGraph.

Regards,

P.

Thanks for the respond,

Here is the links to the paper “Attention, Learn To Solve Routing Problems” and its code in GitHub.

Best,

Eli

Hi,

thank you for sending the paper and I apologise for taking so long to respond.

This was a very interesting paper. Unfortunately, solving TSP problems is not in scope for StellarGraph in the short term. However, we will keep this line of work in mind as we move forward.

Thank you for you interest in our work!

P.

Sorry to hear that.
I will continue following after your important work to see if you change your mind.

Best regards,
Eli

Hi Elinas,

I have seen your release notes for 0.11 version and it seems that your product becomes relevant to the work we are doing on TSP, specifically with GCN.

Will you be interested in developing a joint test?

Thanks in advance,

Eli

Hi Eli,

what kind of joint test do you have in mind?

Regards,

P.

Hi Elinas,

The idea is to leverage your experience with Graphs and our expertise in routing to create a joint solution for solving TSP/VRP in real-world settings.

We can make the basic solution part of open source - StellarGraph.

With the Corona Virus, there is an explosion in demand for home delivery and this may be our joint contribution.

What do you think?

Best,

Eli

Hi Eli,

I guess I was just looking for a bit more detail of the kind of collaboration you had in mind and maybe more specifics about how you suggest we can tackle TSP problems with Graph Neural Networks, other than the preliminary research results in the paper you posted earlier in the thread. It is possible to find optimal solutions for large TSPs (see for example Concorde) whereas the posted paper can only find approximate solutions for smaller ones.

If you prefer to talk in private about this feel free to email me at pantelis.elinas@data61.csiro.au.

Regards,

P.