Linear programming and Artificial Intelligence for Vehicle scheduling problems

Abstract

This work utilises machine learning methods in the branch and price algorithm and applies it to the crew and vehicle scheduling problem. Using machine learning, statistical models are taught to select variables for branching. They are tested and their results are compared with a simple branching rule. Their performance approximately reached the level of this baseline. The implementation is designed to be easily extendable with new rules for branching variable selection, node selection and the primary problem heuristic.

Tato práce využívá metody strojového učení v rámci algoritmu branch and price a apli- kuje ho na problém optimalizace oběhů vozidel a řidičů. Pomocí metod strojového učení jsou statistické modely naučeny zvolit proměnné na větvení. Tyto modely jsou otestovány a jejich výsledky dosahují podobné úrovně, jako výsledky jednoduchého pravidla, se kte- rým byly srovnávány. Implementace je navržena tak, aby byla snadno doplnitelná novými pravidly pro výběr proměnných na větvení, výběr vrcholu na prozkoumání a heuristikou primární úlohy.