A Unified Approach to Route Planning for Shared mobility Yongxin Tong1, Yuxiang Zeng 2, Zimu Zhou 3 Lei chen 2, Jieping Ye 4, Ke xu 1 Beihang University The Hong Kong University of Science and Technology 3 ETH Zurich 4 Didi Research Institute
A Unified Approach to Route Planning for Shared Mobility Yongxin Tong 1 , Yuxiang Zeng 2 , Zimu Zhou 3 , Lei Chen 2 , Jieping Ye 4 , Ke Xu 1 1 Beihang University 2 The Hong Kong University of Science and Technology 3 ETH Zurich 4 Didi Research Institute
Outline o Background and Motivation ● Problem statement ° Our so| utions ● EXperiments Conclusions
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusions 2
Background: Shared Mobility Shared mobility: transportation services that are shared among users o ride sharing, city express, food delivery Ride sharing City Express Food Delivery DIdIeR ST)EXPRESS 顺丰速运 美团 meitan. com seamless Corporation ∪BER
Background: Shared Mobility ⚫ Shared mobility: transportation services that are shared among users. ⚫ ride sharing, city express, food delivery 3 Ride Sharing
Background: Route Planning Route Planning for Shared Mobility(RPSM) o start from orgin, travel 2n location o pickup location the origin of the passenger delivery location: the destination of the passenger e Constraint: first picked up and then delivered icky location delivery location Paris 3e 3 3 2
Background: Route Planning ⚫ Route Planning for Shared Mobility (RPSM) ⚫ start from orgin, travel 2n location ⚫ pickup location: the origin of the passenger ⚫ delivery location: the destination of the passenger ⚫ Constraint: first picked up and then delivered 4 pickup location delivery location 1 1 2 2 3 3
Existing Work ● Disadvantage1: target on only one goal, even conflict goal o e.g., minimizing total distance while trying to serve all requests [ICDE 13, VLDB14 o In another word, not all requests need to be served o That is to say, optimal result is 0, i.e., we do not serve any requests
Existing Work ⚫ Disadvantage 1: ⚫ target on only one goal, even conflict goal o e.g., minimizing total distance while trying to serve all requests [ICDE’13, VLDB’14] o In another word, not all requests need to be served o That is to say, optimal result is 0, i.e., we do not serve any requests 5
6 Existing work ● Disadvantage2 rely on core operation Insertion with O(n)or o(n)time Drop D old route Pick D Drop"Drop new order PickA Drop a Pick bc Insertion Drop D old route Pick D Drop B new route PickA Drop a Drop c Pick Bc
Existing work ⚫ Disadvantage 2: ⚫ rely on core operation: Insertion with O 𝑛 2 or O 𝑛 3 time 6 Pick A Drop A Pick BC Drop B Drop C Pick D Drop D Pick A Drop A Pick BC Drop B Drop C Pick D Drop D old route new order old route new route Insertion
Motivation We propose a unified cost function, which generalizes three main objectives 6552 ￡ Served■ Rejected i. Total Travel Distance. Number of served requests Total revenue
Motivation ⚫ We propose a unified cost function, which generalizes three main objectives 7 Total Travel Distance Number of served requests Total Revenue Served Rejected
Outline e background and motivation ● Problem statement ° Our so| utions ● EXperiments Conclusions
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusions 8
Problem statement: road network Road network undirected graph G =(V,E) V: a vertex set E: an edge set cost(u, v): travel cost between two vertices latitude and longtitude of the vertex (2)56(65) U5(84) n(01)5 59(52) v2(0,2) 24(10,2) u3(30)
Problem Statement: Road Network ⚫ Road network: undirected graph 𝐺 = (𝑉, 𝐸) ⚫ V： a vertex set ⚫ E: an edge set ⚫ cost(u, v)： travel cost between two vertices 9 latitude and longtitude of the vertex 𝑣2(0,2) 𝑣7(2,4) 𝑣3(3,0) 𝑣8(5,2) 𝑣6(6,5) 𝑣4(10,2) 𝑣5(8,4) 5 5 7 8 4 5 5 3 3 5 𝑣1 (0,1) 1
Problem statement: Worker ● Worker:W=(o,Kn initial location Kw: capacity W=(17 7,4) v(24)526(6 (84) n(01)5 59(52) v2(0,2) 24(10,2) u3(30)
Problem Statement: Worker ⚫ Worker: 𝑤 = 𝑜𝑤,𝐾𝑤 ⚫ 𝑜𝑤: initial location ⚫ 𝐾𝑤: capacity 10 𝒘 = 𝒗𝟕 ,𝟒 ! " # ! $ ' &" ! ( ' ! ( % ! " % ! $ 𝑤 % 𝑣2(0,2) 𝑣7(2,4) 𝑣3(3,0) 𝑣8(5,2) 𝑣6(6,5) 𝑣4(10,2) 𝑣5(8,4) 5 5 7 8 4 5 5 3 3 5 𝑣1 (0,1) 1
