Abstract
The Asymmetric Traveling Purchaser Problem (ATPP) is a generalization of the Asymmetric Traveling Salesman Problem with several applications in the routing and the scheduling contexts. This problem is defined as follows. Let us consider a set of products and a set of markets. Each market is provided with a limited amount of each product at a known price. The ATPP consists in selecting a subset of markets such that a given demand of each product can be purchased, minimizing the routing cost and the purchasing cost. The aim of this article is to evaluate the effectiveness of a branch-and-cut algorithm based on new valid inequalities. It also proposes a transformation of the ATPP into its symmetric version, so a second exact method is also presented. An extensive computational analysis on several classes of instances from literature evaluates the proposed approaches. A previous work () solves instances with up to 25 markets and 100 products, while the here-presented approaches prove optimality on instances with up to 200 markets and 200 products.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balas, E. and S.M. Ng. (1989). “On the Set Covering Polytope: I. All the Facets With Coefficients in {0,1,2}.” Mathematical Programming, 43, 57–69.
Balas, E. and M. Oosten. (2000). “On the Cycle Polytope of a Directed Graph.” Networks, 36, 34–46.
Boctor, F.F., G. Laporte, and J. Renaud. (2003). “Heuristics for the Traveling Purchaser Problem.” Computers and Operations Research, 30(4), 491–504.
Burstall, R.M. (1966). “A Heuristic Method for a Job Sequencing Problem.” Operational Research Quarterly, 17, 291–304.
Buzacott, J.A. and S.K. Dutta. (1971). “Sequencing Many Jobs on a Multipurpose Facility.” Naval Research Logistics Quarterly, 18, 75–82.
Fischetti, M., A. Lodi, and P. Toth. (2002). Exact Methods for the Asymmetric Traveling Salesman Problem.” Kluwer Academic Publishers, Dordrecht, chapter 4, 169–206.
Fischetti, M., J.J. Salazar, and P. Toth. (1997). “A Branch-and-Cut Algorithms for the Symmetric Generalized Traveling Salesman Problem.” Operations Research, 45, 378–394.
Fischetti, M. and P. Toth. (1997). “A Polyhedral Approach to the Asymmetric Traveling Salesman Problem.” Management Science, 43, 1520–1536.
Golden, B.L., L. Levy, and R. Dahl. (1981). “Two Generalizations of the Traveling Salesman Problem.” Omega, 9, 439–445.
Grötschel, M. and M.W. Padberg. (1985). Polyhedral Theory. Wyley, Chichester. chapter 8, pp. 251–305.
Jonker, R. and T. Volgenant. (1983). “Transforming Asymmetric into Symmetric Traveling Salesman Problems.” Operations Research Letters, 2, 161–163.
Jünger, M., G. Reinelt, and G. Rinaldi (1995). The Traveling Salesman Problem. North–Holland, Amsterdam chapter 4.
Jünger, M. and S. Thienel. (1998). “Introduction to ABACUS—a Branch-and-Cut System.” Operations Research Letters, 22, 83–95.
Karp, R.M. (1972). “Reducibility Among Combinatorial Problems.” In Miller, R.E. and J.W. Thatcher. (ed.), Complexity of Computer Computations. New York: Plenum Press, pp. 85–103.
Laporte, G., J. Riera-Ledesma, and J.J. Salazar-Gonz´lez. (2003). “A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem.” Operations Research, 51(6), 940–951.
Ong, H.L. (1982). “Approximate Algorithms for the Traveling Purchaser Problem.” Approximate Algorithms for the Traveling Purchaser Problem 1, 201–205.
Padberg, M.W. (1975). “A Note on Zero-One Programming.” Operations Research, 23, 833–837.
Pearn, W.L. and R.C. Chien. (1998). “Improved Solutions for the Traveling Purchaser Problem.” Computers & Operations Research, 25, 879–885.
Ramesh, T. (1981). “Traveling Purchaser Problem.” Opsearch, 18, 78–91.
Riera-Ledesma, J. (2002). The Traveling Purchaser Problem. PhD thesis, DEIOC, Universidad de La Laguna.
Riera-Ledesma, J. and J.J. Salazar-Gonz´lez. (2005). “A Heuristic Approach for the Travelling Purchaser Problem.” European Journal of Operational Research, 162, 142–152.
Singh, K.N. and D.L. van Oudheusden. (1997). “A Branch and Bound Algorithm for the Traveling Purchaser Problem.” European Journal of Operational Research, 97, 571–579.
Voß, S. (1996). “Dynamic Tabu Search Strategies for the Traveling Purchaser Problem.” Annals of Operations Research, 63, 253–275.
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by “Ministerio de Ciencia y Tecnología” (TIC2003-05982-C05-02), and by Vicerrectorado de Investigación y Desarrollo Tecnológico de la Universidad de La Laguna.
Rights and permissions
About this article
Cite this article
Riera-Ledesma, J., Salazar-González, JJ. Solving the asymmetric traveling purchaser problem. Ann Oper Res 144, 83–97 (2006). https://doi.org/10.1007/s10479-006-0014-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-006-0014-y