Multi-agent Approach to Dynamic Pick-up and Delivery Problem with Uncertain Knowledge about Future Transport Demands

• Autorzy: Koźlak J. , Créput J-C. , Hilaire V. , Koukam A.
• Języki publikacji: EN

Abstrakty

EN

This work focuses on the dynamic Pickup and Delivery Problem with Time Windows (PDPTW). The transport requests should be performed using the available fleet of vehicles. The vehicles move between the nodes of a road network. The aim of this work is to propose a model which allows, during a transport plan creation, to take into account predictable events. Particularly, we consider the frequency of requests at any node in the road network and the construction of vehicle routes that will allow new requests to be inserted without any significant route modification. Therefore, we construct routes that pass near the nodes where transport requests are most frequently generated.

Słowa kluczowe

EN

transport planning and scheduling; dynamic PDPTW; multi-agent systems

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 71, nr 1
• Strony: 27--36
• Opis fizyczny: wykr., bibliogr. 12 poz.

Twórcy

autor

Koźlak J.

autor

Créput J-C.

autor

Hilaire V.

autor

Koukam A.

• Computer Science Department, AGH University of Science and Technology al. Mickiewicza 30,Kraków, Poland,

Bibliografia

• [1] Bachem, A., Hochstattler, W., Malich, M.: Simulated Trading A New Parallel Approach for Solving Vehicle Routing Problems, Proceedings of the International Conference Parallel Computing: Trends and Applications, 1994.
• [2] Burckert, H.-J., Fischer, K., Vierke, G.: Transportation scheduling with holonic MAS - the TELETRUCK approach, Third International Conference on Practical Applications of Intelligent Agents and Multiagents (PAAM 98, 1998.
• [3] Cordeau, J.-F., Laporte, G.: The Dial-a-Ride Problem: Variants, Modeling Issues and Algorithms, Les Cahiers du GERAD, 2002.
• [4] Davenport, A., Beck, J.: A Survey of Techniques for Scheduling with Uncertainty, technical report, http://www.mie.utoronto.ca/staff/profiles/beck/uncertainty-survey.ps.zip, 2000.
• [5] Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M. M., Soumis, F.: The VRP with Pickup and Delivery, Les Cahiers du GERAD, 2000.
• [6] Ferber, J., Gutknecht, O., Mechel, F.: MadKit Development Guide Version 3.1, WWW page, http://www.madkit.org, 2004.
• [7] Fischer, K., Muller, J., Pischel, M.: Cooperative Transportation Scheduling: an Application Domain for DAI, Applied Artificial Intelligence, 1996, 1-33.
• [8] Gendreau, A., Guertin, F., Potvin, J., S'guin, R.: Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Technical report CRT-98-1, University of Montreal, 1998.
• [9] Kozlak, J., Creput, J.-C., Hilaire, V., Koukam, A.: Muti-agent environment for dynamic transport planning and scheduling, Computational Science - ICCS 2004, 4th International Conference, Krakow, Poland, June 6-9, Part 3 (M. Bubak, G. van Albada, P. Sloot, J. Dongara, Eds.), Lecture Notes in Computer Science 3038, Springer-Verlag, 2004.
• [10] Mitrowic-Minic, S.: Pickup and Delivery Problem with TimeWindows: A Survey, SFU CMPT TR. 1998-12, ftp://fas.sfu.ca/pub/cs/techreports/1998, 1998.
• [11] Pinedo, M.: Scheduling. Theory, Algorithms, and Systems, Prentice-Hall, 2002.
• [12] Smith, R. G.: The contract net protocol: high-level communication and control in a distributed problem solver, IEEE Transactions on Computer, December 1980, 1104-1113.