Junichi Ochiai and Hitoshi Kanoh, University of Tsukuba, Japan

This paper presents a solution to real-world delivery problems for home delivery services where a large number of roads exist in cities and the traffic on the roads rapidly changes with time. The methodology for finding the shortest-travel-time tour includes a hybrid meta-heuristic that combines ant colony optimization with Dijkstra’s algorithm, a search technique that uses both real-time traffic and predicted traffic, and a way to use a real-world road map and measured traffic in Japan. Experimental results using a map of central Tokyo and historical traffic data indicate that the proposed method can find a better solution than conventional methods.

Ant Colony Optimization, Dijkstra’s Algorithm, Delivery Problem, Traffic, Real-World