Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: VRPTW

Sortuj według:

Ogranicz wyniki do:

Adaptive threads co-operation schemes in a parallel heuristic algorithm for the vehicle routing problem with time windows

Nalepa J., Czech Z. J.

Theoretical and Applied Informatics

2012

Vol. 24, No. 3

191-203

The influence of the co-operation frequency of threads in a parallel heuristic algorithm to solve the vehicle routing problem with time windows on the accuracy of solutions is investigated. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger's benchmarking tests. Two adaptive co-operation schemes are proposed and experimentally evaluated.

Wyznaczanie tras dla pojazdów z oknami czasowymi (ang. vehicle routing problem with time windows) jest problemem optymalizacji dyskretnej należącym do klasy problemów NP-trudnych. Istnieją metody heurystyczne rozwiązywania problemu, pozwalające wyznaczyć w rozsądnym czasie rozwiązania nieoptymalne o koszcie bliskim kosztowi rozwiązania optymalnego, takie jak symulowane wyżarzanie, przeszukiwanie tabu, algorytmy genetyczne czy algorytmy memetyczne. Wprzypadku algorytmów dwustopniowych, w pierwszej fazie minimalizowana jest liczba tras, a w fazie drugiej całkowita przebyta odległość. Flota składa się z pojazdów o jednakowej, zdefiniowanej pojemności, która nie może zostać przekroczona, a obsługa klientów musi rozpocząć się w czasie trwania ich okien czasowych.

On the effectiveness of column generation for time constrained routing problems

Haouari M.

Foundations of Computing and Decision Sciences

2001

Vol. 26, No. 3

215-224

This paper describes how column generation techniques can be used to solve to optimality the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW). This problem is practically important and computationally challenging. It involves the joint optimization of the fleet mix and the set of delivery routes. The main contribution of this paper is to show, by an appropriate graph transformation, that the approach previously developed for the classical VRPTW, and based upon the use of the set partitioning formulation and the column generation techniques yields very good results for the FSMVRPTW. The proposed approach is the first optimization algorithm developed so far for the FSMVRPTW. Computational results are reported on a set of test problems with up to 80 customers.