Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Using „sweep algorithm“ for decomposing a set of vertices and subsequent solution of the traveling salesman problem in decomposed subsets

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27350%2F17%3A10237931" target="_blank" >RIV/61989100:27350/17:10237931 - isvavai.cz</a>

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Using „sweep algorithm“ for decomposing a set of vertices and subsequent solution of the traveling salesman problem in decomposed subsets

  • Popis výsledku v původním jazyce

    The aim of the traveling salesman problem is to find an optimal route, which passes through all vertices of the given graph just once (except for the initial vertex) and that is the one with a minimum length. Basic requirement for solution is that capacity of service vehicle holds all requirements, which are placed at vertices of graph (it could be a collection or distribution). However, it is a common practice that capacity of service vehicle is less than all requirements, which must be satisfied. One of basic ways for troubleshooting is a decomposition of the input set of vertices into several subsets so that the sum of capacity requirements in individual subsets does not exceed the capacity of service vehicle. In these subsets, the optimal route can be found by some of the accessible ways: an exact solution in case of small-scale tasks, heuristics in case of large-scale tasks. The core of the present paper deals with the use of the concept of „sweep algorithm“ for decomposing input set of vertices and subsequent determining optimal vehicle routes using an exact algorithm. Computational experiments that will be presented in this paper, were realized in conditions of the optimal route planning for service vehicles, which ensure the municipal waste collection of the specific commercial company.

  • Název v anglickém jazyce

    Using „sweep algorithm“ for decomposing a set of vertices and subsequent solution of the traveling salesman problem in decomposed subsets

  • Popis výsledku anglicky

    The aim of the traveling salesman problem is to find an optimal route, which passes through all vertices of the given graph just once (except for the initial vertex) and that is the one with a minimum length. Basic requirement for solution is that capacity of service vehicle holds all requirements, which are placed at vertices of graph (it could be a collection or distribution). However, it is a common practice that capacity of service vehicle is less than all requirements, which must be satisfied. One of basic ways for troubleshooting is a decomposition of the input set of vertices into several subsets so that the sum of capacity requirements in individual subsets does not exceed the capacity of service vehicle. In these subsets, the optimal route can be found by some of the accessible ways: an exact solution in case of small-scale tasks, heuristics in case of large-scale tasks. The core of the present paper deals with the use of the concept of „sweep algorithm“ for decomposing input set of vertices and subsequent determining optimal vehicle routes using an exact algorithm. Computational experiments that will be presented in this paper, were realized in conditions of the optimal route planning for service vehicles, which ensure the municipal waste collection of the specific commercial company.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

  • OECD FORD obor

    20104 - Transport engineering

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/TH02010930" target="_blank" >TH02010930: Efektivní přístupy k úsporným a adaptabilním systémům údržby a obsluhy dopravních sítí</a><br>

  • Návaznosti

    V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Ostatní

  • Rok uplatnění

    2017

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    Mathematical Methods in Economics: MME 2017 : 35th international conference : book of abstracts : Hradec Králové, Czech Republic, September 13th-15th, 2017

  • ISBN

    978-80-7435-677-3

  • ISSN

  • e-ISSN

    neuvedeno

  • Počet stran výsledku

    6

  • Strana od-do

    584-589

  • Název nakladatele

    Gaudeamus

  • Místo vydání

    Hradec Králové

  • Místo konání akce

    Hradec Králové

  • Datum konání akce

    13. 9. 2017

  • Typ akce podle státní příslušnosti

    EUR - Evropská akce

  • Kód UT WoS článku