N. Mukai, J. Feng, and T. Watanabe (Japan)
Demand-Bus, VRTPR-Tree, Dynamic Vehicle RoutingProblem (DVRP)
Dynamic Vehicle Routing Problem (DVRP) is a prob lem which models a new transportation system called a demand-bus system. As in DVRP delivery demands of cus tomers occur continuously in real time, share-ride vehicles must transport all of them to their destinations as early as possible and reduce their traveling costs as much as possi ble. Traditional methods using heuristic algorithms could not solve the problem effectively in such a time-varying en vironment because of their time complexities. Therefore, we propose Vehicle Routing TPR-Tree which is a spatial index structure for moving vehicles on DVRP. Entries in leaf nodes consist of a pointer to a vehicle and a bounding rectangle called VRCBR which implies the future position of the vehicle on the basis of a road network. By using the spatial indexes, customers are assigned to vehicles effec tively. Moreover, we propose two scheduling algorithms based on first-in first-out (FIFO) or traveling time measure (TTM) for delivery orders of customers. At last, we show with experiments that this problem can be efficiently solved by using our approach.
Important Links:
Go Back
