Algorithms for Traveling Purchaser Problem (TPP)

[mathbalduino]

Hey guys, how you doing?

Im here to ask for you help. I am writing my bachelor paper as an implementation/review of the TPP algorithms out there. Almost every paper that I read references the Ramesh algorithm, that returns an exact solution for TPP problems, but I just can't find the algorithm, not even a high level description that I could use to implement my own version.

Does someone know how to implement it? I would be grateful with even a high level description.

There's other two approaches out there that I would be grateful to have access: the branch-and-bound algorithm of Singh and Van Oudheusden, and the branch-and-cut algorithm of Laporte. If someone know how to implement or something like that, please share with me.

In these two papers, you can find the actual references:
- https://ir.nctu.edu.tw/bitstream/11536/31784/1/000075284000001.pdf
- https://www.fsa.ulaval.ca/personnel/renaudj/pdf/Recherche/tpp(purchaser)%20COR.pdf

If you don't know what's the TPP, please see this link: https://en.wikipedia.org/wiki/Traveling_purchaser_problem before answering

Guys, I know that this is an NP-HARD problem, and that it's always best to use Heuristic Algorithms instead of exact ones for larger instances, but I still want to study the exact ones.

Thanks! Any help is very welcome.

 

[pbuk]

Almost every paper that I read references the Ramesh algorithm, that returns an exact solution for TPP problems, but I just can't find the algorithm, not even a high level description that I could use to implement my own version.

Does someone know how to implement it? I would be grateful with even a high level description.

Isn't it described in Ramesh's paper as referenced? The second paper you linked refers to it as "the lexicographic algorithm of Ramesh" so I think it is reasonable to assume that it simply enumerates all paths (in lexicographic order, although this is not really relevant) and selects the optimum.

There's other two approaches out there that I would be grateful to have access: the branch-and-bound algorithm of Singh and Van Oudheusden

Surely this is described in the referenced EJOR article.

and the branch-and-cut algorithm of Laporte

This is described as unpublished however a simple search for the authors' names finds it on JSTOR.

Do you know how to follow up references?

 

[mathbalduino]

Oh man, is obvious that I know how to follow references... Why would I reach this forum and create a post? Isn't it much much more labor than just following the references or searching google?

The thing is, all the referenced papers have paywalls and my university don't provide access to it (including the referenced JSTOR). I cannot afford them, and that's why I though someone could help me in the internet.

Why everyone needs to be hostile on the internet? Couldn't you just help someone that's just asking a question? Man, that's sad...

Anyways, thanks for the reply!

 

[pbuk]

The thing is, all the referenced papers have paywalls and my university don't provide access to it (including the referenced JSTOR).

Really? I suggest you take that up with whoever assigned you the topic for the bachelor paper.

 

[Tom.G]

Way out of my field but it doesn't seem to be available on the net, even in China!

Here is a possibility that may may give some insight though:

"The Travelling Purchaser Problem with Budget Constraint "
https://www.ijmttjournal.org/Volume-66/Issue-2/IJMTT-V66I2P515.pdf

Good Luck!
Tom

 

[mathbalduino]

Way out of my field but it doesn't seem to be available on the net, even in China!

Here is a possibility that may may give some insight though:

"The Travelling Purchaser Problem with Budget Constraint "
https://www.ijmttjournal.org/Volume-66/Issue-2/IJMTT-V66I2P515.pdf

Good Luck!
Tom

Man, there's a dude on Reddit that said that his University has the physical copy of the Ramesh paper. As I'm from Brazil, I'll need to contact the Uni via e-mail or something to ask them if they can send me a copy.

Anyways, thanks for the help, really!

 

[Wrichik Basu]

Why everyone needs to be hostile on the internet? Couldn't you just help someone that's just asking a question?

I just couldn't resist replying to this, even though this is addressed to @pbuk.

After reading pbuk's post, I don't think it is hostile in any way. Following references is the first most obvious thing that people will do, but how are we supposed to know that you have already done that if you do not say so in your 1^st post? If you are asking for help because those papers are behind a paywall, you should have mentioned that in the 1^st post itself.

And if paywall is indeed your main problem, I stand by pbuk's reply that you should take this up with your university or advisor for not providing you access to papers. It is a different issue whether knowledge should be constrained behind paywalls, but if you are doing some research, then it is up to your university to provide you necessary access to journals, and your advisor to arrange for that with the university. We can help you find the papers you need, but unfortunately, we really can't help you with the paywall issue.