IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v54y2006i2p366-378.html
   My bibliography  Save this article

The Black and White Traveling Salesman Problem

Author

Listed:
  • Gianpaolo Ghiani

    (Centre de recherche sur les transports, Université de Montréal, C.P. 6128, Succursale Centre-ville, Montréal, Quebec, Canada H3C 3J7 and Dipartimento di Ingegneria dell’Innovazione, Università di Lecce, Via per Arnesano, 73100 Lecce, Italy)

  • Gilbert Laporte

    (Centre de recherche sur les transports, Université de Montréal, C.P. 6128, Succursale Centre-ville, Montréal, Quebec, Canada H3C 3J7 and HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Quebec, Canada H3T 2A7)

  • Frédéric Semet

    (LAMIH, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont-Houy, 59311 Valenciennes Cedex 9, France)

Abstract

The black and white traveling salesman problem (BWTSP) is defined on a graph G whose vertex set is partitioned into black and white vertices. The aim is to design a shortest Hamiltonian tour on G subject to cardinality and length constraints: both the number of white vertices as well as the length of the tour between two consecutive black vertices are bounded above. The BWTSP has applications in airline scheduling and in telecommunications. This paper proposes an integer linear formulation for the undirected BWTSP, as well as several classes of valid inequalities. An exact branch-and-cut algorithm is then developed. Extensive tests show that it can solve exactly instances involving up to 100 vertices. The algorithm can also be applied directly to solve unit demand vehicle routing problems of similar sizes.

Suggested Citation

  • Gianpaolo Ghiani & Gilbert Laporte & Frédéric Semet, 2006. "The Black and White Traveling Salesman Problem," Operations Research, INFORMS, vol. 54(2), pages 366-378, April.
    • Handle: RePEc:inm:oropre:v:54:y:2006:i:2:p:366-378
    DOI: 10.1287/opre.1050.0218
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1050.0218
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1050.0218?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
    ---><---

    References listed on IDEAS

    as
    1. Ram Gopalan & Kalyan T. Talluri, 1998. "The Aircraft Maintenance Routing Problem," Operations Research, INFORMS, vol. 46(2), pages 260-271, April.
    2. Kalyan T. Talluri, 1998. "The Four-Day Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 32(1), pages 43-53, February.
    3. Volgenant, Ton & Jonker, Roy, 1982. "A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation," European Journal of Operational Research, Elsevier, vol. 9(1), pages 83-89, January.
    4. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    5. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    6. Matteo Fischetti & Paolo Toth, 1997. "A Polyhedral Approach to the Asymmetric Traveling Salesman Problem," Management Science, INFORMS, vol. 43(11), pages 1520-1536, November.
    7. Gilbert Laporte & Yves Nobert & Martin Desrochers, 1985. "Optimal Routing under Capacity and Distance Restrictions," Operations Research, INFORMS, vol. 33(5), pages 1050-1073, October.
    8. Matteo Fischetti & Juan José Salazar González & Paolo Toth, 1997. "A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem," Operations Research, INFORMS, vol. 45(3), pages 378-394, June.
    9. Augerat, P. & Belenguer, J. M. & Benavent, E. & Corberan, A. & Naddef, D., 1998. "Separating capacity constraints in the CVRP using tabu search," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 546-557, April.
    10. Steven Cosares & David N. Deutsch & Iraj Saniee & Ondria J. Wasem, 1995. "SONET Toolkit: A Decision Support System for Designing Robust and Cost-Effective Fiber-Optic Networks," Interfaces, INFORMS, vol. 25(1), pages 20-40, February.
    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.
    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. Li, Xiangyong & Lin, Shaochong & Tian, Peng & Aneja, Y.P., 2017. "Models and column generation approach for the resource-constrained minimum cost path problem with relays," Omega, Elsevier, vol. 66(PA), pages 79-90.
    2. Gerardo Berbeglia & Gilles Pesant & Louis-Martin Rousseau, 2012. "Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis," Transportation Science, INFORMS, vol. 46(3), pages 359-373, August.
    3. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    4. Khalid Mekamcha & Mehdi Souier & Hakim Nadhir Bessenouci & Mohammed Bennekrouf, 2021. "Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case," Operational Research, Springer, vol. 21(3), pages 1641-1661, September.
    5. Gouveia, Luis & Leitner, Markus & Ruthmair, Mario, 2017. "Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 908-928.

    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. Muren, & Wu, Jianjun & Zhou, Li & Du, Zhiping & Lv, Ying, 2019. "Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 87-102.
    2. 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.
    3. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    4. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    5. 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.
    6. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    7. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    8. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.
    9. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    10. Gary R. Waissi & Pragya Kaushal, 2020. "A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 73-87, March.
    11. Mehdi El Krari & Belaïd Ahiod & Youssef Bouazza El Benani, 2021. "A pre-processing reduction method for the generalized travelling salesman problem," Operational Research, Springer, vol. 21(4), pages 2543-2591, December.
    12. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    13. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    14. William Cook & Daniel G. Espinoza & Marcos Goycoolea, 2007. "Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 356-365, August.
    15. David Applegate & William Cook & Sanjeeb Dash & André Rohe, 2002. "Solution of a Min-Max Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 132-143, May.
    16. Éric Duchenne & Gilbert Laporte & Frédéric Semet, 2007. "The Undirected m -Peripatetic Salesman Problem: Polyhedral Results and New Algorithms," Operations Research, INFORMS, vol. 55(5), pages 949-965, October.
    17. Bruce Golden & S. Raghavan & Daliborka Stanojević, 2005. "Heuristic Search for the Generalized Minimum Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 17(3), pages 290-304, August.
    18. Jeanette Schmidt & Stefan Irnich, 2020. "New Neighborhoods and an Iterated Local Search Algorithm for the Generalized Traveling Salesman Problem," Working Papers 2020, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    19. Anirudh Subramanyam & Chrysanthos E. Gounaris, 2018. "A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling," Transportation Science, INFORMS, vol. 52(2), pages 386-401, March.
    20. Gorka Kobeaga & María Merino & Jose A. Lozano, 2021. "On solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithms," Annals of Operations Research, Springer, vol. 305(1), pages 107-136, October.

    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:inm:oropre:v:54:y:2006:i:2:p:366-378. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.