ANT COLONY SYSTEM BASED APPROACHES TO THE AIR-EXPRESS COURIER'S ROUTING PROBLEM

概要

論文の詳細を見る
This paper proposes two ant colony system (ACS) based approaches, called stepwise-ACS (SACS) and cheapest-insertion-stepwise-ACS (CISACS), to solve the air-express courier's routing problem. The courier visits N predetermined delivery points and M pickup requests during the en route delivery. The SACS performs an ACS to obtain the initial tour for the N delivery points and then to find the shortest Hamiltonian path, in a stepwise manner, when the M requests arrive. The CISACS, following the SACS, incorporates the cheapest insertion into the SACS as new requests become known. Experiments with various pickup emergence patterns that characterize the real-world circumstances are tested for the proposed algorithms. The computational results, in terms of total traveled distance, are compared with the baseline results by a cheapest insertion (CI) heuristic. The results show that both SACS and CISACS perform better than the CI heuristic and that CISACS yields the lowest traveled distance.
Eastern Asia Society for Transportation Studiesの論文