The Travelling Purchaser Problem with Budget Constraint

Sumathi P; Viswanatha Reddy G; Purusotham Singamsetty

doi:https://doi.org/10.14445/22315373/IJMTT-V66I2P515

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 66 | Issue 2 | Year 2020 | Article Id. IJMTT-V66I2P515 | DOI : https://doi.org/10.14445/22315373/IJMTT-V66I2P515

The Travelling Purchaser Problem with Budget Constraint

Sumathi P, Viswanatha Reddy G, Purusotham Singamsetty

Citation :

Sumathi P, Viswanatha Reddy G, Purusotham Singamsetty, "The Travelling Purchaser Problem with Budget Constraint," International Journal of Mathematics Trends and Technology (IJMTT), vol. 66, no. 2, pp. 126-137, 2020. Crossref, https://doi.org/10.14445/22315373/IJMTT-V66I2P515

Abstract

The traveling purchaser problem (TPP) is an NP-hard problem in the family of combinatorial optimization. The purchaser needs to buy several items with variable demands which are available at different marketplaces. The cost of travelling between different marketplaces and a list of available items together with the price of such item at each marketplace is known. The objective of the TPP is to design an optimal tour such that the purchaser tour starts and ends at a home point/ domicile point, purchases all the required items on travelling through a subset of marketplaces exactly once and which satisfy the budget constraint i.e. the total purchasing cost of the items should not surpass the pre-defined budget threshold. The tour may not necessary contain all the marketplaces. This problem finds interesting applications in machine scheduling, transportation logistics among others. The problem is nicely designed with zero-one integer programming. In order to find optimum solution for this problem, an exact algorithm called Lexi-search algorithm is proposed, it searches feasible solutions systematically and with effective bounding and backtracking strategies quickly moves towards the optimal solution.

Keywords

Travelling purchaser problem, Lexi-search Algorithm, Budget threshold, Backtracking.

References

[1] Bentley, J.J. ‘Fast Algorithms for Geometric Traveling Salesman Problems’. INFORMSORSA Journal on Computing,1992; 4 (4).https://doi.org/10.1287/ijoc.4.4.387.
[2] Boctor FF, Laporte G, Renaud J. ‘Heuristics for the traveling purchaser problem’. Computers & Operations Research 2003;30(4):491–504.
[3] Burstall, R.M. ‘A heuristic method for a job sequencing problem’, Operational Research Quarterly 17, 1966: 291304.
[4] Buzacott JA, Dutta SK. Sequencing many jobs on a multipurpose facility. Naval Research Logistics Quarterly 1971;18:75–82.
[5] Daniele Manerba.,Renata Mansini., and Jorge Riera-Ledesma. ‘The Traveling Purchaser Problem and its Variants’. European Journal of Operational Research, 2017; Pages 1-41. DOI: 10.1016/j.ejor.2016.12.017.
[6] Ehrgott, M. and Gandibleux, X. 2000. An Annotated Bibliography of Multi-objective Combinatorial Optimization. Technical Report 62/2000, Fachbereich Mathematik, Universitat Kaiserslutern.
[7] Goldbarg M.C, Bagi L.B, Goldbarg E.F.G., 2009. ‘Transgenetic algorithm for the Traveling Purchaser Problem’. European Journal of Operational Research 199 (2009) 36–45.
[8] Golden BL, Levy L, Dahl R. Two generalizations of the travelling salesman problem. Omega 1981;9:439–45
[9] Hamed Farrokhi., Reza Tavakkoli-Moghaddam., and Esmat Sangari. 2017. ‘Meta- heuristics for a bi-objective location-routing-problem in waste collection management’. Journal of Industrial and Production Engineering. DOI : 10.1080/21681015.2016.1253619.
[10] Infante, D., Giuseppe Paletta., and Francesca Vocaturo. ‘A ship-truck intermodal transportation problem’. Maritime Economics and Logistics, 2009; 11 (3), 247–259.
[11] Jorge Riera-Ledesma and Juan José Salazar-González. ‘A heuristic approach for the Travelling Purchaser Problem'. European Journal of Operational Research, 2005; 162 (1) : 142-152.
[12] Kyle Booth, E. C., Tony Tran, T., Christopher Beck, J. 2016. ‘Logic-Based Decomposition Methods for the Travelling Purchaser Problem’. International Conference on Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems. pp 55-64.
[13] Laporte, G., Riera-Ledesma, J., and Salazar-Gonzalez, J.J. 2003. ‘A branch-and-cut algorithm for the undirected travelling purchaser problem’. Operations Research, 51 (6). https://doi.org/10.1287/opre.51.6.940.24921.
[14] Mansini R, Pelizzari M, Saccomandi R. ‘An effective tabu search algorithm for the capacitated traveling purchaser problem’. Technical Report 10–49, Dipartimento di Elettronica per l'Automazione, University of Brescia; 2005.
[15] Nemhauser, G.L. and Wolsey, L. 1999. ‘Integer and Combinatorial Optimization’. John Wiley and Sons, New York, USA.
[16] Ong HL. ‘Approximate algorithms for the traveling purchaser problem’. Operations Research Letters 1982;1:201–5.
[17] Pearn WL, Chien RC. ‘Improved solutions for the traveling purchaser problem’. Computers & Operations Research 1998;25:879–85.
[18] Peder Wikström and Ljusk Ola Eriksson. 2000. ‘Solving the stand management problem under biodiversity-related considerations’. Forest Ecology and Management,126 (3) : 361-376. https://doi.org/10.1016/S0378-1127(99)00107-3.
[19] Ramesh, T. 1981. ‘Travelling purchaser problem’. Opsearch, 18 : 78–91
[20] Raquel Bernardino., and Ana Paias. 2018. ‘Meta-heuristics based on decision hierarchies for the traveling purchaser problem’. International Transactions in Operational Research 2.34. DOI :10.1111/itor.12330.
[21] Ravi, R., and Salman, F.S., 1999. ‘Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design’. In: Nesetril, J. (Ed.), Algorithms - ESA’ 99. Vol. 1643 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 29-40.
[22] Renata Mansini and Barbara Tocchella 2009. ‘The travelling purchaser problem with budget constraint’. Computers and Operations Research, 36 (7) : 2263-2274. https://doi. 10.1016/j.cor.2008.09.001.
[23] Renaud, J., Boctor, F.F., and Laporte, G. 2002. ‘Perturbation heuristics for the pickup and delivery travelling salesman problem’. Computers and Operations Research, 29 : 1129–1141.
[24] Singh, K.N. and van Oudheusden, D.L. 1997. ‘A branch and bound algorithm for the travelling purchaser problem’. European Journal of Operational Research, 97 : 571–579.
[25] Sundara Murthy, M. (1979): Combinatorial Programming: A Pattern Recognition Technique Approach, a PhD thesis, REC Warangal, India (Unpublished).
[26] Voß, S. 1996. ‘Dynamic tabu search strategies for the travelling purchaser problem’. Annals of Operations Research, 63 (2) : 253–275.