Development of an integrated model for congestion prediction and determination of optimal number of active channels in module

[А. Петровић]

160 листова

Организационе науке / ORGANIZATIONAL SCIENCES

Последњих година велики број истраживања је усмерен ка предикцији саобраћајних гужви. Различите статистичке методе нису показале значајан допринос у предиктивним перформансама предикције гужви. Стога се данас све чешће користе алгоритми машинског учења у циљу постизања задовољавајућих резултата предикције. У овој дисертацији, представљена је метолодогија за класификацију гужви на бази новоразвијеног модела Гаусових условних случајних поља за стрктурну бинарну предикцију (GCRFBC). Иста је успешно имплементирана на реалне проблеме предвиђања гужви. Методлогија може бити успешно примењена на класификационе проблеме описане неусмереним графовима који се не могу ефективно решити стандардним условним случајним пољима (CRF). Новоразвијени модел, коришћен у методологији, је заснован на стандардним Гаусовим условним случајним пољима за регресију (GCRF) која су проширена латентним променљивим што даје бројне предности истом. Захваљујући латентној структури, учење и закључивање у моделу не захтева компликоване нумеричке процедуре, већ може бити решено аналитички. Поред тога, постојање латентне структуре омогућава да модел буде отворен ка даљим побољшањима. Три различита алгоритма су развијена: GCRFBCb (GCRFBC – Бајесовски), GCRFBCb-fast (GCRFBC – Бајесовски са апроксимацијом) и GCRFBCnb (GCRFBC – не-Бајесовски). Проширена метода локалне варијационе апроксимације сигмоидне функције коришћена је за решавање интеграла по латентним променљивим у Бајесовској верзији GCRFBC модела. У случају не-Бајесовског GCRFBC модела у учењу и закључивању је коришћена латентна променљива са максималном вредношћу функције густине вероватноће. Закључивање у GCRFBCb моделу је решено коришћењем Њутн-Котесовим формулама за једнодимензионалну интеграцију. Услед великог броја варијационих параметара, рачунски трошак учења је велики, стога је развијена брза верзија Бајесовског GCRFBC модела. Перформансе модела су евалуиране на синтетичким и реалним подацима. Показано је да се применом методлогије остварују боље перформансе предвиђања гужви у поређењу са неструктурним моделима. Додатно су евалуирани рачунски и меморијски трошкови. Методологија је генерализована на примере из других домена. Детаљне предности и мане свих развијених модела су наглашене. У другом делу дисертације развијенa је хибридна методлогија за предвиђање индикатора саобаћаја који се заснива на комбинацији Гаусових условних случајних поља за регресију и класификацију. Услед коришћења структурних модела, методологија се користи за предвиђање индикатора саобраћаја на више излаза који су међусобно зависни. Поред тога, обезбеђује се учење из ретких података, односно података где многи излази немају никакаву вредност (ништа). Класификациони модел служи за елиминисање излаза са вредностима ништа, док регресиони модел служи за предвиђање индикатора саобраћаја на оним излазима који немају вредност ништа. Информације о индикаторима саобраћаја омогућавају ефикасан мониторинг саобраћаја, управљање, планирање као и доношење информација које учеснике у саобраћају могу да наведу на путање где гужве могу да се заобиђу. Предности и мане новоразвијене методлогије приказане су на два примера. Први се тиче предвиђања гужви на ауто-путу E70-E75 који пролази кроз Србију, док је други проблем везан за предвиђање гужви на ски-центру Копаоник. У последњем делу дисертације развијена је методологија за3 одређивања оптималног броја активних канала у будућности. Методологија је заснована на комбинацији рекурентних неуронских мрежа, теорије редова чекања и метахеуристика у циљу одређивања оптималног броја активних канала у будућности. Методологија се базира на предвиђању интензитета долазака и одређивању интензитета опслуживања у неком периоду у будућности. Коришћењем тих интензитета у моделима теорије редова чекања, поставља се функција циља која се оптимизује посредством избора броја активних канала у модулу. Приказана су два алгоритма: први заснован на не-Бајесовском приступу одређивања броја активних канала у модулу и други заснован на Бајесовском приступу. На примеру одређивања оптималног броја наплатних рампи који треба да буде отворен у будућности на наплатној станици Врчин верификована је примена исте. Може се видети да у свим анализираним случајевима, резултати добијени новоразвијеном методологијом показују неупоредиво ниже очекиване укупне трошкове у поређењу са тренутном стратегијом отварања наплатних рампи.

In the recent years, research committed in the field of congestion prediction present one of the most popular area of interest. A variety of novel methods for congestion prediction based on unstructured statistical (machine) learning have become the standard for congestion prediction. However, in this dissertaion I argue that structured machine (statistical) learning algorithms can significantly improve congestion prediction performances. In this dissertation, a Gaussian conditional random field model for structured binary classification (GCRFBC) is proposed for solving problems of congestion prediction. The model is applicable to classification problems with undirected graphs, intractable for standard classification CRFs. The model representation of GCRFBC is extended by latent variables which yield some appealing properties. Thanks to the GCRF latent structure, the model becomes tractable, efficient and open to improvements previously applied to GCRF regression models. In addition, the model allows for reduction of noise, that might appear if structures were defined directly between discrete outputs. Three different forms of the algorithm are presented: GCRFBCb (GCRGBC - Bayesian), GCRFBCbfast (GCRGBC - Bayesian approximation) and GCRFBCnb (GCRFBC - non-Bayesian). The extended method of local variational approximation of sigmoid function is used for solving empirical Bayes in Bayesian GCRFBCb variant, whereas MAP value of latent variables is the basis for learning and inference in the GCRFBCnb variant. The inference in GCRFBCb is solved by Newton-Cotes formulas for one-dimensional integration. Due to large numbers of variational parameters the computational costs of learning is significant, so fast version of GCRFBCb model is derived (GCRFBCb-fast). Models are evaluated on synthetic data and real data. It was shown that models achieve better congestion prediction performance than unstructured predictors. Furthermore, computational and memory complexity is evaluated. The generalization of the proposed models on other problems are discussed in details. Moreover, in the second part of this dissertation a hybrid model of two Gaussian Conditional Random Fields models (one recently proposed for classification, and one for regression) for inference of traffic speed, a relevant variable for traffic state estimation and travel information systems is proposed. It addresses two specifics of the problem - sparsity in traffic data and the fact that observations are not independent. It does so by combining a Gaussian conditional random field binary classification (GCRFBC) model (for gating of free-flow regimes and potentially congested traffic regimes) and a regression Gaussian conditional random field (GCRF) model with varying structure of nodes for prediction of traffic speed in dependent variables of potentially congested traffic regimes only. The information provided by the model can help in traffic monitoring, control, and planning, as well in congestion mitigation by providing information for avoiding congested routes. The proposed model is tested on two large-scale networks in Serbia, an arterial E70-E75 335km long highway stretch as well as in the ski resort Kopaonik with 55 km of ski slopes. The advantages and disadvantages of hybrid model is shown. In the last section of dissertation methodology for determination of optimal number of active channels in module is developed. Methodology is based on combination of recurrent neural networks, queuing theory and metaheuristics. Recurrent neural networks are used for prediction of arrival intensity and estimation of service intensity in some period in future. The predicted intensities are used in queuing theory models in order to develop objective function5 that has to be minimized. Two different algorithms are presented: the first one is based on nonBayesian and the second one is based on Bayesian approach. The application of methodology is presented on the example of pay toll ramp optimization on pay toll station Vrčin. In all analyzed cases the estimated total costs are significantly reduced compared to current policy

структурни пробабалистички модели, Гаусова условна случајна поља, класификација, регресија, предвиђање гужви, теорија редова чекања, нестационарни Марковљеви процеси, oптимизација.

structural probabalistic models, Gaussian conditional radnom fields, classifiaction, regression, congestion prediction, queuing theory, non homogenous Markov process, optimization

519.8:004.85.021(043.3)

Tekst