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

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

—

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20104 - Transport engineering

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

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ů

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

—