Warianty tytułu
An Approach to Robust Traveling Salesmen Problem with Interval Data in A Company
Języki publikacji
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)
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)
Czasopismo
Rocznik
Numer
Strony
277--292
Opis fizyczny
Twórcy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171279467