IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v259y2017i1p1-18.html
   My bibliography  Save this article

The Traveling Purchaser Problem and its variants

Author

Listed:
  • Manerba, Daniele
  • Mansini, Renata
  • Riera-Ledesma, Jorge

Abstract

The Traveling Purchaser Problem (TPP) has been one of the most studied generalizations of the Traveling Salesman Problem. In recent decades, the TPP attracted the attention of both researchers in combinatorial optimization and practitioners, thanks to its double nature of procurement and transportation problem. The problem has been used to model several application contexts and is computationally challenging, dealing at the same time with the suppliers selection, the optimization of the purchasing plan and the routing decisions of the purchaser. For the first time after 50 years from its birth, we survey all the research done on the TPP including the most interesting and best performing solution methods proposed so far. We conclude providing some interesting future developments.

Suggested Citation

  • Manerba, Daniele & Mansini, Renata & Riera-Ledesma, Jorge, 2017. "The Traveling Purchaser Problem and its variants," European Journal of Operational Research, Elsevier, vol. 259(1), pages 1-18.
    • Handle: RePEc:eee:ejores:v:259:y:2017:i:1:p:1-18
    DOI: 10.1016/j.ejor.2016.12.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716310517
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.12.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bianchessi, N. & Mansini, R. & Speranza, M.G., 2014. "The distance constrained multiple vehicle traveling purchaser problem," European Journal of Operational Research, Elsevier, vol. 235(1), pages 73-87.
    2. Jorge Riera-Ledesma & Juan-José Salazar-González, 2006. "Solving the asymmetric traveling purchaser problem," Annals of Operations Research, Springer, vol. 144(1), pages 83-97, April.
    3. Singh, Kashi N. & van Oudheusden, Dirk L., 1997. "A branch and bound algorithm for the traveling purchaser problem," European Journal of Operational Research, Elsevier, vol. 97(3), pages 571-579, March.
    4. Renata Mansini & Barbara Tocchella, 2009. "Effective Algorithms for a Bounded Version of the Uncapacitated TPP," Lecture Notes in Economics and Mathematical Systems, in: Jo A.E.E. Nunen & M. Grazia Speranza & Luca Bertazzi (ed.), Innovations in Distribution Logistics, chapter 14, pages 267-281, Springer.
    5. Riera-Ledesma, Jorge & Salazar-Gonzalez, Juan Jose, 2005. "The biobjective travelling purchaser problem," European Journal of Operational Research, Elsevier, vol. 160(3), pages 599-613, February.
    6. Golden, Bruce & Levy, Larry & Dahl, Roy, 1981. "Two generalizations of the traveling salesman problem," Omega, Elsevier, vol. 9(4), pages 439-441.
    7. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    8. E. Angelelli & R. Mansini & M. Vindigni, 2009. "Exploring greedy criteria for the dynamic traveling purchaser problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 17(2), pages 141-158, June.
    9. Gilbert Laporte & Jorge Riera-Ledesma & Juan-José Salazar-González, 2003. "A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem," Operations Research, INFORMS, vol. 51(6), pages 940-951, December.
    10. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    11. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1992. "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 40(6), pages 1086-1094, December.
    12. Goldbarg, M.C. & Bagi, L.B. & Goldbarg, E.F.G., 2009. "Transgenetic algorithm for the Traveling Purchaser Problem," European Journal of Operational Research, Elsevier, vol. 199(1), pages 36-45, November.
    13. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    14. Graham Kendall & Ruibin Bai & Jacek Błazewicz & Patrick De Causmaecker & Michel Gendreau & Robert John & Jiawei Li & Barry McCollum & Erwin Pesch & Rong Qu & Nasser Sabar & Greet Vanden Berghe , 2016. "Good Laboratory Practice for optimization research," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(4), pages 676-689, April.
    15. M. Bellmore & G. L. Nemhauser, 1968. "The Traveling Salesman Problem: A Survey," Operations Research, INFORMS, vol. 16(3), pages 538-558, June.
    16. Carolina Almeida & Richard Gonçalves & Elizabeth Goldbarg & Marco Goldbarg & Myriam Delgado, 2012. "An experimental analysis of evolutionary heuristics for the biobjective traveling purchaser problem," Annals of Operations Research, Springer, vol. 199(1), pages 305-341, October.
    17. Gendreau, Michel & Manerba, Daniele & Mansini, Renata, 2016. "The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 248(1), pages 59-71.
    18. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    19. Degraeve, Zeger & Labro, Eva & Roodhooft, Filip, 2000. "An evaluation of vendor selection models from a total cost of ownership perspective," European Journal of Operational Research, Elsevier, vol. 125(1), pages 34-58, August.
    20. Riera-Ledesma, Jorge & Salazar-Gonzalez, Juan Jose, 2005. "A heuristic approach for the Travelling Purchaser Problem," European Journal of Operational Research, Elsevier, vol. 162(1), pages 142-152, April.
    21. Petersen, Hanne L. & Madsen, Oli B.G., 2009. "The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches," European Journal of Operational Research, Elsevier, vol. 198(1), pages 139-147, October.
    22. E. Angelelli & R. Mansini & M. Vindigni, 2016. "The Stochastic and Dynamic Traveling Purchaser Problem," Transportation Science, INFORMS, vol. 50(2), pages 642-658, May.
    23. Kang, Seungmo & Ouyang, Yanfeng, 2011. "The traveling purchaser problem with stochastic prices: Exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 209(3), pages 265-272, March.
    24. Davide Infante & Giuseppe Paletta & Francesca Vocaturo, 2009. "A ship-truck intermodal transportation problem," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 11(3), pages 247-259, September.
    25. Robert L. Karg & Gerald L. Thompson, 1964. "A Heuristic Approach to Solving Travelling Salesman Problems," Management Science, INFORMS, vol. 10(2), pages 225-248, January.
    26. Manerba, Daniele & Mansini, Renata, 2012. "An exact algorithm for the Capacitated Total Quantity Discount Problem," European Journal of Operational Research, Elsevier, vol. 222(2), pages 287-300.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zahra Sadat Hasanpour Jesri & Kourosh Eshghi & Majid Rafiee & Tom Van Woensel, 2022. "The Multi-Depot Traveling Purchaser Problem with Shared Resources," Sustainability, MDPI, vol. 14(16), pages 1-26, August.
    2. Palomo-Martínez, Pamela J. & Salazar-Aguilar, M. Angélica, 2019. "The bi-objective traveling purchaser problem with deliveries," European Journal of Operational Research, Elsevier, vol. 273(2), pages 608-622.
    3. Nicola Bianchessi & Stefan Irnich & Christian Tilk, 2020. "A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand," Working Papers 2003, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Christian Tilk & Katharina Olkis & Stefan Irnich, 2020. "The Last-mile Vehicle Routing Problem with Delivery Options," Working Papers 2017, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    5. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    6. Alfandari, Laurent & Ljubić, Ivana & De Melo da Silva, Marcos, 2022. "A tailored Benders decomposition approach for last-mile delivery with autonomous robots," European Journal of Operational Research, Elsevier, vol. 299(2), pages 510-525.
    7. Christian Tilk & Katharina Olkis & Stefan Irnich, 2021. "The last-mile vehicle routing problem with delivery options," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 877-904, December.
    8. Manerba, Daniele & Mansini, Renata & Perboli, Guido, 2018. "The Capacitated Supplier Selection problem with Total Quantity Discount policy and Activation Costs under uncertainty," International Journal of Production Economics, Elsevier, vol. 198(C), pages 119-132.
    9. Gambella, Claudio & Maggioni, Francesca & Vigo, Daniele, 2019. "A stochastic programming model for a tactical solid waste management problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 684-694.
    10. Jaehn, Florian & Meissner, Finn, 2022. "The rebound effect in transportation," Omega, Elsevier, vol. 108(C).
    11. Baldi, Mauro Maria & Manerba, Daniele & Perboli, Guido & Tadei, Roberto, 2019. "A Generalized Bin Packing Problem for parcel delivery in last-mile logistics," European Journal of Operational Research, Elsevier, vol. 274(3), pages 990-999.
    12. Gu, Wenjuan & Archetti, Claudia & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Speranza, M. Grazia, 2024. "Vehicle routing problems with multiple commodities: A survey," European Journal of Operational Research, Elsevier, vol. 317(1), pages 1-15.
    13. Fang, Chao & Han, Zonglei & Wang, Wei & Zio, Enrico, 2023. "Routing UAVs in landslides Monitoring: A neural network heuristic for team orienteering with mandatory visits," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    14. Sharmistha Halder Jana & Biswapati Jana & Barun Das & Goutam Panigrahi & Manoranjan Maiti, 2019. "Constrained FC 4D MITPs for Damageable Substitutable and Complementary Items in Rough Environments," Mathematics, MDPI, vol. 7(3), pages 1-26, March.
    15. Pablo A. Miranda-Gonzalez & Javier Maturana-Ross & Carola A. Blazquez & Guillermo Cabrera-Guerrero, 2021. "Exact Formulation and Analysis for the Bi-Objective Insular Traveling Salesman Problem," Mathematics, MDPI, vol. 9(21), pages 1-33, October.
    16. Mingyu Xiao & Jianan Zhang & Weibo Lin, 0. "Parameterized algorithms and complexity for the traveling purchaser problem and its variants," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-17.
    17. Mingyu Xiao & Jianan Zhang & Weibo Lin, 2022. "Parameterized algorithms and complexity for the traveling purchaser problem and its variants," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2269-2285, November.
    18. Cinar, Ahmet & Salman, F. Sibel & Bozkaya, Burcin, 2021. "Prioritized single nurse routing and scheduling for home healthcare services," European Journal of Operational Research, Elsevier, vol. 289(3), pages 867-878.
    19. Miranda, Pablo A. & Blazquez, Carola A. & Obreque, Carlos & Maturana-Ross, Javier & Gutierrez-Jarpa, Gabriel, 2018. "The bi-objective insular traveling salesman problem with maritime and ground transportation costs," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1014-1036.
    20. Riccardo Giusti & Chiara Iorfida & Yuanyuan Li & Daniele Manerba & Stefano Musso & Guido Perboli & Roberto Tadei & Shuai Yuan, 2019. "Sustainable and De-Stressed International Supply-Chains Through the SYNCHRO-NET Approach," Sustainability, MDPI, vol. 11(4), pages 1-26, February.
    21. Roohnavazfar, Mina & Manerba, Daniele & De Martin, Juan Carlos & Tadei, Roberto, 2019. "Optimal paths in multi-stage stochastic decision networks," Operations Research Perspectives, Elsevier, vol. 6(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Palomo-Martínez, Pamela J. & Salazar-Aguilar, M. Angélica, 2019. "The bi-objective traveling purchaser problem with deliveries," European Journal of Operational Research, Elsevier, vol. 273(2), pages 608-622.
    2. Jaehn, Florian & Meissner, Finn, 2022. "The rebound effect in transportation," Omega, Elsevier, vol. 108(C).
    3. Mingyu Xiao & Jianan Zhang & Weibo Lin, 0. "Parameterized algorithms and complexity for the traveling purchaser problem and its variants," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-17.
    4. Mingyu Xiao & Jianan Zhang & Weibo Lin, 2022. "Parameterized algorithms and complexity for the traveling purchaser problem and its variants," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2269-2285, November.
    5. Carolina Almeida & Richard Gonçalves & Elizabeth Goldbarg & Marco Goldbarg & Myriam Delgado, 2012. "An experimental analysis of evolutionary heuristics for the biobjective traveling purchaser problem," Annals of Operations Research, Springer, vol. 199(1), pages 305-341, October.
    6. Archetti, Claudia & Bertazzi, Luca & Laganà, Demetrio & Vocaturo, Francesca, 2017. "The Undirected Capacitated General Routing Problem with Profits," European Journal of Operational Research, Elsevier, vol. 257(3), pages 822-833.
    7. Riera-Ledesma, Jorge & Salazar-Gonzalez, Juan Jose, 2005. "A heuristic approach for the Travelling Purchaser Problem," European Journal of Operational Research, Elsevier, vol. 162(1), pages 142-152, April.
    8. Bianchessi, N. & Mansini, R. & Speranza, M.G., 2014. "The distance constrained multiple vehicle traveling purchaser problem," European Journal of Operational Research, Elsevier, vol. 235(1), pages 73-87.
    9. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    10. Goldbarg, M.C. & Bagi, L.B. & Goldbarg, E.F.G., 2009. "Transgenetic algorithm for the Traveling Purchaser Problem," European Journal of Operational Research, Elsevier, vol. 199(1), pages 36-45, November.
    11. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    12. E. Angelelli & R. Mansini & M. Vindigni, 2009. "Exploring greedy criteria for the dynamic traveling purchaser problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 17(2), pages 141-158, June.
    13. Jorge Riera-Ledesma & Juan-José Salazar-González, 2006. "Solving the asymmetric traveling purchaser problem," Annals of Operations Research, Springer, vol. 144(1), pages 83-97, April.
    14. Zahra Sadat Hasanpour Jesri & Kourosh Eshghi & Majid Rafiee & Tom Van Woensel, 2022. "The Multi-Depot Traveling Purchaser Problem with Shared Resources," Sustainability, MDPI, vol. 14(16), pages 1-26, August.
    15. Gendreau, Michel & Manerba, Daniele & Mansini, Renata, 2016. "The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 248(1), pages 59-71.
    16. ARNOLD, Florian & SÖRENSEN, Kenneth, 2017. "A simple, deterministic, and efficient knowledge-driven heuristic for the vehicle routing problem," Working Papers 2017012, University of Antwerp, Faculty of Business and Economics.
    17. Gahm, Christian & Brabänder, Christian & Tuma, Axel, 2017. "Vehicle routing with private fleet, multiple common carriers offering volume discounts, and rental options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 192-216.
    18. Jamal Ouenniche & Prasanna K. Ramaswamy & Michel Gendreau, 2017. "A dual local search framework for combinatorial optimization problems with TSP application," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1377-1398, November.
    19. Gilbert Laporte & Jorge Riera-Ledesma & Juan-José Salazar-González, 2003. "A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem," Operations Research, INFORMS, vol. 51(6), pages 940-951, December.
    20. Yannis Marinakis & Athanasios Migdalas & Panos M. Pardalos, 2005. "A Hybrid Genetic—GRASP Algorithm Using Lagrangean Relaxation for the Traveling Salesman Problem," Journal of Combinatorial Optimization, Springer, vol. 10(4), pages 311-326, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:259:y:2017:i:1:p:1-18. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.