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

Result code in IS VaVaI

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

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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 &quot;sweep algorithm&quot; 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

20104 - Transport engineering

Project

<a href="/en/project/TH02010930" target="_blank" >TH02010930: Effective approaches to economical and adaptable systems of maintenance and operation of transport networks</a><br>

Continuities

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Publication year

2017

Confidentiality

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

Article name in the collection

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

ISBN

978-80-7435-678-0

ISSN

—

e-ISSN

neuvedeno

Number of pages

6

Pages from-to

584-589

Publisher name

Gaudeamus

Place of publication

Hradec Králové

Event location

Hradec Králové

Event date

Sep 13, 2017

Type of event by nationality

EUR - Evropská akce

UT code for WoS article

000427151400100