Effective and efficient: Large-scale dynamic city express

Publication Type:
Conference Proceeding
GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2015, 03-06-November-2015
Issue Date:
Filename Description Size
[2015 SIGSPATIAL] Effective and Efficient- Large-scale Dynamic City Express.pdfPublished version332.05 kB
Adobe PDF
Full metadata record
© 2015 ACM. City express services are in great demand in recent years. However, the current city express system is found to be unsatisfactory for both the service providers and customers. In this paper, we are the first to systematically study the large-scale dynamic city express problem. We aim to increase both the effectiveness and the efficiency of the scheduling algorithm. To improve the effectiveness, we adopt a batch assignment strategy that computes the pickup-delivery routes for a group of requests received in a short period rather than dealing with each request individually. To improve the efficiency, we design a two-level priority queue structure to reduce redundant shortest distance calculation and repeated candidate generation. We develop a simulation system and conduct extensive performance studies in the real road network of Beijing city. The experimental results demonstrate the high effectiveness and efficiency of our algorithm.
Please use this identifier to cite or link to this item: