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

The bi-objective traveling purchaser problem with deliveries

Author

Listed:
  • Palomo-Martínez, Pamela J.
  • Salazar-Aguilar, M. Angélica

Abstract

In this work we introduce a variant of the well-known Traveling Purchaser Problem in which the purchased products must be delivered to a set of customers. The objective is to minimize the total cost (purchasing plus traveling costs) and the waiting time of the customers, simultaneously, while satisfying the total demand. This problem is called the bi-objective Traveling Purchaser Problem with Deliveries. In order to approximate Pareto fronts for this problem, a relinked variable neighborhood search is proposed and tested over a large set of artificial instances. Our results show that our algorithm is highly competitive compared to the ϵ-constraint method in small instances. On the other hand, experiments carried out over large instances show that our algorithm is able to find Pareto front approximations with more points in a shorter running time for uncapacitated instances than for capacitated ones. Also, computational results show that the performance of some local searches used in our algorithm depends on the characteristics of the instances, this underlines the importance of designing a metaheuristic based on multiple local searches.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:273:y:2019:i:2:p:608-622
    DOI: 10.1016/j.ejor.2018.08.039
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718307343
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.08.039?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. 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.
    2. Julian Molina & Manuel Laguna & Rafael Martí & Rafael Caballero, 2007. "SSPMO: A Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 91-100, February.
    3. 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.
    4. 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.
    5. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    6. 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.
    7. 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.
    8. Golden, Bruce & Levy, Larry & Dahl, Roy, 1981. "Two generalizations of the traveling salesman problem," Omega, Elsevier, vol. 9(4), pages 439-441.
    9. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    10. G. A. Croes, 1958. "A Method for Solving Traveling-Salesman Problems," Operations Research, INFORMS, vol. 6(6), pages 791-812, December.
    11. 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.
    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. 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.
    14. 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.
    15. 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.
    16. E. Angelelli & R. Mansini & M. Vindigni, 2016. "The Stochastic and Dynamic Traveling Purchaser Problem," Transportation Science, INFORMS, vol. 50(2), pages 642-658, May.
    17. 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.
    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. 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.

    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. 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.
    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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Margaretha Gansterer & Murat Küçüktepe & Richard F. Hartl, 2017. "The multi-vehicle profitable pickup and delivery problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 303-319, January.
    11. Kalayci, Can B. & Kulak, Osman & Günther, Hans-Otto, 2015. "A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time LimitAuthor-Name: Polat, Olcay," European Journal of Operational Research, Elsevier, vol. 242(2), pages 369-382.
    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. 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.
    14. 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.
    15. 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.
    16. Gansterer, Margaretha & Hartl, Richard F. & Sörensen, Kenneth, 2020. "Pushing frontiers in auction-based transport collaborations," Omega, Elsevier, vol. 94(C).
    17. Hennig, F. & Nygreen, B. & Christiansen, M. & Fagerholt, K. & Furman, K.C. & Song, J. & Kocis, G.R. & Warrick, P.H., 2012. "Maritime crude oil transportation – A split pickup and split delivery problem," European Journal of Operational Research, Elsevier, vol. 218(3), pages 764-774.
    18. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    19. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    20. Connor Little & Salimur Choudhury & Ting Hu & Kai Salomaa, 2022. "Comparison of Genetic Operators for the Multiobjective Pickup and Delivery Problem," Mathematics, MDPI, vol. 10(22), pages 1-21, November.

    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:273:y:2019:i:2:p:608-622. 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.