Communications - Scientific Letters of the University of Zilina 2003, 5(4):16-20 | DOI: 10.26552/com.C.2003.4.16-20

Bus Scheduling as a Graph Coloring Problem

Stanislav Paluch1
1 Faculty of Management Science and Informatics, University of Zilina, Slovakia

The fundamental vehicle-scheduling problem (VSP) is usually formulated as a matching problem for which there exists a polynomial algorithm. The formulation of VSP as a graph coloring problem may seem not to be practical since a graph coloring problem is NP-hard and it is not a good idea to solve a polynomial problem using a non polynomial algorithm. However, no polynomial algorithms have been found for generalizations of VSP and hence the graph coloring formulation offers good approximation algorithms for their solution.

Keywords: no keywords

Published: December 31, 2003  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Paluch, S. (2003). Bus Scheduling as a Graph Coloring Problem. Communications - Scientific Letters of the University of Zilina, 5(4), 16-20. doi: 10.26552/com.C.2003.4.16-20
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. ČERNÁ, A.: Heterogenous Bus Fleet Exploitation in Regional Bus Transport, Slovak, (Využitie heterogenneho autobusového parku v mestskej a regionálnej doprave), Proceedings of the 5-th International Conference on Public Transport, Dom techniky, Bratislava, 21. - 22. 11. 2001, pp. 93-96.
    2. ČERNÁ, A.: Optimization of Regional Bus Transport, Czech, (Optimalizace regionální autobusové dopravy.) Proceedings of International Conference "Transportation Science"., (Věda o dopravě), Fakulta Dopravní ČVUT Praha, 6. - 7. 11. 2001, pp. 70-75.
    3. ČERNÝ, J.: Fleet Management. Selected Optimization Problems. Proceedings of the 8-th IFAC/IFIP/IFORS Symposium Transportation Systems Chania, Greece, june 1997, pp. 607-610. Go to original source...
    4. DEMEL, J.: Graphs and their applications, (Grafy a jejich aplikace), Czech, Academia Praha, 2002, ISBN 80-200-0990-6.
    5. JANOŠÍKOVÁ, L., STASINKA, R.: Constraint Programming: An Application for Graph Coloring. In: Journal of Information, Control and Management Systems, No. 2/2003. University of Žilina, Žilina. ISSN 1336-1716. (to appear)
    6. PALÚCH, S.: A Graph Theory Approach to Bus Scheduling with Two Types of Buses. Studies of the Faculty of Management Science and Informatics, Vol. 9, December 2001, pp. 53-57.
    7. PEŠKO, Š.: Multicommodity Return Bus Scheduling Problem. Proceedings, International scientific conference on mathematics, pp. 77-82, Žilina, ISBN 80-7100-578-9, (1998)

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits 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