Route ● Route:SR=(lo,l1,…,ln) o R: a set of requests o lo: the current location of worker o li: either origin or destination of r in R 2 (88) 4.5 57 0w/(24) 6→④ a+1(04) 0r1(44) 2 3 (10,2) 2 Feasible: (1) Capacity constraint;(2) Deadline constraint
Route ⚫ Route： S𝑅 = 𝑙0,𝑙1, ⋯ , 𝑙𝑛 ⚫ 𝑅: a set of requests ⚫ 𝑙0: the current location of worker ⚫ 𝑙𝑖 : either origin or destination of 𝑟 in 𝑅 11 1 3 2 6 𝒚 𝒙 4 5 𝒐𝒘(2,4) 𝒐𝒓𝟐 (8,8) 𝒅𝒓𝟏 (10,4) 𝒅𝒓𝟐 (4,0) 𝒐𝒓𝟏 (4,4) 𝒐𝒓𝟑 (10,2) 𝒅𝒓𝟑 (10,0) 5.7 2 4.5 6 2 2 Feasible: (1) Capacity constraint; (2) Deadline constraint
Problem formulation ● nsertion Operator ● Given o Worker w, feasible original route sr, new request r Goal o Inserts r' into sr to obtain a new feasible route with I Minimizing maximum flow time of all requests: I Focus of i. e, minimizing maximum waiting time of all This talk, requests (waiting time = delivery time-release r time) Minimizing total travel time of the worker, i.e the delivery time of the last request for the worker
Problem Formulation ⚫ Insertion Operator ⚫ Given: o Worker 𝑤, feasible original route 𝑆𝑅, new request 𝑟′ ⚫ Goal: o Inserts 𝑟′ into 𝑆𝑅 to obtain a new feasible route with: ▪ Minimizing maximum flow time of all requests: i.e., minimizing maximum waiting time of all requests (waiting time = delivery time - release time) ▪ Minimizing total travel time of the worker, i.e., the delivery time of the last request for the worker 12 Focus of This talk
Example new request 4.5 original route W T 1 20 1 473 6 2 3 1 25 44)(10,4 0000 37 (88)(4,0) 2 3 33(10,2)(10,0)1 26 (46)(6,2)
Example 13 𝒕𝒓 𝒆𝒓 𝒐𝒓 𝒅𝒓 𝒄𝒓 𝒓𝟏 0 25 (4,4) (10,4) 1 𝒓𝟐 0 37 (8,8) (4,0) 2 𝒓𝟑 0 33 (10,2) (10,0) 1 𝒓′ 0 26 (4,6) (6,2) 1 1 3 2 6 𝒚 𝒙 4 5 𝒐𝒘 𝒐𝒓 ′ 𝒅𝒓 ′ 5.7 2 4.5 6 2 2 new request 𝒐𝒓𝟐 𝒅𝒓𝟏 𝒅𝒓𝟐 𝒐𝒓𝟏 𝒐𝒓𝟑 𝒅𝒓𝟑 original route
Example 4.5 new route W 2.8 T 1 0 1 3 4.5 2.8 2 3 1 25 44)(10,4 3 0000 37 (88)(4,0) 2 33(10,2)(10,0)1 26 (46)(6,2)
Example 14 𝒕𝒓 𝒆𝒓 𝒐𝒓 𝒅𝒓 𝒄𝒓 𝒓𝟏 0 25 (4,4) (10,4) 1 𝒓𝟐 0 37 (8,8) (4,0) 2 𝒓𝟑 0 33 (10,2) (10,0) 1 𝒓′ 0 26 (4,6) (6,2) 1 𝒚 𝒙 𝒐𝒘 5.7 4.5 2 2 2.8 2.8 4.5 2 new route 1 3 2 6 4 5 𝒐𝒓𝟐 𝒅𝒓𝟏 𝒅𝒓𝟐 𝒐𝒓𝟏 𝒐𝒓𝟑 𝒅𝒓𝟑 𝒐𝒓 ′ 𝒅𝒓 ′
15 Problem Time complexity: o(n) Calculate objective and check constraints in o(n) Enumerate all possible insertion pairs in o(n) Basic Algorithm
Problem 15 Enumerate all possible insertion pairs in 𝑂 ( 𝑛 2 ) Calculate objective and check constraints in 𝑂 ( 𝑛 ) Time complexity:𝑂 ( 𝑛 3 ) Basic Algorithm ×=