article

Multi-agent approach to dynamic pick-up and delivery problem with uncertain knowledge about future transport demands

Authors:

Jaroslaw Koźlak,

Jean-Charles Créput,

Vincent Hilaire,

Abder KoukamAuthors Info & Claims

Fundamenta Informaticae, Volume 71, Issue 1

Pages 27 - 36

Published: 01 January 2006 Publication History

Abstract

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.

References

[1]

{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.

Google Scholar

[2]

{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.

Google Scholar

[3]

{3} Cordeau, J.-F., Laporte, G.: The Dial-a-Ride Problem: Variants, Modeling Issues and Algorithms, Les Cahiers du GERAD, 2002.

Google Scholar

[4]

{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.

Google Scholar

[5]

{5} Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M. M., Soumis, F.: The VRP with Pickup and Delivery, Les Cahiers du GERAD, 2000.

Google Scholar

[6]

{6} Ferber, J., Gutknecht, O., Mechel, F.: MadKit Development Guide Version 3.1, WWW page, http://www.madkit.org, 2004.

Google Scholar

[7]

{7} Fischer, K., Muller, J., Pischel, M.: Cooperative Transportation Scheduling: an Application Domain for DAI, Applied Artificial Intelligence, 1996, 1-33.

Google Scholar

[8]

{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.

Google Scholar

[9]

{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.

Google Scholar

[10]

{10} Mitrowic-Minic, S.: Pickup and Delivery Problem with Time Windows: A Survey, SFU CMPT TR. 1998-12, ftp://fas.sfu.ca/pub/cs/techreports/1998, 1998.

Google Scholar

[11]

{11} Pinedo, M.: Scheduling. Theory, Algorithms, and Systems, Prentice-Hall, 2002.

Digital Library

Google Scholar

[12]

{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.

Digital Library

Google Scholar

Cited By

View all

Egan MJakob M(2014)A profit-aware negotiation mechanism for on-demand transport servicesProceedings of the Twenty-first European Conference on Artificial Intelligence10.5555/3006652.3006699(273-278)Online publication date: 18-Aug-2014
https://dl.acm.org/doi/10.5555/3006652.3006699
Xia YZhang TWang S(2014)A Generic Methodological Framework for Cyber-ITSFundamenta Informaticae10.5555/2692058.2692061133:1(35-53)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/2692058.2692061
Śnieżyński BKoźlak J(2011)Agent-based system with learning capabilities for transport problemsProceedings of the Third international conference on Computational collective intelligence: technologies and applications - Volume Part II10.5555/2041914.2041927(100-109)Online publication date: 21-Sep-2011
https://dl.acm.org/doi/10.5555/2041914.2041927
Show More Cited By

Index Terms

Multi-agent approach to dynamic pick-up and delivery problem with uncertain knowledge about future transport demands
1. Computing methodologies
  1. Artificial intelligence
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A Novel Approach for Dynamic Traffic Assignment Based on Multi-Agent Node Reservation: Comparative Study on Two Competing Roads
Abstract
This paper aims to contribute to the challenging issue of one microscopic simulation round for dynamic traffic assignment. It relays on the selfish behavior of the vehicle agent that benefits from a more accurate estimation of its travel time. The ...
Multi agent parking lots modelling for anomalies detection while parking

Recently crowded cities are having an increasing need for an advanced parking management system to help drivers to locate the vacant and available parking places in real time. In this study, the authors propose a novel multi agent parking lots management ...
An application oriented multi-agent based approach to dynamic load/truck planning

A novel multi-agent system for dynamic load and truck planning.A realistic simulation with real data from a major transportation company.A practical negotiation based model for real life implementations.Detailed explanations and numerical examples are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Fundamenta Informaticae Volume 71, Issue 1

Special issue on theory and applications of soft computing (TASC04)

July 2006

133 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 January 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Egan MJakob M(2014)A profit-aware negotiation mechanism for on-demand transport servicesProceedings of the Twenty-first European Conference on Artificial Intelligence10.5555/3006652.3006699(273-278)Online publication date: 18-Aug-2014
https://dl.acm.org/doi/10.5555/3006652.3006699
Xia YZhang TWang S(2014)A Generic Methodological Framework for Cyber-ITSFundamenta Informaticae10.5555/2692058.2692061133:1(35-53)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/2692058.2692061
Śnieżyński BKoźlak J(2011)Agent-based system with learning capabilities for transport problemsProceedings of the Third international conference on Computational collective intelligence: technologies and applications - Volume Part II10.5555/2041914.2041927(100-109)Online publication date: 21-Sep-2011
https://dl.acm.org/doi/10.5555/2041914.2041927
Zeddini BYassine ATemani MGhédira KBenslimane DOuksel A(2008)Collective intelligence for demand-responsive transportation systemsProceedings of the 8th international conference on New technologies in distributed systems10.1145/1416729.1416778(1-8)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1145/1416729.1416778

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

A Novel Approach for Dynamic Traffic Assignment Based on Multi-Agent Node Reservation: Comparative Study on Two Competing Roads

Multi agent parking lots modelling for anomalies detection while parking

An application oriented multi-agent based approach to dynamic load/truck planning

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations