- Author
- Hanczar Paweł (Akademia Ekonomiczna we Wrocławiu)
- Title
- Dolne ograniczenie problemu wyznaczania tras pojazdów przy zadanym podziale odbiorców
Lower Bound for Set Partitioning Formulations in Vehicle Routing Problem - Source
- Prace Naukowe Akademii Ekonomicznej we Wrocławiu, 2007, nr 1167, s. 84-92, rys., tab., bibliogr. 5 poz.
- Issue title
- Współczesne tendencje rozwojowe badań operacyjnych
- Keyword
- Transport, Optymalizacja, Algorytmy
Transport, Optimalization, Algorithms - Note
- summ.
- Abstract
- Ograniczenie dolne (ang. lower bound) jest wyznaczane przez rozwiązanie relaksacji problemu wyjściowego, uzyskanej najczęściej w wyniku usunięcia z problemu wyjściowego jednego lub kilku ograniczeń. Dla zagadnień minimalizacji rozwiązanie optymalne tak skonstruowanej relaksacji ogranicza rozwiązanie optymalne problemu wyjściowego od dołu i dlatego jest określane mianem dolnego ograniczenia. Różne sposoby relaksacji zagadnienia pierwotnego dają różne wartości dolnego ograniczenia. Podstawowym problemem przy opracowywaniu sposobów wyznaczania dolnego ograniczenia jest znalezienie relaksacji łatwej do rozwiązania, a zarazem dającej możliwie ciasne dolne ograniczenie. Ograniczenie dolne odgrywa bardzo istotną rolę w rozwiązywaniu zadań z zakresu optymalizacji dystrybucji. W sytuacji stosowania algorytmów przybliżonych znajomość dolnego ograniczenia umożliwia szacowanie jakości uzyskanych rozwiązań, natomiast dla metod dokładnych wykorzystanie dolnego ograniczenia jest jednym z głównych elementów ich realizacji. (fragment tekstu)
The lower bound plays a very important role in the solution of combinatorial optimization problems. In the case of usage of heuristic methods, knowledge about lower bound enables the estimation of the quality of achieved solutions. However, in the case of exact methods, particulary in the case of branch and bound methods, the usage of lower bound for the solution subset is one of the algorithms for the solution determination. In this paper we propose a method for finding lower bound for set partitioning formulations of vehicle routing problem. (original abstract) - Accessibility
- The Main Library of the Cracow University of Economics
The Library of Warsaw School of Economics
The Main Library of Poznań University of Economics and Business - Bibliography
-
- Christofides N., Mingozzi A., Toth O., Exact Algorithms for the Vehicle Routing Problem Based on Spanning Tree and Shortest Path Relaxations, "Mathematical Programming" 1981 vol. 20, s. 255-282.
- Fisher M., Optimal Solution of Vehicle Routing Problems Using k-tree Problem, "Operations Research" 1988 vol. 42, s. 626-642.
- Held M., Karp R. M., The Traveling-salesman Problem and Minimum Spanning Trees, "Operations Research" 1970 vol. 19, s. 1138-1162.
- Miller D., A Matching Based Exact Algorithm for Capacitated Vehicele Routing Problem, "ORSA Journal of Computing" 1995 vol. 7, s. 1-9.
- Miller D., Pekny J., A Staged Primal-dual Algorithm for Finding a Minimum Cost Perfect Two-matching in an Undirected graph "ORSA Journal of Computing" 1984 vol. 6, s. 68-81.
- Cited by
- ISSN
- 0324-8445
- Language
- pol
