Two-sided online bipartite matching in spatial data: experiments and analysis

With the rapid development of sharing economy and mobile Internet in recent years, a wide range of applications of the T wo-sided O nline B ipartite M atching (TOBM) problem in spatial data are gaining increasing popularity. To be specific, given a group of workers and tasks that dynamically appear...

Full description

Saved in:
Bibliographic Details
Published in:GeoInformatica 2020, Vol.24 (1), p.175-198
Main Authors: Li, Yiming, Fang, Jingzhi, Zeng, Yuxiang, Maag, Balz, Tong, Yongxin, Zhang, Lingyu
Format: Article
Language:English
Subjects:
Algorithms
Beliefs, opinions and attitudes
Comparative analysis
Computer Science
Data Structures and Information Theory
Earth and Environmental Science
Economic development
Employees
Geographical Information Systems/Cartography
Geography
Geospatial data
Information Storage and Retrieval
Matching
Multimedia Information Systems
Sharing economy
Spatial analysis
Spatial data
Workers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the rapid development of sharing economy and mobile Internet in recent years, a wide range of applications of the T wo-sided O nline B ipartite M atching (TOBM) problem in spatial data are gaining increasing popularity. To be specific, given a group of workers and tasks that dynamically appear in a 2D space, the TOBM problem aims to find a matching with the maximum cardinality between workers and tasks satisfying the spatiotemporal constraints. Many works have studied this problem, but the settings of their problems are different from each other. Moreover, no prior works have compared the performances of the algorithms tailored for different settings under a unified definition. As a result, there lacks a guideline for practitioners to adopt appropriate algorithms for various scenarios. To fill the blank in this field, we present a comprehensive evaluation and analysis of the representative algorithms for the TOBM problem in this paper. We first give our unified definition and then provide uniform implementations for all the algorithms. Finally, based on the experimental results on both synthetic and real datasets, we discuss the strengths and weaknesses of the algorithms in terms of short-term effect and long-term effect, which can be guidance on selecting appropriate solutions or designing new methods.
ISSN:1384-6175
1573-7624
DOI:10.1007/s10707-019-00359-w