Rozwiązywanie problemu wyznaczania tras pojazdów za pomocą metody podziału i ograniczeń

• Autorzy: Paweł Hanczar

Warianty tytułu

Solving the Vehicle Routing Problem Based on Branch and Bound Method

• Języki publikacji: PL

Abstrakty

Zaproponowano nowy sposób podziału zbioru rozwiązań problemu wyznaczania tras pojazdów z ograniczeniem pojemności (ang. capacitated vehicle routing problem) w skrócie CVRP. Technikę tą wykorzystano do znajdowania dokładnego rozwiązywania CVRP za pomocą metody podziału i ograniczeń. Prezentowany sposób charakteryzuje łatwe wprowadzanie nowych warunków oraz prosta realizacja. W procesie optymalizacji wykorzystywane są tylko dobrze znane algorytmy stosowane w rozwiązywaniu problemu komiwojażera. Ważną cechą omawianego podejścia jest możliwość skrócenia czasu obliczeń przy wprowadzaniu kolejnych warunków. Działanie algorytmu zaprezentowano na zbiorze zadań testowych. (abstrakt oryginalny)

EN

A new method for the solution set partitioning for Vehicle Routing Problem has been proposed in the paper. It is used in search for an exact VRP solution with the aid of a branch and bound method. The advantages of the method put forward lie in easy implementation and in the new bounds can be readily added. In the optimization process, use is made of the well-known algorithms applied to Travelling Salesman Problem. Another very important characteristic of our approach is the possibility of shortening the calculation time when introducing subsequent bounds. The algorithm was proved effective by solving a set of test problems. (original abstract)

Słowa kluczowe

PL

Transport; Rozwiązywanie problemów; Strategie dystrybucji; Algorytmy

EN

Transport; Solving problems; Distribution strategies; Algorithms

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2002
• Numer: nr 3-4
• Strony: 55--67

Twórcy

autor

Paweł Hanczar

• Akademia Ekonomiczna we Wrocławiu

Bibliografia

• [1] AGARWAL Y., MATHUR K., SALKIN H., A set-partitioning-based exact algorithm for the vehicle routing problem, Networks, 1989, nr 19, s. 731-749.
• [2] BALINSKI M., QUANDT R., On an integer program for a delivery problem, Operations Research, 1964, nr 12, s. 300-304.
• [3] BRAMEL J., SIMCHI-LEVI D., A Location Based Heuristic for General Routing Problem, Operation Research, 1995, nr 43, s. 649-660.
• [4] CHRISTOFIDES N., The vehicle routing problem, RAIRO, 1976, nr 10, s. 55-70.
• [5] CHRISTOFIDES N., Vehicle Rounting, The Traveling Salesman Problem, 1985, John Wiley & Sons, New York, s. 431-448.
• [6] CHRISTOFIDES N., EILON S., An algorithm for the vehicle dispatching problem, Operational Research Quaterly, 1969, nr 20, s. 309-318.
• [7] CHRISTOFIDES N., MINGOZZI A., TOTH P., Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Mathematical Programming, 1981, nr 20, s. 255-282.
• [8] CHRISTOFIDES N., MINGOZZI A., TOTH P., The Vehicle Routing Problem, w Combinatorial Optimization, 1979, John Wiley & Sons, New York, s. 318-338.
• [9] DANTZIG G., RAMSER J., The truck dispatching problem, Management Science, 1959, nr 6, s. 80-91.
• [10] FISHER M., Optimal solution of vehicle routing problem using minimum K-tress, Operations Research, 1994, nr 42, s. 626-646.
• [11] FOSTER B., RYAN D., An integer programming approach to the vehicle scheduling problem, Operational Research Quaterly, 1976, nr 27, s. 367-384.
• [12] GOLDEN B., ASSAD A., Vehicle Routing: Methods and Studies, Elsevier Science Publishers, New York 1988.
• [13] HELD M., KARP H., The traveling salesman problem and minimum spanning tress, Operations Research, 1970, nr 18, s. 1138-1162.
• [14] LENSTRA J.K., KAN A.H.G., Complexity of vehicle routing and scheduling problems, Networks, 1981, nr 11, s. 221-227.
• [15] LIPSKI W., Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa 1989.
• [16] LITTLE J., MURTY K., SWEENEY K., KAREL D., An algorithm for traveling salesman problem, Operations Research, 1963, nr 11, s. 972-989.