Tomorrow we have a meeting with Dr. Randy LeVeque, UW Applied Math legend/Professor, and Wednesday he's leading the "Reproducibility Workshop" where we're spending a lot of time on file organization via Git - maybe I'll finally start climbing up this Git learning curve.
Last Friday, July 10th, we had a meeting with Matthew, our primary contact at King County Metro Access operations. Fortunately, our interpretation of the optimization problem was correct. The situation is still this: given an unscheduled request (or set of unscheduled requests), find the most appropriate run on which we can squeeze the new passenger. Compare the additional cost/damage to current schedule to the cost of sending a DEB (dispatched extra boarding?) bus out, or fulfill the ride with a taxi (given the passenger can even ride in a taxi).
We've done a decent amount of literature review (shout-out to Dr. Carl Henrik Hall for his 2013 paper "Improving Paratransit Scheduling Using Ruin and Recreate Methods" being the most relevant paper to our problem thus far). The best method for inserting unscheduled requests is simply called "best insertion," and it's mentioned in Hall's aforementioned paper:
Lol. Deceptive use of the word "simply," eh?
It's just a brute-force algorithm, where you test Y/N "can this new passenger fit on bus K between nodes i and j given everyone's time window constraints and the Access bus's capacity constraints (12 ambulatory spots or 3 wheelchairs)?"
On a regular weekday, the peak number of Access bus routes in operation is ~250. If a bus breaks down at a peak ridership time, are we going to test the insertion of b stranded passengers onto 250 routes? Well, hopefully not. My job for tomorrow is to write a reasonable distance cut-off function that will tell us which buses are simply too far away to be able to service the stranded passengers by the end of each passenger's acceptable pick-up or drop-off window.
Over all, we're planning on using the OSRM (Open Street Routing Machine) API to obtain the estimated travel time to leave normally-scheduled node i, arrive at unscheduled request node h, and make it back to normally-scheduled node j by the end of j's time window. If this is the case, then it's feasible to pick up unscheduled request at node h. We'll get a list of these feasible pick-up routes. The next question obviously becomes whether or not we can also feasibly drop off the unscheduled request at their drop-off location without breaking subsequent time windows. One of my top priorities is to minimize the number of API requests our solution will have to make, querying travel times between points. I think I've got a good methodology...
Iterating over all of the unscheduled requests, we'll get a list of wholly feasible bus routes that can accommodate each unscheduled request, and then we'll have to rank each feasible re-route. The ranking might get tricky, because technically all feasible routes will only extend each original bus route schedule by 2(time-window-size)-minutes, assuming that no passenger's time window constraints are broken. But, I anticipate that we might have to change our methodology to let feasible re-routes break time window constraints, in which case the ranking criterion would obviously rank feasible re-route according to who misses the fewest passenger's time windows, and by how much those windows are missed.
Then, there's the whole question of how to put this application into a feasible package... Django anyone?
No comments:
Post a Comment