IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i5p795-d762518.html
   My bibliography  Save this article

Special Type Routing Problems in Plane Graphs

Author

Listed:
  • Tatiana Makarovskikh

    (Department of System Programming, South Ural State University, 454080 Chelyabinsk, Russia
    These authors contributed equally to this work.)

  • Anatoly Panyukov

    (Department of System Programming, South Ural State University, 454080 Chelyabinsk, Russia
    These authors contributed equally to this work.)

Abstract

We considered routing problems for plane graphs to solve control problems of cutting machines in the industry. According to the cutting plan, we form its homeomorphic image in the form of a plane graph G . We determine the appropriate type of route for the given graph: O E -route represents an ordered sequence of chains satisfying the requirement that the part of the route that is not passed does not intersect the interior of its passed part, A O E -chain represents O E -chain consecutive edges which are incident to vertex v and they are neighbours in the cyclic order O ± ( v ) , N O E -route represents the non-intersecting O E -route, P P O E -route represents the Pierce Point N O E -route with allowable pierce points that are start points of O E -chains forming this route. We analyse the solvability of the listed routing problems in graph G . We developed the polynomial algorithms for obtaining listed routes with the minimum number of covering paths and the minimum length of transitions between the ending of the current path and the beginning of the next path. The solutions proposed in the article can improve the quality of technological preparation of cutting processes in CAD/CAM systems.

Suggested Citation

  • Tatiana Makarovskikh & Anatoly Panyukov, 2022. "Special Type Routing Problems in Plane Graphs," Mathematics, MDPI, vol. 10(5), pages 1-22, March.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:5:p:795-:d:762518
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/5/795/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/5/795/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. T.A. Makarovskikh & A.V. Panyukov & E.A. Savitskiy, 2018. "Mathematical models and routing algorithms for economical cutting tool paths," International Journal of Production Research, Taylor & Francis Journals, vol. 56(3), pages 1171-1188, February.
    2. Reginald Dewil & Pieter Vansteenwegen & Dirk Cattrysse & Manuel Laguna & Thomas Vossen, 2015. "An improvement heuristic framework for the laser cutting tool path problem," International Journal of Production Research, Taylor & Francis Journals, vol. 53(6), pages 1761-1776, March.
    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. Khachai, Daniil & Sadykov, Ruslan & Battaia, Olga & Khachay, Michael, 2023. "Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm," European Journal of Operational Research, Elsevier, vol. 309(2), pages 488-505.

    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:gam:jmathe:v:10:y:2022:i:5:p:795-:d:762518. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.