人工生命的アプローチによる集配送計画問題の解法

Abstract

This paper proposes a new method for multi-vehicle routing problems (MVRP). MVRP is to determine the optimal routes for all vehicles through the minimal total tour length subject to vehicle capacity constraints and other restrictions. All nodes have some packages to deliver to other nodes before vehicles start. Each time a vehicle arrives at a node, it drops off packages and picks up others. Vehicles go on moving until all packages in the area are completely delivered. The aim of this paper is to indicate that MVRP can be solved by artificial life, which is a methodology of the modern heuristics such as genetic algorithms, tabu search or simulated annealing. The proposed approach is basis on a point of view that a vehicle can be regarded as an artificial life. For instance, picking up goods is corresponded to the act of predatory, and dropping off ones to the act of excretory. The method makes use of three indicators to characterize the artificial life. First is a moving length, second is a loading tendency, and last is a standing by at the same node. Each indicator takes one integer value among zero to 99. If the value of moving length indicator is relatively small, then it means that the vehicle tends to prefer a short-distance movement to a long-distance. Other two indicators can be made similarly interpretation.