Acta Univ. Agric. Silvic. Mendelianae Brun. 2016, 64(3), 847-854 | DOI: 10.11118/actaun201664030847

Optimization of the Municipal Waste Collection Route Based on the Method of the Minimum Pairing

Michal Petřík, Stanislav Bartoň
Department of Technology and Automobile Transport, Faculty of AgriSciences, Mendel University in Brno, Zemědělská 1, 613 00 Brno, Czech Republic

In the present article is shown the use of Maple program for processing of data describing the position of municipal waste sources and topology of collecting area. The data are further processed through the use of graph theory algorithms, which enable creation of collection round proposal.
In this case study is described method of waste pick-up solution in a certain village of approx. 1,600 inhabitants and built-up area of approx. 30 hectares. Village has approx. 11.5 kilometers of ride able routes, with approx. 1 kilometer without waste source. The first part shows topology of the village in light of location of waste sources and capacity of the routes. In the second part are topological data converted into data that can be processed by use of the Graph Theory and the correspondent graph is shown. Optimizing collection route in a certain graph means to find the Euler circle. However, this circle can be constructed only on condition that all the vertices of the graph are of an even degree. Practically this means that is necessary to introduce auxiliary edges - paths that will be passed twice. These paths will connect vertices with odd values. The optimal solution then requires that the total length of the inserted edges was minimal possible, which corresponds to the minimum pairing method. As it is a problem of exponential complexity, it is necessary to make some simplifications. These simplifications are depicted graphically and the results are displayed in the conclusion.
The resulting graph with embedded auxiliary edges can be used as a basic decision making material for creation of real collection round that respects local limitations such as one way streets or streets where is the waste collection is not possible from both sides at the same time.

Keywords: Graph theory, Eulerian circle, vertex, degree, weight matrix, computational complexity, minimal perfect matching, maple
Grants and funding:

The research has been supported by the project TP 4/2014 "Analysis of degradation processes of modern materials used in agricultural technology" financed by IGA AF MENDELU.

Prepublished online: July 4, 2016; Published: July 1, 2016  Show citation

ACS AIP APA ASA Harvard Chicago IEEE ISO690 MLA NLM Turabian Vancouver
Petřík, M., & Bartoň, S. (2016). Optimization of the Municipal Waste Collection Route Based on the Method of the Minimum Pairing. Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis, 64(3), 847-854. doi: 10.11118/actaun201664030847
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. ARCGIS. 2016. ArcGIS 10.4 for Desktop Basic. [Online]. Available at: http://store.esri.com/esri/showdetl.cfm?SID=2&Product_ID=29&. [Accessed: 2016, March 23].
    2. BERGE, C. 2001. The Theory of graphs. Courier Dover Publications.
    3. COOK, W. J. 2012. In Pursuit of the Traveling Salesman. Mathematics at the Limits. Princeton University Press.
    4. ČÚZK. 2016. Main maps of the Czech Rep. [in Czech: Zákládní mapy ČR]. [Online]. Available at: http://geoportal.cuzk.cz/geoprohlizec/default.aspx?. [Accessed: 2016, Januar 5].
    5. DARLING, D. J. 2004. The Universal Book of Mathematics. John Wiley.
    6. DEMEL, J. 2002. Graphs and their applications [in Czech: Grafy a jejich aplikace]. Academia.
    7. DIESTEL, R. 2010. Graph Theory. Springer. Go to original source...
    8. HAROLD, P., MUSSER, G., TRYMPE, L. et al. 2007. A Mathematical View of Our World. Thompson Books.
    9. LINDO. 2016. LindoTM. [Online]. Available at: http://www.lindo.com/. [Accessed: 2016, March 21].
    10. LINDODAR. 2016. Dial a Ride. [Online]. Available at: http://www.lindo.com/cgi-bin/modelf.cgi?Dial_a_Ride.txt;LINGO. [Accessed: 2016, March 21].
    11. LINDOFLEET. 2016. Fleet Roouting. [Online]. Available at: http://www.lindo.com/cgi-bin/modelf.cgi?FLEET.txt;LINDO. [Accessed: 2016, March 22].
    12. LINDOROUTE. 2016. The VROUTE.lng Model. [Online]. Available at: http://www.lindo.com/lsmodels/Controller/doSelect.php?action=2&name=VROUTE.lng. [Accessed: 2016, March 22].
    13. LINDOWIDGETS. 2016. The WIDGETS.lng Model. [Online]. Available at: http://www.lindo.com/lsmodels/Controller/doSelect.php?action=2&name=WIDGETS.lng. [Accessed: 2016, March 22].
    14. MAPLE. 2011. Maple User Manual. Maplesoft. Waterloo Canada.
    15. MATOUŠEK, J., NEŠETŘIL, J. 2002. Discrete mathematics chapters [in Czech: Kapitoly z diskrétní matematiky]. Karolinum. Go to original source...
    16. OPTIMAP. 2015. Fastest Roundtrip Solver. [Online]. Available at: http://gebweb.net/optimap/. [Accessed: 2015, December 12].

    This is an open access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY NC ND 4.0), which permits non-comercial use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content