Multiobjective fuzzy approach to the vehicle routing problem with time windows

• Autorzy: Wesołek P. , Kubiak M.

Warianty tytułu

PL

Wielokryterialny problem planowania tras z oknami czasowymi w wersji rozmytej

• Języki publikacji: EN

Abstrakty

EN

The paper presents a model of the vehicle routing problem with flexible (fuzzy) constraints. This kind of model allows a decision maker to explore a set of alternatives with diverse cost and constraint satisfaction levels. The model is tested on well-known instances of the vehicle routing problem with time windows adjusted to the fuzzy case. They are solved by a multiobjective Pareto Memetic Algorithm. The obtained results indicate that the introduction of fuzzy constraints leads to exploration of new alternatives which may be interesting to a decision maker.

PL

Artykuł prezentuje model problemu planowania tras z elastycznymi (rozmytymi) ograniczeniami. Model takiego rodzaju pozwala decydentowi na wybór rozwiązania spośród zbioru alternatyw ze zróżnicowanym kosztem i stopniem spełnienia ograniczeń. Ten model został przetestowany na klasycznym zestawie instancji problemu planowania tras z oknami czasowymi dostosowanych do przypadku rozmytych ograniczeń. Rozwiązania są uzyskiwane przez użycie wielokryterialnego algorytmu memetycznego. Uzyskane wyniki wskazują na to, że wprowadzenie elastycznych ograniczeń prowadzi do odkrycia rozwiązań, które mogą być interesujące z punktu widzenia decydenta

Słowa kluczowe

EN

fuzzy vehicle routing; flexible constraints; multiobjective optimization

PL

planowanie tras; ograniczenia elastyczne; optymalizacja wielokryterialna

• Wydawca: Polskie Towarzystwo Diagnostyki Technicznej
• Czasopismo: Diagnostyka
• Rocznik: 2006
• Tom: nr 2(38)
• Strony: 21--24
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Wesołek P.

autor

Kubiak M.

• Poznan University of Technology, Institute of Computing Science, Piotrowo Street 2, 60-965 Poznań, Poland,

Bibliografia

• [1] Dubois D., Fargier H., Prade H.: Fuzzy constraints in job-shop scheduling, Journal of Intelligent Manufacturing, 1995, Vol. 6.
• [2] Dubois D., Prade H.: Possibility Theory. Plenum Press, New York, 1988.
• [3] Hadjiconstantinou E., Roberts D.: Routing under uncertainty: an application in the scheduling of field service engineers. In: Toth P., Vigo D. (eds.): The Vehicle Routing Problem, 2002, Philadelphia, SIAM.
• [4] Hapke M., Wesołek P.: Handling imprecision and flexible constraints in vehicle routing problems: fuzzy approach. Technical report RA-005/2003, Poznan University of Technology, 2003.
• [5] Jaszkiewicz A.: On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study. European Journal of Operational Research, 2004, Vol. 158, pp. 418-433.
• [6] Kubiak M.: Systematic construction of recombination operators for the vehicle routing problem. Foundations of Computing and Decision Sciences, 2004, Vol. 29, No. 3.
• [7] Potvin J.-Y., Bengio S.: The vehicle routing problem with time windows part ii: genetic search. INFORMS Journal of Computing,, 1996, Vol. 8, No. 2.
• [8] Rahoual M., et al.: Multicriteria genetic algorithm for the vehicle routing problem with time windows. Metaheuristics International Conference, Porto, Portugal, 2001, pp. 527-532.
• [9] Solomon M. M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987, Vol. 35, No. 2, pp. 254-265.
• [10] Taillard É., Badeau P., Gendreau M., Guertin F., Potvin J.-Y.: A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 1997, Vol. 31, No. 2, pp. 170-186.
• [11] Zimmermann H.-J.: Description and optimization of fuzzy systems. International Journal of General Systems, 1976, Vol. 2, pp. 202-216.
• [12] Zitzler E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 1999, Vol. 3., No. 4, pp. 257-271.