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

Multiobjective traveling salesperson problem on Halin graphs

Author

Listed:
  • Özpeynirci, Özgür
  • Köksalan, Murat

Abstract

In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.

Suggested Citation

  • Özpeynirci, Özgür & Köksalan, Murat, 2009. "Multiobjective traveling salesperson problem on Halin graphs," European Journal of Operational Research, Elsevier, vol. 196(1), pages 155-161, July.
    • Handle: RePEc:eee:ejores:v:196:y:2009:i:1:p:155-161
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00367-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. COULLARD, Collette R. & RAIS, Abdur & RARDIN, Ronald L. & WAGNER, Donald K., 1993. "Linear-Time Algorithms for the 2-Connected Steiner Subgraph Problem on Special Classes of Graphs," LIDAM Reprints CORE 1037, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
    3. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    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. Florios, Kostas & Mavrotas, George, 2014. "Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems," MPRA Paper 105074, University Library of Munich, Germany.
    2. Diclehan Tezcaner Öztürk & Murat Köksalan, 2016. "An interactive approach for biobjective integer programs under quasiconvex preference functions," Annals of Operations Research, Springer, vol. 244(2), pages 677-696, September.
    3. Diclehan Tezcaner & Murat Köksalan, 2011. "An Interactive Algorithm for Multi-objective Route Planning," Journal of Optimization Theory and Applications, Springer, vol. 150(2), pages 379-394, August.
    4. Çela, Eranda & Deineko, Vladimir & Woeginger, Gerhard J., 2012. "The x-and-y-axes travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 333-345.

    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. S. Dutta & S. Acharya & Rajashree Mishra, 2016. "Genetic algorithm based fuzzy stochastic transportation programming problem with continuous random variables," OPSEARCH, Springer;Operational Research Society of India, vol. 53(4), pages 835-872, December.
    2. Zhong, Tao & Young, Rhonda, 2010. "Multiple Choice Knapsack Problem: Example of planning choice in transportation," Evaluation and Program Planning, Elsevier, vol. 33(2), pages 128-137, May.
    3. Cai, Yutong & Ong, Ghim Ping & Meng, Qiang, 2022. "Dynamic bicycle relocation problem with broken bicycles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    4. Yang, X. Q. & Goh, C. J., 1997. "A method for convex curve approximation," European Journal of Operational Research, Elsevier, vol. 97(1), pages 205-212, February.
    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. Aritra Pal & Hadi Charkhgard, 2019. "A Feasibility Pump and Local Search Based Heuristic for Bi-Objective Pure Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 115-133, February.
    7. KIKOMBA KAHUNGU, Michaël & MABELA MAKENGO MATENDO, Rostin & M. NGOIE, Ruffin-Benoît & MAKENGO MBAMBALU, Fréderic & OKITONYUMBE Y.F, Joseph, 2013. "Les fondements mathématiques pour une aide à la décision du réseau de transport aérien : cas de la République Démocratique du Congo [Mathematical Foundation for Air Traffic Network Decision Aid : C," MPRA Paper 68533, University Library of Munich, Germany, revised Mar 2013.
    8. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    9. Singh, Preetvanti & Saxena, P. K., 2003. "The multiple objective time transportation problem with additional restrictions," European Journal of Operational Research, Elsevier, vol. 146(3), pages 460-476, May.
    10. Pankaj Gupta & Mukesh Mehlawat, 2007. "An algorithm for a fuzzy transportation problem to select a new type of coal for a steel manufacturing unit," 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 114-137, July.
    11. Li, Yuan & Chen, Haoxun & Prins, Christian, 2016. "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests," European Journal of Operational Research, Elsevier, vol. 252(1), pages 27-38.
    12. Przybylski, Anthony & Gandibleux, Xavier & Ehrgott, Matthias, 2008. "Two phase algorithms for the bi-objective assignment problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 509-533, March.
    13. Nicolas Jozefowiez & Gilbert Laporte & Frédéric Semet, 2012. "A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 554-564, November.
    14. Tolga Bektaş & Güneş Erdoğan & Stefan Røpke, 2011. "Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 299-316, August.
    15. Diclehan Tezcaner & Murat Köksalan, 2011. "An Interactive Algorithm for Multi-objective Route Planning," Journal of Optimization Theory and Applications, Springer, vol. 150(2), pages 379-394, August.
    16. Derbel, Bilel & Humeau, Jérémie & Liefooghe, Arnaud & Verel, Sébastien, 2014. "Distributed localized bi-objective search," European Journal of Operational Research, Elsevier, vol. 239(3), pages 731-743.
    17. Fatih Rahim & Canan Sepil, 2014. "A location-routing problem in glass recycling," Annals of Operations Research, Springer, vol. 223(1), pages 329-353, December.
    18. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    19. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 597-618, November.
    20. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.

    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:196:y:2009:i:1:p:155-161. 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.