Solving vehicle scheduling problem on dataflow architecture

This paper explores the use of dataflow computation in the implementation of a parallel search algorithms for Vehicle Scheduling Problem (VSP). The VSP is concerned with finding optimal routes for a fleet of vehicles, each with a fixed capacity, which deliver goods from a depot to a number of customers located at different cities and having known demand of some commodity. The objective is to flnd optimal schedule for each vehicle. This problem is to find optimal schedule for each vehicle. This problem is ideally suited for dataflow computation. The nodes (location of customers) and their interconnections is viewed as dataflow graph where the asynchronous propagation of tokens along the arcs are used to perfrom parallel search in order to find optimal path. The implementation of the algorithm is studied on a simulated model of token storage type of dataflow architecture. The performance of the model for networks with 6, 9 and 10 nodes is evaluated.