BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Hanczar Paweł (Akademia Ekonomiczna we Wrocławiu)
Tytuł
Dolne ograniczenie problemu wyznaczania tras pojazdów przy zadanym podziale odbiorców
Lower Bound for Set Partitioning Formulations in Vehicle Routing Problem
Źródło
Prace Naukowe Akademii Ekonomicznej we Wrocławiu, 2007, nr 1167, s. 84-92, rys., tab., bibliogr. 5 poz.
Tytuł własny numeru
Współczesne tendencje rozwojowe badań operacyjnych
Słowa kluczowe
Transport, Optymalizacja, Algorytmy
Transport, Optimalization, Algorithms
Uwagi
summ.
Abstrakt
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)
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Bibliografia
Pokaż
  1. 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.
  2. Fisher M., Optimal Solution of Vehicle Routing Problems Using k-tree Problem, "Operations Research" 1988 vol. 42, s. 626-642.
  3. Held M., Karp R. M., The Traveling-salesman Problem and Minimum Spanning Trees, "Operations Research" 1970 vol. 19, s. 1138-1162.
  4. Miller D., A Matching Based Exact Algorithm for Capacitated Vehicele Routing Problem, "ORSA Journal of Computing" 1995 vol. 7, s. 1-9.
  5. 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.
Cytowane przez
Pokaż
ISSN
0324-8445
Język
pol
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu