knowledge transfer


Opportunistic planning for a fleet of transportation robots

Submitted by Josefa Z. Hernandez 27.11.2001, IBA B


The Dynamic Transportation-Planning Problem (DTPP) embodies a class of real-world applications that involve the reactive routing and scheduling of a fleet of taxi vehicles in an urban road network in response to dynamically changing transportation demands. The complexity associated with dynamic transportation problems is enormous. Therefore there are a lot of constraints such as time windows, deadlines, carrier capacities, trip duration, resource optimisation, and moreover there can be unpredictable events like traffic situations, weather conditions and vehicle breakdowns between others.


In the Intelligent Systems Laboratory, at the Nanyang Technological University, an intelligent transportation planning system (ITPS) has been developed using a heuristic solution. This solution is a combination of a constructive method realised by a blackboard system architecture with an iterative method supported by a truth-maintenance system. It comprises both traffic simulation and vehicle locomotion models and various monitoring and problem-solving strategies. In particular, dynamic vehicle assignment and routing strategies are employed to construct and deploy plans in response to changes in the traffic conditions and new passenger request. For the routing strategies include iterative deepening depth-first and A* search algorithms.

Status and results

It has been developed simulation software only. Experiments using randomly generated road networks and traffic conditions show the effectiveness of the proposed approach, as the dynamic strategy realised performs better than classic approaches in terms of average passenger service rate, waiting time, and travel time. The drawback is an unavoidable increase in computational time due to the implementation complexity of the blackboard approach.

Adaptivity and portability

For the ITPS to be scalable and thus usable in real-world applications, more efficient dynamic routing algorithms (such as iterative, real-time A* search) must be incorporated. Also, the actual implementation of the ITPS using intelligent electric vehicles will require other issues to be solved efficiently and reliably, especially the navigation and communication aspects of the system.

More information

M. Pasquier et al. Engineering Applications of Artificial Intelligence 14 (2001) 329-340

technical reports & case studies

executive summaries

scientific papers




search eunite with