Optimalizace obsazení turnusů řidičů autobusové dopravy

Abstract

Cílem diplomové práce je vytvořit algoritmus pro určování optimálního plánu přidělení řidičů a vozidel na předem dané schéma jízd. Naším cílem při tvorbě plánu je minimalizace přímých nákladů spojených s přepravou. Zároveň se snažíme vytvořit vyvážený plán, s ohledem na vytížení řidičů a vozidel. Struktura problému plánování byla matematicky popsána sestavením rozsáhlého lineárního modelu, jehož součástí jsou algebraické formulace jednotlivých omezení, která je nutné v automobilové dopravě dodržovat. V tomto modelu figurují binární a reálné proměnné, jedná se tedy o model smíšeného celočíselného programování. O řešení celočíselných úloh se dá říci, že je obecně mnohem komplikovanější než řešení úloh bez celočíselných omezení. K praktickému řešení úlohy byl použit optimalizační software GAMS, který pro řešení celočíselných úloh používá algoritmus větvení a mezí. V GAMSu byl, na základě výše zmíněného modelu, sestaven programový kód, který je schopen pro sérii vstupních dat určit optimální plán obsazení jízd. Součástí práce je i několik vyřešených vzorových úloh.

The thesis is focused on suggesting an algorithm for planning of optimal assignment drivers and vehicles to scheme of expeditions. When we make the assignment, we aspire to minimize the total transportation costs. By the same mail we push for well-balanced assignment, with respect to utilization of drivers and vehicles . The structure of the planning problem there is describing by making out of a wide linear model, whose parts are algebraic formulations of restrictions, which one must in traffic abide. In this model we can see binary and real variables that mean we draw up a model of mixed integer programming. We can say, that the integer programming is in general more complicated, then integer programming. We used optimization software named GAMS for solution this problem. The software uses Branch and Bound algorithm for the integer number problems. We draw up a program in GAMS, which is able to set an optimal pian for assignment drivers and vehicles to expeditions. A part of this work is couple of exemplary tasks, with their solution.