Consider an ultimately flexible on-demand transit system. Buses are dispatched to pick up passengers anywhere and transport them anywhere.
The bus can take any route in between, including picking up other passengers under the following constraint: the distance traveled between origin and destination for any passenger is no longer than F times the shortest path between them, where F is a fixed factor, say F=2.
A more sophisticated way constrains time: the time it takes (including waiting) must not exceed the some factor F multiplying the time of an immediate car trip.
Perhaps F*t+C.
Consider a service area of a completely paved disc (no need to follow roads), with passengers' origins and destinations occurring uniformly randomly within it over time. Devise an on-line scheduling algorithm that does probabilistically well (servicing as many passengers as possible).
Permit transfers.
Permit more sophisticated scheduling: Instead of "I need a bus now", also permit, "I will need a bus at a time T."
I imagine the reason this doesn't exist yet is because this kind of scheduling is computationally difficult.
No comments :
Post a Comment