Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: robust optimisation

Sortuj według:

Ogranicz wyniki do:

Improving logic-based Benders’ algorithms for solving min-max regret problems

Assunção Lucas, Santos Andréa Cynthia, Noronha Thiago F., Andrade Rafael

Operations Research and Decisions

2021

Vol. 31, No. 2

23--57

This paper addresses a class of problems under interval data uncertainty, composed of min-max regret generalisations of classical 0-1 optimisation problems with interval costs. These problems are called robust-hard when their classical counterparts are already NP-hard. The state-of-the-art exact algorithms for interval 0-1 min-max regret problems in general work by solving a corresponding mixed- -integer linear programming formulation in a Benders’ decomposition fashion. Each of the possibly exponentially many Benders’ cuts is separated on the fly by the resolution of an instance of the classical 0-1 optimisation problem counterpart. Since these separation subproblems may be NP-hard, not all of them can be easily modelled using linear programming (LP), unless P equals NP. In this work, we formally describe these algorithms through a logic-based Benders’ decomposition framework and assess the impact of three warm-start procedures. These procedures work by providing promising initial cuts and primal bounds through the resolution of a linearly relaxed model and an LP-based heuristic. Extensive computational experiments in solving two challenging robust-hard problems indicate that these procedures can highly improve the quality of the bounds obtained by the Benders’ framework within a limited execution time. Moreover, the simplicity and effectiveness of these speed-up procedures make them an easily reproducible option when dealing with interval 0-1 min-max regret problems in general, especially the more challenging subclass of robust-hard problems.

Predykcyjny model planowania tras pojazdów w warunkach niepewności z zastosowaniem sztucznych sieci neuronowych

Kubek D., Więcek P.

Prace Naukowe Politechniki Warszawskiej. Transport

2018

z. 120

231--240

W artykule zaprezentowano autorskie podejście do planowania tras pojazdów w warunkach niepewności, które bazuje na krótkookresowych prognozach czasu przejazdu w sieci drogowej miasta. Model predykcyjny został stworzony z wykorzystaniem sztucznych sieci neuronowych. Niepewność wartości czasu przejazdu została zamodelowana w oparciu o wyznaczone wielkości prognozy oraz jej błędy, które zostały wykorzystane do zdefiniowania zbioru niepewności dla parametrów modelu planowania tras pojazdów. Charakterystykę oraz zalety stosowania zaproponowanej metodyki zilustrowano przykładem symulacyjnym bazującym na wybranej sieci drogowej miasta Krakowa.

The article presents the author's approach to planning vehicle routes in conditions of uncertainty, which is based on short-term forecasts of the travel time in the city's road network. The prediction model was created on the basis of the artificial neural networks. The uncertainty of the time value was modelled on the basis of the estimated values of the forecast and its errors, which were used to define the set of uncertainty for the parameters of the vehicle route planning model. The characteristics and advantages of the proposed methodology are illustrated on the basis of a simulation example based on a selected road network of the city of Kraków.