IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v56y2009i5p478-486.html
   My bibliography  Save this article

A branch‐and‐cut algorithm for the nonpreemptive swapping problem

Author

Listed:
  • Charles Bordenave
  • Michel Gendreau
  • Gilbert Laporte

Abstract

In the Swapping Problem (SP), we are given a complete graph, a set of object types, and a vehicle of unit capacity. An initial state specifies the object type currently located at each vertex (at most one type per vertex). A final state describes where these object types must be repositioned. In general, there exist several identical objects for a given object type, yielding multiple possible destinations for each object. The SP consists of finding a shortest vehicle route starting and ending at an arbitrary vertex, in such a way that each object is repositioned in its final state. This article exhibits some structural properties of optimal solutions and proposes a branch‐and‐cut algorithm based on a 0‐1 formulation of the problem. Computational results on random instances containing up to 200 vertices and eight object types are reported. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009

Suggested Citation

  • Charles Bordenave & Michel Gendreau & Gilbert Laporte, 2009. "A branch‐and‐cut algorithm for the nonpreemptive swapping problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(5), pages 478-486, August.
    • Handle: RePEc:wly:navres:v:56:y:2009:i:5:p:478-486
    DOI: 10.1002/nav.20361
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20361
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20361?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. Michael O. Ball & Michael J. Magazine, 1988. "Sequencing of Insertions in Printed Circuit Board Assembly," Operations Research, INFORMS, vol. 36(2), pages 192-201, April.
    2. Shoshana Anily & Julien Bramel, 1999. "Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(6), pages 654-670, September.
    3. Hao, Jianxiu. & Orlin, James B., 1953-., 1992. "A faster algorithm for finding the minimum cut in a graph," Working papers 3372-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    Full references (including those not matched with items on IDEAS)

    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. Ji, P. & Sze, M. T. & Lee, W. B., 2001. "A genetic algorithm of determining cycle time for printed circuit board assembly lines," European Journal of Operational Research, Elsevier, vol. 128(1), pages 175-184, January.
    2. E Duman, 2007. "Modelling the operations of a component placement machine with rotational turret and stationary component magazine," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 317-325, March.
    3. Spieksma, F.C.R. & Crama, Y. & van de Klundert, J. & Flippo, O.E., 1995. "The component retrieval problem in printed circuit board assembly," Research Memorandum 027, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    4. Aggarwal, Charu C. (Charu Chandra) & Hao, Jianxiu. & Orlin, James B., 1953-, 1994. "Diagnosing infeasibilities in network flow problems," Working papers 3696-94., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    5. George J. Kyparisis & Christos Koulamas, 2002. "Assembly-Line Scheduling with Concurrent Operations and Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 68-80, February.
    6. Michael E. Fragkos & Vasileios Zeimpekis & Vasilis Koutras & Ioannis Minis, 2022. "Supply planning for shelters and emergency management crews," Operational Research, Springer, vol. 22(1), pages 741-777, March.
    7. L. Fleischer & É. Tardos, 1999. "Separating Maximally Violated Comb Inequalities in Planar Graphs," Mathematics of Operations Research, INFORMS, vol. 24(1), pages 130-148, February.
    8. T Knuutila & S Pyöttiälä & O S Nevalainen, 2007. "Minimizing the number of pickups on a multi-head placement machine," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(1), pages 115-121, January.
    9. Kazaz, Burak & Altinkemer, Kemal, 2003. "Optimization of multi-feeder (depot) printed circuit board manufacturing with error guarantees," European Journal of Operational Research, Elsevier, vol. 150(2), pages 370-394, October.
    10. Anantaram Balakrishnan & François Vanderbeck, 1999. "A Tactical Planning Model for Mixed-Model Electronics Assembly Operations," Operations Research, INFORMS, vol. 47(3), pages 395-409, June.
    11. Spieksma, F.C.R. & Crama, Y. & van de Klundert, J. & Flippo, O.E., 1995. "The assembly of printed circuit boards: a case with multiple machines and multiple board types," Research Memorandum 023, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    12. Hipólito Hernández-Pérez & Juan-José Salazar-González, 2004. "Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem," Transportation Science, INFORMS, vol. 38(2), pages 245-255, May.
    13. Boland, N. L. & Clarke, L. W. & Nemhauser, G. L., 2000. "The asymmetric traveling salesman problem with replenishment arcs," European Journal of Operational Research, Elsevier, vol. 123(2), pages 408-427, June.
    14. Altinkemer, Kemal & Kazaz, Burak & Koksalan, Murat & Moskowitz, Herbert, 2000. "Optimization of printed circuit board manufacturing: Integrated modeling and algorithms," European Journal of Operational Research, Elsevier, vol. 124(2), pages 409-421, July.
    15. 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.
    16. Egon Balas & Matteo Fischetti, 1999. "Lifted Cycle Inequalities for the Asymmetric Traveling Salesman Problem," Mathematics of Operations Research, INFORMS, vol. 24(2), pages 273-292, May.
    17. Fu, Hsin-Pin & Su, Chao-Ton, 2000. "A comparison of search techniques for minimizing assembly time in printed wiring assembly," International Journal of Production Economics, Elsevier, vol. 63(1), pages 83-98, January.
    18. Torabi, S.A. & Hamedi, M. & Ashayeri, J., 2010. "A Multi-Objective Optimization Approach for Multi-Head Beam-Type Placement Machines," Other publications TiSEM 8ea272ae-66f1-4999-aec7-8, Tilburg University, School of Economics and Management.
    19. Sun, Dong-Seok & Lee, Tae-Eog & Kim, Kyung-Hoon, 2005. "Component allocation and feeder arrangement for a dual-gantry multi-head surface mounting placement tool," International Journal of Production Economics, Elsevier, vol. 95(2), pages 245-264, February.
    20. Ayob, Masri & Kendall, Graham, 2008. "A survey of surface mount device placement machine optimisation: Machine classification," European Journal of Operational Research, Elsevier, vol. 186(3), pages 893-914, May.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:56:y:2009:i:5:p:478-486. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.