Detecting arbitrarily shaped clusters in origin-destination flows using ant colony optimization

ABSTRACT

An origin-destination (OD) flow can be defined as the movement of objects between two locations. These movements must be determined for a range of purposes, and strong interactions can be visually represented via clustering of OD flows. Identification of such clusters may be useful in urban planning, traffic planning and logistics management research. However, few methods can identify arbitrarily shaped flow clusters. Here, we present a spatial scan statistical approach based on ant colony optimization (ACO) for detecting arbitrarily shaped clusters of OD flows (AntScan_flow). In this study, an OD flow cluster is defined as a regional pair with significant log likelihood ratio (LLR), and the ACO is employed to detect the clusters with maximum LLRs in the search space. Simulation experiments based on AntScan_flow and SaTScan_flow show that AntScan_flow yields better performance based on accuracy but requires a large computational demand. Finally, a case study of the morning commuting flows of Beijing residents was conducted. The AntScan_flow results show that the regions associated with moderate- and long-distance commuting OD flow clusters are highly consistent with subway lines and highways in the city. Additionally, the regions of short-distance commuting OD flow clusters are more likely to exhibit ‘residential-area to work-area’ patterns.

KEYWORDS:

• Origin-destination flow
• spatial local statistics
• spatial scan statistics
• ant colony optimization

Acknowledgments

The authors gratefully acknowledge the comments from the editor and the reviewers.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. For SC3 and AC7, both clusters include flows between Yidongyuan and the Wanquanhe Bridge. For destination areas differing from Suzhou St. (identified by SaTScan_flow), AntScan_flow has identified Peking University instead. Although Suzhou St. is a famous business area and workplace, more flows of people occur from Yidongyuan to Peking University (561 during the morning and 2217 during the day to Peking University versus 238 during the morning and 1060 during the day to Suzhou St.). These trips are mainly attributed to the students of Peking University who live in Yidongyuan.

Additional information

Funding

This study was funded through support from National Natural Science Foundation of China (Grant Nos. 41421001, 41525004, 41601430), and Key Research Program of Frontier Science, Chinese Academy of Sciences (Grant No. QYZDY-SSW-DQC007).

Notes on contributors

Tao Pei

Tao Pei Ci Song designed the study, performed the ACO-algorithm and experiment and drafted the manuscript. Tao Pei conceived of the study, and participated in its design and conduct to draft the manuscript. Ting Ma participated in the statistical analysis and Monte-Carlo simulation. Yunyan Du contributed to the design of simulated OD flow clusters and the comparison of experiments. Hua Shu and Sihui Guo participated in investigation of study region and result analyses. Zide Fan preprocessed the mobile phone data and extracted the daily commute OD flows. All authors read and approved the final manuscript.