Siyuan Zhang
Yu Zheng
ABSTRACT
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.
- O. Bräysy and M. Gendreau. Vehicle routing problem with time windows, part i: Route construction and local search algorithms. Transportation science, 39(1), 2005. Google Scholar
Digital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3. ed). MIT Press, 2009. Google ScholarDigital Library
- M. Gendreau, F. Guertin, J.-Y. Potvin, and E. Taillard. Parallel tabu search for real-time vehicle routing and dispatching. Transportation science, 33(4), 1999. Google ScholarDigital Library
- V. Pillac, M. Gendreau, C. Guéret, and A. L. Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 2013.Google Scholar
- S. M. Ross et al. Stochastic processes, volume 2. John Wiley & Sons New York, 1996.Google Scholar
- M. M. Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 1987. Google ScholarDigital Library
- Y. Zheng, L. Capra, O. Wolfson, and H. Yang. Urban computing: concepts, methodologies, and applications. ACM Transactions on Intelligent Systems and Technology, 5(3):38--55, 2014. Google ScholarDigital Library
Index Terms
- Effective and efficient: large-scale dynamic city express
Recommendations
Efficient and Effective Express via Contextual Cooperative Reinforcement Learning
KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningExpress systems are widely deployed in many major cities. Couriers in an express system load parcels at transit station and deliver them to customers. Meanwhile, they also try to serve the pick-up requests which come stochastically in real time during ...
Effective and Efficient: Large-Scale Dynamic City Express
Due to the large number of requirements for city express services in recent years, 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 ...
A Queueing Model without Customer Waiting Applied in Flexible Production Line to Optimize the Number of Servers
ICIII '11: Proceedings of the 2011 International Conference on Information Management, Innovation Management and Industrial Engineering - Volume 01The queueing model of Poisson arrival process, general distribution service process and infinite servers can be applied in the stochastic service system how many servers do we need to ensure the customers scarcely have to wait in queue. According to the ...
Comments