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