We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD). In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed. We denote this stochastic version by S-MDVRPPD. One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route. The objective is to find a solution with minimum expected traveling distance. We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions. To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure. The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work. We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances. The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We will show a validated method to compute the stability radius for polynomials based on stabilization techniques. Graillat and Langlois proposed an algorithm to compute the stability radius for polynomials using pseudozeros of the polynomials. Since the algorithm is based on algebraic manipulations, it might be unstable if the coefficients of the input polynomials are floating point numbers. In fact, it is well-known that Sturm's theorem which is used in the algorithm is unstable for relatively large degree input polynomials. Here, we apply the stabilization method to the algorithm, and we propose an validated algorithm to compute the stability radius for polynomials. Two examples will be given to show effectiveness of the proposed algorithm.
PL
Komputerowe systemy wspomagające projektowanie wymagają od swoich twórców wyboru własciwej: uniwersalnej i odpornej na błędy użytkownika, procedury optymalizacji. Często proponowanym rozwiązaniem jest wykorzystanie w takich systemach algorytmów ewolucyjnych. W tym artykule próbujemy pokazać że taki wybór nie zawsze jest właściwy. Zastosowanie klasycznego algorytmu deterministycznego prowadzi bowiem do lepszego rozwiązania, które ponadto jest znajdowane znacznie szybciej. Rozwaząnia zostały zilustrowane przykładem systemu wspomagającego projektowanie przepływomierzy elektromagnetycznych.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Choice of a robust and universal optimization procedure is one of the crucial design decision for many Computer Aided Design systems. Evolutionary Algorithms are commonly advised in such situations. This paper shows, that such choice is not always the best one. Use of a classical deterministic procedure may lead to better results which are obtained much faster. Example CAD system for electromagnetic flow meters design is used as a practical example illustrating the problem.
PL
Komputerowe systemy wspomagające projektowanie wymagają od swoich twórców wyboru właściwej: uniwersalnej i odpornej na błędy użytkownika, procedury optymalizacji. Często proponowanym rozwiązaniem jest wykorzystanie w takich systemach algorytmów ewolucyjnych. W tym artykule próbujemy pokazać, że taki wybór nie zawsze jest właściwy. Zastosowanie klasycznego algorytmu deterministycznego prowadzi bowiem do lepszego rozwiązania, które ponadto jest znajdowane znacznie szybciej. Rozważania zostały zilustrowane przykładem systemu wspomagającego projektowanie przepływomierzy elektromagnetycznych.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.