Hybrid Ant Colony Optimization Algorithm for Solving the Open Vehicle Routing Problem

Bin Ge ； Yue Han ； Chen Bian

《電腦學刊》 27卷4期 (2016/12) Pp. 41-54

https://doi.org/10.3966/199115592016122704004

摘要

Open vehicle routing problem (OVRP) is a hot research topic in modern operational research, compared with classical VRP problems, one of its marked characteristics is that the vehicle can choose the other distribution center as an end after the completion of the transportation service. The solving goal of OVRP is to build a Hamiltonian path to meet the needs of all customers. In order to solve the OVRP, a hybrid ant colony optimization (HACO) algorithm based on random distribution of loading and dynamically encoding was proposed. Firstly, the initial solutions were obtained through the method of random loading, and the colony optimization algorithm was adopted to get the optimal solution. Then the optimal solution was encoded as the zeroth particle of particle swarm algorithm. The initial fitness values were regarded as the historical optimal solution for individual. In order to get the best historical of individual and global optimal solution, the global optimal solution and the switching sequence of each particle was calculated and implemented, combining the hill climbing strategy for local search with side step. Computer simulations on the benchmark problems show that it can quickly and effectively get the known optimal solution or approximate solution.

關鍵字

ant colony optimization algorithm ； dynamic coding ； open vehicle routing problem ； particle exchange sequence ； random stowage