융합 유전자 알고리즘 기반의 공공자전거 재배치 방안에 관한 연구

Abstract

더욱 합리적이고 인간적인 공공자전거 서비스를 제공하기 위해서 공공자전거가 시스템 더 효율적으로 운영되고 서비스 이용자 만족도를 높이도록 한 가지 자전거 재배치 경로 최적화 목적으로 공공자전거 재배치 최적화 모델을 제시하였다. 기존 재배치 모델들의 속도 느림, 정확도 낮음 등 한계점을 개선하기 위해서, 본 논문에서 GA와 ACO 알고리즘을 조합돼서 GAACO-BSP(a Genetic Hybrid Ant Colony Optimization Algorithm for Solving Bike-sharing Scheduling Problem) 알고리즘을 개발하였다. 그리고 성능 향상시키기 위하여 GA 수행횟수 제어 함수를 수립하여 두 알고리즘을 동적으로 연결하였다. 우선 GA가 스케줄링 가능한 초기해를 구하고, 그 다음으로 GA 수행횟수 제어 함수를 통해 최적 전환 시기를 파악해서 동적으로 ACO으로 전환한다. ACO가 GA에게서 초기화 필요한 페로몬을 얻고 최종 최적해를 찾는 것이다. 서울시 공공자전거 따릉이 사례로 결과를 검증하여, GAACO-BSP은 전통 단일 알고리즘보다 뛰어난 성능 우세로 대규모 자전거 시스템에 적용하고 더 짧은 시간 만에 재배치 거리를 더 많이 줄였다. 실험을 통해 GAACO-BSP가 실제 도시 공공자전거 시스템에서 적용할 수 있다는 것을 알 수 있다.

To improve the service efficiency and customer satisfaction degree of public bicycle, a bike-sharing scheduling model is proposed, which aims to get the shortest length of the bicycle scheduling. To address the slow solution speed of the existing algorithms, which is not conducive to real-time scheduling optimization, this paper designed a Genetic Hybrid Ant Colony System Algorithm for Solving Bike-sharing Scheduling Problem (GAACS-BSP). Genetic algorithm was used to search initial feasible scheme， which was used to initialize pheromone distribution of ant colony algorithm. It solved problem of lack initial pheromone, to improve the efficiency of bike-sharing scheduling tasks. There also proposed a genetic algorithm control function to control the appropriate combination opportunity of the two algorithms. Finally, the results show that compared with GA or ACS, it is more suitable for solving the problem of large-scale bike-sharing scheduling tasks, which shortens the scheduling distance in a short period.