Dualizm logistyczno-kombinatoryczny zadania komiwojażera

W pracy został przedstawiony dualny charakter problemu komiwojażera (TPS –Travelling Salesman Problem), który może być jednocześnie rozpatrywany jako utylitarne zadanie transportowe według kryteriów logistycznych oraz jako złożony problem kombinatoryczny optymalizacji dyskretnej. W aspekcie optymalizacyjnym zadanie TSP należy do problemów NP-zupełnych, dla których w ogólności nie istnieją efektywne metody rozwiązań. Ze względu na bardzo szeroki zakres logistycznych aplikacji zadania TSP, dokonano prezentacji najbardziej popularnych metod jego rozwiązania. Szczególną uwagę zwrócono na nowoczesne podejście oparte na metodach sztucznej inteligencji i algorytmach mrówkowych. Klasyczny problem TSP jest szczególnym przypadkiem bardzo ważnego we współczesnej logistyce wielowymiarowego problemu marszrutacji rzutującego m.in. na globalne koszty działalności transportowej i logistycznej.

---

At the work described dual character of the vehicle routing stayed (TPS – Travelling Salesman Problem) which can simultaneously be considered as the utilitarian transport task according to logistic criteria and as a combinatorial many-sided problem of discreet optimization. In the operational research aspect the TSP task is included in problems NP-complete, which in general effective methods of solutions don’t exist for. On account of very wide range of logistic applications of the TSP task they made the pre-sentation the most of popular methods of untying him. They paid special attention to the modern attempt based on methods of the artificial intelligence and ant algorithms. The classic TSP problem is a special case very much important in the contemporary logistics of the multidimensional problem route projecting among others onto total costs of transport and logistic activity.