Algorytm Clarke’a-Wrighta jako źródło początkowego rozwiązania dla algorytmu symulowanego wyżarzania w problemie marszrutyzacji

• Autorzy: Oszelska-Mierzejewska J. , Misztalska E.

Warianty tytułu

EN

Clarke-Wright algorithm as the source of the initial solution for the simulated annealing algorithm in the vehicle routing problem

• Języki publikacji: PL

Abstrakty

PL

W prezentowanym artykule skupiono się na przedstawieniu rozwiązania problemu marszrutyzacji. Zaproponowano tutaj zastosowanie zmodyfikowanego algorytmu Clarke'a-Wrighta jako mechanizmu generowania pierwszego rozwiązania dla algorytmu symulowanego wyżarzania, w celu znalezienia optymalnego rozwiązania dla zadanego problemu. Opisano również przeprowadzone badania symulacyjne ukazujące skuteczność proponowanego rozwiązania wykorzystując zestawy danych o różnym charakterze, a także przedyskutowano otrzymane wyniki z badania doświadczalnego z wykorzystaniem rzeczywistych danych z firmy dystrybucyjnej. Wykazano, że zaproponowane podejście do generowania pierwszego rozwiązania dla metaheurystyki powala uzyskać lepsze wyniki w akceptowalnym czasie, co zostało potwierdzone w badaniu doświadczalnym.

EN

This paper presents a solution to the vehicle routing problem. A modified Clarke-Wright algorithm has been proposed as a mechanism for generating an initial solution for the simulated annealing algorithm, which is then used to find the optimal solution. The effectiveness of the proposed method is examined by means of a simulation study using data sets of various types. The results of an experimental study using real data from a selected distribution company are also discussed. The comparison of the results indicates that the proposed approach to generating the first (initial) solution for metaheuristics is able to produce better results within an acceptable time.

Słowa kluczowe

PL

problem marszrutyzacji; algorytm Clarke'a i Wrighta; algorytm symulowanego wyżarzania; Vehicle Routing Problem; Clarke and Wright Algorithm; Simulated Annealing Algorithm

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2015
• Tom: nr 4
• Strony: 5080--5088, CD 2
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Oszelska-Mierzejewska J.

• Politechnika Łódzka, Wydział Fizyki Technicznej, Informatyki i Matematyki Stosowanej, Instytut Informatyki, 90-924 Łódź, ul. Wólczańska 215

autor

Misztalska E.

• Politechnika Łódzka, Wydział Budownictwa, Architektury i Inżynierii Środowiska, Katedra Mechaniki Materiałów, 90-924 Łódź, Al. Politechniki 6

Bibliografia

• 1. Augerat R., Capacitated VRP Instance, Dostęp [sierpień 2014]: http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances
• 2. Cérny V., A thermodynamical approach to traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Application, vol. 45(1), s. 41-45, 1985.
• 3. 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, vol. 13(3), 1993, s. 371-406.
• 4. Clarke G., Wright J., Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, vol. 12(4), 1964, s. 568-581.
• 5. Cuervo D. P., Goos P., Sörensen K., Arráiz E., An Iterated Local Search Algorithm for the Vehicle Routing Problem with Backhauls. European Journal of Operational Research, vol. 237(2), 2014, s. 454-464.
• 6. Dantzig G. B., Ramser J. H., The Truck Dispatching Problem. Management Science, vol. 6(1), 1959, s. 80-91.
• 7. Dasgupta S., Papdimitriou C., Vazirani U., Algorytmy. Wydawnictwo Naukowe PWN, Warszawa, 2010.
• 8. Hosny M. I., Investigating Heuristic and Meta-Heuristic Algorithms for Solving Pickup and Delivery Problems. Doctorial Thesis, School of Computer Science & Informatics, Cardiff University, United Kingdom, 2010.
• 9. Kirkpatrick S., Gellat C. D., Vecchi M. P., Optimization by simulated annealing. Science, vol. 220(4598), 1983, s. 671-680.
• 10. Letchford A. N., Nasiri S. D., Oukil A., Pricing Routines for Vehicle Routing with Time Windows on Road Networks. Computers & Operations Research, vol. 51, 2014, s. 331-337.
• 11. Ochelska-Mierzejewska J., Sztajerowski W., Rozwiązanie problemu marszrutyzacji z zastosowaniem algorytmu symulowanego wyżarzania. Zarządzenie transportem – wybrane aspekty organizacyjne, (Eds. Lewandowski J., Sekieta M., Bielecki M.), Wydawnictwo Politechniki Łódzkiej, 2014, Nr 2108, Rozdział 9, ISBN 978-83-7283-622-9, s. 131-155.
• 12. Ochelska-Mierzejewska J., Zastosowanie algorytmu symulowanego wyżarzania do rozwiązania problemu dostaw z uwzględnieniem okien czasowych. Logistyka – nauka, Logistyka nr 6/2014, DVD nr 3, ISSN 1231-5478, s. 8043-8052.
• 13. Oliveira, H. C. B.; Vasconcelos, G. C., Vehicle Routing Problem with Time Window. Annals of Operations Research, vol. 180(1), Issue 1 , 2010, s. 125-144.
• 14. Ralphs T. K., Pulleyblank W. R., Trotter L. E., On Capacitated Vehicle Routing. 1998.
• 15. Segerstedt A., A Simple Heuristic for Vehicle Routing. A Variant of Clarke and Wright's Saving Method. International Journal of Production Economics, vol. 157, 2014, s. 74-79.
• 16. Solomon M., Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows Constraints, Operations Research, 1987, s. 254-265.
• 17. Toth P., Vigo D., The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, 2002.
• 18. Tzoreff T. E., Granot D., Granot F., Sošić G., The Vehicle Routing Problem with Pickups and Deliveries on Some Special Graphs, Discrete Applied Mathematics, vol. 116(3), 2002, s. 193-220.
• 19. Żak J., Sawicki P., Porównanie wybranych procedur metaheurystycznych w zastosowaniu do rozwiązywania problemu marszrutyzacji, Zeszyty naukowe Wydziału Mechanicznego, zeszyt 32, s. 156-167, Mielno, 2003.