Sposoby wyznaczania odpornych tras komiwojażera w przedsiębiorstwie

• Autorzy: Bogusz Przybysławski

Warianty tytułu

An Approach to Robust Traveling Salesmen Problem with Interval Data in A Company

• Języki publikacji: PL

Abstrakty

W artykule zamodelowano sieć dystrybucji pieczywa przez piekarnię, w której kierowca odwiedza ustalone punkty i wraca do miejsca startu. Czas przejazdu pomiędzy poszczególnymi punktami jest niepewny, wyrażony jako reprezentacja przedziałowa. Scenariusz odpowiada pewnemu stanowi świata, który w danej chwili występuje w sieci transportowej. Poszukuje się ścieżki, która gwarantuje optymalną trasę bez względu na scenariusz, który wystąpi (dla każdej możliwej konfiguracji czasów). Zaproponowano dwie metody rozwiązania problemu: algorytm AMU oraz heurystykę lokalnego przeszukiwania 2-opt. Do uzyskania wyników zastosowano ogólnodostępne narzędzia. (abstrakt oryginalny)

EN

This paper concerns a bakery distribution network, where a salesman starts and ends his route at the same point and the travel time is uncertain. A scenario can be seen as a snapshot representing the real network situation, where a travel time takes value between a lower and upper bound. We seek a tour that should guarantee reasonably good performance under any possible configuration of costs. We proposed two methods to get a solution. Namely an AMU algorithm and local search heuristic 2-opt is adopted. To obtain results we use open source tools. (original abstract)

Słowa kluczowe

PL

Algorytm transportowy; Planowanie w transporcie; Zarządzanie transportem; Modele matematyczne

EN

Transport algorithm; Planning in transport; Transport management; Mathematical models

• Czasopismo: Zarządzanie i Finanse
• Rocznik: 2013
• Numer: R. 11, nr 1, cz. 2
• Strony: 277--292

Twórcy

autor

Bogusz Przybysławski

• Politechnika Wrocławska

Bibliografia

• Helsgaun K. (2000), An effective implementation of the lin-kernighan traveling salesman heuristic, "European Journal of Operational Research", nr 126 (1).
• Jonker R., Volgenant T. (1983), Transforming asymmetric into symmetric traveling salesman problems, "Operations Research Letters", nr 2 (4).
• Karasan O.E., Pinar M.C., Yaman H. (2001), The robust shortest path problem with interval data, Bilkent University.
• Kasperski, A., Zieliński P. (2006), An approximation algorithm for interval data minmax regret combinatorial optimization problems, "Information Processing Letters", nr 97 (5).
• Kouvelis P., Yu G. (1997), Robust discrete optimization and its applications, Kluwer Academic Publishers.
• Lin S., Kernigham B.W. (1973), An effective heuristic algorithm for the traveling salesman problem, "Operations Research", nr 21.
• Luce R. D., Raiffa H. (1957), Games And Decisions: Introduction and Critical Survey. Dovers Publications.
• Miller C.E., Tucker A.W., Zemlin R.A. (1960), Integer programming formulation of traveling salesman problems, "Journal of the ACM".
• Montemanni R., Barta J., Mastrolilli M., and Gambardella L. (2007), The robust traveling salesman problem with interval data, Transportation Science, (41).
• Sysło M. M., Deo N., Kowalik J. S. (1993), Algorytmy optymalizacji dyskretnej z programami w języku Pascal, PWN Warszawa.
• Yaman H., Karasan O., Pinar M. (2001), The robust spanning tree problem with interval data, "Operations research letters", nr 29.
• http://maps.google.pl, dostęp dnia 06.01.2013.
• http://mapa.targeo.pl, dostęp dnia 06.01.2013.