关键词: 车辆路径问题, 自行车再平衡问题, 人工免疫, 克隆选择, 抗体相似性

Abstract:

Bicycle repositioning is a key point to the operating efficiency and customer service levels in city public bike system. In this paper, on the basis of existing research, the artificial immune clone selection algorithm for BRP is proposed, which uses multidimensional integer coding method, designs a new method of antibody similarity measure method and suppression strategies based on the problem characteristics, and the secondary response solving mechanism is also integrated into algorithm framework. Using benchmark problems test shows that, in the firstly response test, this algorithm can find all optimal solution in the small size problems（n<50）, but the average CPU consumption is 96.80% faster than the exact algorithm, and the solution average quality is 7.43% lower than the exact algorithm in the middle size problems（50<n<100）, which is same to the genetic algorithm, but the average CPU consumption is 96.8% faster than the exact algorithm. In the secondary response test, the solution quality is better than the first response slightly, CPU consumption is faster than the first response by more than 39%.

Key words: vehicle routing problem, bike sharing rebalancing problem, artificial immune, clonal selection, antibody similarity