Wspomaganie decyzji w obszarze wyznaczania tras pojazdów

• Autorzy: Paweł Hanczar

Warianty tytułu

Decision Support Models for Vehicle Routing Problems

• Języki publikacji: PL

Abstrakty

Problem wyznaczania tras pojazdów jest znany już od 1959 roku. Od tego czasu rozważono wiele różnych wersji tego zadania, a także opracowano wiele algorytmów jego rozwiązywania. Wraz z rozwojem nowych koncepcji w zakresie zarządzania przedsiębiorstwem w obszarze planowania tras wciąż pojawiają się nowe wymagania. W pierwszej części artykułu zostały przedstawione klasyczne sformułowania problemu wyznaczania tras pojazdów oraz wybrane metody jego rozwiązywania. Następnie w części drugiej zaprezentowano główne, zdaniem autora, kierunki rozwoju modeli wyznaczania tras pojazdów. W części tej przedstawiono także nowe propozycje metod ich rozwiązywania wraz z oceną ich skuteczności. Jako pierwszy kierunek przedstawiono zagadnienie wyznaczania tras przepływu zapasów określane często jako zarządzanie zapasami sterowane przez dostawcę. Następnie rozważono zagadnienie wyboru dostawcy usług transportowych w warunkach różnych taryf transportowych. Jako ostatnie zaprezentowano zagadnienie wyznaczania tras pojazdów w wielopoziomowych sieciach dystrybucyjnych. (abstrakt oryginalny)

EN

Research in the field of vehicle routing problem started in 1959. For more then 50 years a lot of versions of this problem have been considered and many solution methods have been developed. Unfortunately new management concepts continuously put out the challenge to vehicle routing researchers. Presented paper is divided into two parts. In the first part the classical vehicle routing formulations and their solution methods were presented. In the second part the three main directions of advance are identified and briefly described. The new solution approaches to finding solution to the new variants of vehicle routing problem are proposed and tested. Firstly we conduct new solution methods to inventory routing problem. Then the common case of the vehicle routing problem in different distribution tariff environment is analyzed. Lastly the vehicle routing problem in multiechelon distribution networks is considered. (original abstract)

Słowa kluczowe

PL

Podejmowanie decyzji; Informacja w podejmowaniu decyzji; Łańcuch dostaw; Zarządzanie flotą pojazdów

EN

Decision making; Information in decision making; Supply chain; Fleet management

• Czasopismo: Decyzje
• Rocznik: 2010
• Numer: nr 13
• Strony: 55--83

Twórcy

autor

Paweł Hanczar

• Uniwersytet Ekonomiczny we Wrocławiu

Bibliografia

• Adenso-Diaz, B., Gonzalez, M., Garcia, E. 1998 A hierarchical approach to managing dairy routing. "Interfaces" 28: 21-31.
• Agarwal, Y., Mathur, K., Salkin, H. 1989. A set-partitioning-based exact algorithm for the vehicle routing problem. "Networks" 19: 731-749.
• Altinkemer, K., Gavish, B. 1991. Parallel savings based heuristic for the delivery problem. "Operations Research" 39: 456-469.
• Balinski, M., Quandt, R. 1964. On an integer program for a delivery problem. "Operations Research" 12: 300-304.
• Bell, W., Dalberto, L., Fisher, M., Greeneld, A., Jaikumar, R., Kedia, P., Mack, R., Prutzman, P. 1983. Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. "Interfaces" 6.
• Beltrami, E., Bodin, L. 1974. Networks and vehicle routing for municipal waste collection. "Networks" 4: 65-94.
• Blasum, U., Hochstättler, W. 2000. Application of the Branch and Cut Method to the Vehicle Routing Problem. Technical Report zaik 2000-386, Centre of Applied Computer Science, Uniwersytet Koloński, Niemcy (dostępne http://www.zaik.uni-koeln.de/paper).
• Caprara, A., Fischetti, M. 1997. Branch-and-cut algorithms. W: Dell'Amico M., Maffioli F., Martello S. (red.), Annotated Bibliographies in Combinatorial Optimization, New York: Wiley, 45-64.
• Chien, T., Balakrishnan, A., Wong, R. 1989. An integrated inventory allocation and vehicle routing problem. "Transportation Science" 2.
• Christofides, N., Elion, S. 1969. An Algorithm for the Vehicel Dispatching Problem. "Operational Research Quarterly" 20: 309-318.
• Clarke, G., Wright, J. 1964. Scheduling of vehicles from central depot to a number of delivery points. "Operations Research" 12: 568-581.
• Cline, A., King, D., Meyering, J. 1992. Routing and scheduling Coast Guard buoy tenders. "Interfaces" 22: 56-72.
• Dantzig, G., Ramser, J. 1959. The truck dispatching problem. "Management Science" 6: 80-91.
• De Backer, B., Furnon, V., Shaw, P., Kilby, P., Prosser, P., 2000. Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics. "Journal of Heuristics" 6: 501-523.
• Desrochers, M., Desrosiers, J., Solomon, M., 1992. A new optimization algorithm for the vehicle routing problem with time windows. "Operations Research" 40: 342-354.
• Fiala Timlin, M., Pulleyblank, W. 1992. Precedence constrained routing and helicopter scheduling: Heuristics desing. "Interfaces" 22: 100-111.
• Fisher, M.L., Jaikumar, R. 1981. A generalized assignment heuristic for vehicle routing. "Networks" 11: 109-124
• Fisher, M., 1988. Optimal solution of vehicle routing problems using k-tree problem. "Operations Research" 42: 626-642.
• Gaskell, T. 1967. Bases for vehicle fleet scheduling. "Operational Research Quarterly" 18: 281-295.
• Gillett, B., Miller, L. 1976. A heuristic algorithm for the vehicle dispatch problem. "Operations Research" 22: 340-349.
• Golden, B., Assad, A. 1988. Vehicle Routing: Methods and Studies. New York. Elsevier Science Publishers Golden, B., Assad, A., Dahl, R. 1984. Analysis of a large scale vehicle routing problem with inventory component. "Large Scale Systems" 7.
• Golden, B., Magnanti, T., Nguyen, H. 1977. Implementing vehicle routing algorithms. "Networks" 7: 113-148.
• Golden, G., Assad, A., Wasil, E. 2002. Routing Vehicles in the Real World: Applications in the Solid Waste, Beverage, Food, Dairy and Newspaper Industries. W: Toth P., Vigo D. The Vehicle Routing Problem. Philadelphia. Wiley, s 245-279.
• Gourley, G. 1998 Distribution systems ease products down the road. "Food Engineering" 7-8: 91.
• Greczyn, M. 1997. Computers tackle Pennsylvania routes. "Waste News" 27: 23.
• Hadjiconstantinou, E., Christofieds, N., Mingozzi, A. 1995. A new exact algorithm for the vehicle routing problem based on q-paths and k-shortest paths relaxations. "Annals of Operations Research" 61: 21-43.
• Hanczar, P. 2006. Problemy w planowaniu dostaw w koncepcji uzupełniania zapasów sterowanego przez dostawcę. Referat wygłoszony na Pierwszej Międzynarodowej Konferencji Logistycznej INTLOG 2006. Gdynia - Sztokholm.
• Hanczar, P. 2008. Transport planning in conditions of different transport tariffs - application of integer programming. W: "Total Logistics Management" 1: 25-33. Kraków. AGH Press.
• Hannon, D. 2005. Best practices: Five key initiatives. "Purchasing" 1.
• Laporte, G., Nobert, Y. 1987 Exact algorithms for the vehicle routing problem. "Annals of Discrete Mathematics" 31: 147-184.
• Larson, R., Minkoff, A., Gregory, P. 1988. Fleet sizing and dispatching for the marine division on the New York City Departament of Sanitation. W: Golden B., Assad A., Vehicle Routing: Methods and Studies. Amsterdam. Wiley, 395-423.
• Little, J.D.C, Murty, K.G., Sweeney, D.W., Karel, C., 1963. An algorithm for the traveling salesman problem. "Operations Research" 11: 972-989.
• Mans, J. 1997 Downloading distribution. "Dairy Foods" 8.
• Miller, D., 1995. A matching based exact algorithm for capacitated vehicele routing problem. "ORSA Journal of Computing" 7: 1-9.
• Mongelluzzo, B. 1998. Shippers let vendors manage the stock: Wal-mart's suppliers share in databases. "Journal of Commerce and Commercial" 12A: 417.
• Padberg, M., Rinaldi, G., 1991. A branch and cut algorithm for the resolution of largescale symetric traveling salesman problems. "SIAM Review" 33: 60-100.
• Paessens, H. 1988. The savings algorithm for the vehicle routing problem. "European Journal of Operations Research" 34: 336-344.
• Prutzman, P. 1983. Improving the distribution of industrial gases with an on-line Rich, J. 1999. A Computational Study of Vehicle Routing Aplications. Praca doktorska. Rice University Houston.
• Sfiligoj, E. 1997. One for the road. "Beverage World" 11.
• Thienel, S., 1995. ABACUS: A Branch and Cut System. Praca doktorska, Universitaet zu Koeln.
• Waller, M., Johnson, M. E., Davis, T. 1999. Vendor-managed inventory in the retail.
• Wark, P., Holt, J. 1994. A repeated matching heuristic for the vehicle routing problem. "Journal of Operational Research Society" 45: 1156-1167.
• Wren, A., Holliday, A. 1972. Computer scheduling of vehicles from one or more depots to a number of delivery points. "Operational Research Quarterly" 23: 333-344.
• Yellow, P. 1970. A computational modification to the savings method of vehicle scheduling. "Operational Research Quarterly" 21: 281-283.