{"id":163766,"date":"2013-04-01T00:00:00","date_gmt":"2013-04-01T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/t-share-a-large-scale-dynamic-taxi-ridesharing-service\/"},"modified":"2018-10-16T19:59:47","modified_gmt":"2018-10-17T02:59:47","slug":"t-share-a-large-scale-dynamic-taxi-ridesharing-service","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/t-share-a-large-scale-dynamic-taxi-ridesharing-service\/","title":{"rendered":"T-Share: A Large-Scale Dynamic Taxi Ridesharing Service"},"content":{"rendered":"<div class=\"asset-content\">\n<p>By encouraging passengers to share taxi trips, taxi ridesharing is of significant social and environmental benefit, such as saving energy consumption and satisfying people\u2019s commute in peak hours. Despite the great potential, the taxi ridesharing, especially with dynamic queries, is not well studied. In this paper, we formally define the dynamic ridesharing problem and present a large-scale taxi ridesharing service, which efficiently serves real-time requests sent by taxi users and generates ridesharing schedules that reduce the total travel distance significantly. In our method, we first propose a taxi searching algorithm using a spatio-temporal index to quickly retrieve candidate taxies that could satisfy a user query. A schedule allocation algorithm is then proposed to check each candidate taxi so as to insert the user\u2019s trip into the schedule of the taxi which satisfies the query with minimum incurred travel distance for the ridesharing. To tackle the heavy computational load, a lazy shortest path calculation strategy is devised to speed up this schedule allocation algorithm. We evaluated our service with a GPS trajectory dataset generated by over 33,000 taxies during a period of 3 months. By learning the spatio-temporal distributions and the stochastic process of real user queries from this dataset, we built an experimental platform that can simulate user behaviours in taking a taxi in the real-world. Tested on this platform with extensive experiments, our approach demonstrates its efficiency, effectiveness, and scalability. For example, our proposed service can serve 40% additional taxi users while saving 15% travel distance over no ridesharing (when the ratio between the number of queries and the number of taxies is 5).<\/p>\n<\/div>\n<p><span id=\"460e5776-aac9-40c0-b1a1-3a2733e61636\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Image460e5776-aac9-40c0-b1a1-3a2733e61636\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/urbancomputing-tshare.jpg\" alt=\"\" \/><span id=\"ImageCaption460e5776-aac9-40c0-b1a1-3a2733e61636\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span><\/p>\n<p>\uff08<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" target=\"_blank\" href=\"https:\/\/www.cs.uic.edu\/~sma\/ridesharing\/\">Code<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>\uff09(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/t-drive-trajectory-data-sample\/\">Data<\/a>)<\/p>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>By encouraging passengers to share taxi trips, taxi ridesharing is of significant social and environmental benefit, such as saving energy consumption and satisfying people\u2019s commute in peak hours. Despite the great potential, the taxi ridesharing, especially with dynamic queries, is not well studied. In this paper, we formally define the dynamic ridesharing problem and present [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"ICDE 2013","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"Proceedings of The 29th IEEE International Conference on Data Engineering","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"Proceedings of The 29th IEEE International Conference on Data Engineering","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"Shuo Ma, Ouri Wolfson","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2013-04-01","msr_highlight_text":"","msr_notes":"The Best Paper Runner-Up Award","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2013,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13563],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-163766","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-data-platform-analytics","msr-locale-en_us"],"msr_publishername":"ICDE 2013","msr_edition":"Proceedings of The 29th IEEE International Conference on Data Engineering","msr_affiliation":"","msr_published_date":"2013-04-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"The Best Paper Runner-Up Award","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"205523","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"ICDE13_conf_camera-ready_clean.pdf","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/ICDE13_conf_camera-ready_clean.pdf","id":205523,"label_id":0},{"type":"file","title":"Ridesharing-ICDE2013.pptx","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/Ridesharing-ICDE2013.pptx","id":205524,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":205524,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/Ridesharing-ICDE2013.pptx"},{"id":205523,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/ICDE13_conf_camera-ready_clean.pdf"}],"msr-author-ordering":[{"type":"text","value":"Shuo Ma","user_id":0,"rest_url":false},{"type":"user_nicename","value":"yuzheng","user_id":35088,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=yuzheng"},{"type":"text","value":"Ouri Wolfson","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[170824],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":170824,"post_title":"Urban Computing","post_name":"urban-computing","post_type":"msr-project","post_date":"2016-07-03 10:26:01","post_modified":"2018-04-07 17:32:40","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/urban-computing\/","post_excerpt":"Concept\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (\u4e2d\u6587\u4e3b\u9875) Urban computing is a process of acquisition, integration, and analysis of big and heterogeneous data generated by a diversity of sources in urban spaces, such as sensors, devices, vehicles, buildings, and human, to tackle the major issues that cities face, e.g. air pollution, increased energy consumption and traffic congestion. Urban computing connects unobtrusive and ubiquitous sensing technologies, advanced data management and analytics models, and novel visualization methods, to create win-win-win solutions that improve&hellip;","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170824"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163766","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163766\/revisions"}],"predecessor-version":[{"id":517400,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163766\/revisions\/517400"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=163766"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=163766"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=163766"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=163766"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=163766"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=163766"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=163766"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=163766"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=163766"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=163766"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=163766"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=163766"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=163766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}