Abstract:

In the paper, planning period is divided and the dynamic vehicle routing problem is partitioned into a series of static subproblems, which is solved by an improved maxmin ant system. In the maxmin ant system, routes are constructed by sequence method and parallel method for customers with clustering distribution and random distribution respectively. The value of pheromone updating is altered with the number of customers which can be selected by an ant. Due to the behavior of ant colony algorithms depends strongly on the value of parameters, multiparameters including distance heuristic factor, choice probability, level of pheromone persistence and the number of ants are selfadapted at different stages in the course of algorithm execution. Nine instances were tested with the objective to minimize total travelling distance of all routes. Compared with results obtained by other algorithms in literature, the number of used vehicles is basically the same, best solutions and the best average solutions have been found for all instances by maxmin ant system with parameter adaptation. It demonstrates the effectiveness and robustness of the algorithm in solving these problems.

Key words: intelligent transportation system;dynamic vehicle routing problem;maxmin ant system;parameter adaptation;ant colony algorithm