On Efficient Passenger Assignment for Group Transportation

详细信息    查看全文

• 作者：Jiajie Xu (17) (21)
  Guanfeng Liu (17) (21)
  Kai Zheng (18)
  Chengfei Liu (19)
  Haoming Guo (20)
  Zhiming Ding (20)
  
  17. Department of Computer Science and Technology ; Soochow University ; Suzhou ; China
  21. Collaborative Innovation Center of Novel Software Technology and Industrialization ; Nanjing ; China
  18. School of Information Technology and Electrical Engineering ; The University of Queensland ; Brisbane ; Australia
  19. School of Software and Electrical Engineering ; Swinburne University of Technology ; Melbourne ; Australia
  20. Institute of Software ; Chinese Academy of Sciences ; Beijing ; China
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9049
• 期：1
• 页码：226-243
• 全文大小：515 KB
• 参考文献：1. Balinski, ML, Gomory, RE (1964) A primal method for the assignment and transportation problems. Management Sci. 10: pp. 578-593 287/mnsc.10.3.578" target="_blank" title="It opens in new window">CrossRef
  2. Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proceedings of VLDB, pp. 853鈥?64 (2005)
  3. Brunsch, T., Cornelissen, K., Manthey, B., R枚glin, H.: Smoothed analysis of the successive shortest path algorithm. In: Proceedings of SODA, pp. 1180鈥?189 (2013)
  4. Dantzig, G, Ramser, J (1959) The truck dispatching problem. Management Science 6: pp. 80-91 287/mnsc.6.1.80" target="_blank" title="It opens in new window">CrossRef
  5. Desrochers, M, Jones, C, Lenstra, JK, Savelsbergh, M, Stougie, L (1999) Towards a model and algorithm management system for vehicle routing and scheduling problems. Decision Support Systems 2: pp. 109-133 236(98)00090-6" target="_blank" title="It opens in new window">CrossRef
  6. Duan, R., Su, H.-H.: A scaling algorithm for maximum weight matching in bipartite graphs. In: Proceedings of SODA, pp. 1413鈥?424 (2012)
  7. Geisberger, R, Sanders, P, Schultes, D, Delling, D Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, CC eds. (2008) Experimental Algorithms. Springer, Heidelberg, pp. 319-333 2-4_24" target="_blank" title="It opens in new window">CrossRef
  8. Matijevic, D., Sanders, P., Bast, H., Funke, S., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Proceedings of ALENEX (2007)
  9. Kaul, M, Wong, RC-W, Yang, B, Jensen, CS (2013) Finding shortest paths on terrains by killing two birds with one stone. PVLDB 7: pp. 73-84
  10. Kuhn, HW (1955) The hungarian method for the assignment problem. Naval Research Logistics Quarterly 2: pp. 83-97 2/nav.3800020109" target="_blank" title="It opens in new window">CrossRef
  11. Liu, K., Li, Y., He, F., Xu, J., Ding, Z.: Effective map-matching on the most simplified road network. In: Proceedings of ACM SIGSPATIAL GIS, pp. 609鈥?12 (2012)
  12. Ma, S., Zheng, Y., Wolfson, O.: T-share: A large-scale dynamic taxi ridesharing service. In: Proceedings of ICDE, pp. 410鈥?21 (2013)
  13. Munkres, J (1957) Algorithms for the assignment and transportation problems. J. Soc. Indust. Appl. Math. 5: pp. 32-38 CrossRef
  14. Pournajaf, L., Xiong, L., Sunderam, V.S., Goryczka, S.: Spatial task assignment for crowd sensing with cloaked locations. In: Proceedings of MDM, pp. 73鈥?2 (2014)
  15. Sanders, P, Schultes, D Engineering highway hierarchies. In: Azar, Y, Erlebach, T eds. (2006) Algorithms 鈥?ESA 2006. Springer, Heidelberg, pp. 804-816 CrossRef
  16. Sankaranarayanan, J, Samet, H (2010) Query processing using distance oracles for spatial networks. IEEE TKDE 22: pp. 1158-1175
  17. U, LH, Mouratidis, K, Mamoulis, N (2010) Continuous spatial assignment of moving users. VLDBJ 19: pp. 141-160 CrossRef
  18. U, L.H., Yiu, M.L., Mouratidis, K., Mamoulis, N.: Capacity constrained assignment in spatial databases. In: Proceedings of SIGMOD, pp. 15鈥?8 (2008)
  19. U, LH, Yiu, ML, Mouratidis, K, Mamoulis, N (2010) Optimal matching between spatial datasets under capacity constraints. ACM TODS 35: pp. 1-43 CrossRef
  20. Wong, R.C.-W., Tao, Y., Fu, A.W.-C., Xiao, X.: On efficient spatial matching. In: Proceedings of VLDB, pp. 579鈥?90 (2007)
  
• 作者单位：Database Systems for Advanced Applications
• 丛书名：978-3-319-18119-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

With the increasing popularity of LBS services, spatial assignment has become an important problem nowadays. Nevertheless most existing works use Euclidean distance as the measurement of spatial proximity. In this paper, we investigate a variant of spatial assignment problem with road networks as the underlying space. Given a set of passengers and a set of vehicles, where each vehicle waits for the arrival of all passengers assigned to it, and then carries them to the same destination, our goal is to find an assignment from passengers to vehicles such that all passengers can arrive at earliest together. Such a passenger assignment problem has various applications in real life. However, finding the optimal assignment efficiently is challenging due to high computational cost in the fastest path search and combinatorial nature of capacity constrained assignment. In this paper, we first propose two exact solutions to find the optimal results, and then an approximate solution to achieve higher efficiency by trading off a little accuracy. Finally, performances of all proposed algorithms are evaluated on a real dataset.