Zastosowanie algorytmu symulowanego wyżarzania do rozwiązania problemu dostaw z uwzględnieniem okien czasowych

• Autorzy: Ochelska-Mierzejewska J.

Warianty tytułu

EN

The application of simulated annealing algorithm to the solving of vehicle routing problem with time window

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono autorskie rozwiązanie problemu optymalizacji dostaw rozszerzonego o uwzględnienie okien czasowych z wykorzystaniem algorytmu symulowanego wyżarzania. Algorytm symulowanego wyżarzania został zmodyfikowany poprzez stworzenie oryginalnych algorytmów generowania pierwszego rozwiązania oraz znajdowania najlepszego miejsca na trasie, a także algorytmu optymalizacji wszystkich tras, aby umożliwić go do rozwiązania problemu marszrutyzacji. W artykule przedstawiono wyniki badań eksperymentalnych pokazujących, że uzyskane wyniki są bliskie tym otrzymanym przez planistów. Natomiast uzyskana znaczna redukcja czasu generowania wynikó,w w porównaniu z tymi otrzymywanymi przez osoby w firmie gwarantuje obniżenie kosztów wyznaczania tras dostaw.

EN

The article presents a novel method of solving the vehicle routing problem with time windows based on a modified simulated annealing algorithm. The novelty lies in the introduction of new algorithms for generating the first solution and finding the next best location along the route. The algorithm for the optimisation of all routes is also proposed. The results of the experimental study presented in this paper are comparable to those produced by route planners in a company. However, the times of results generation are significantly reduced compared with those obtained by route planners. Thus, the proposed method can be considered as a way to minimise the cost of vehicle route planning.

Słowa kluczowe

PL

algorytm symulowanego wyżarzania; optymalizacja dostaw; okno czasowe

EN

simulated annealing algorithm; time window; route planning

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 6
• Strony: 8043--8052
• Opis fizyczny: Bibliogr. 9 poz., rys., tab., wykr., pełny tekst na CD3

Twórcy

autor

Ochelska-Mierzejewska J.

• Instytut Informatyki, Politechnika Łódzka, ul. Wólczańska 215, 90-924 Łódź

Bibliografia

• 1. Cérny V.,A thermodynamical approach to traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Application, 45, pp. 41-45, 1985.
• 2. Chao I.M., Golden B., Wasil E.,A New Heuristic for the Multi-Depot Vehicle Routing Problem that Improves Upon Best-Known Solutions. American Journal of Mathematical and Management Sciences, 13, pp. 371-406, 1993.
• 3. Dantziga G., Ramser R., The Truck Dispatching Problem. Management Science 6, pp. 80-91, 1959.
• 4. Kirkpatrick S., Gellat C.D., Vecchi M.P., Optimization by simulated annealing. Science, 220, pp. 671-680, 1983.
• 5. Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Equation of state calculation by fast computing machines. Journal Of Chemical Physics ., 21, pp.1087-1091, 1953.
• 6. Oliveira, H.C.B.de; Vasconcelos, G.C., Vehicle Routing Problem with Time Window. Annals of Operations Research, Volume 180, Issue 1 , pp. 125-144, 2010.
• 7. Ralphs T. K., Pulleyblank W. R., Trotter L. E., On Capacitated Vehicle Routing. 1998.
• 8. Solomon M., Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows Constraints. Operations Research, pp. 254-265 , 1987.
• 9. Woch M., Łebkowski P., Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows. Decision Making in Manufacturing and Services, vol. 3, no. 1-2., pp. 87-100, 2009.