Imperfect Classifications

As I think has become increasingly obvious by my topic choice, I believe one of the biggest flaws many OR models have when dealing with emergencies is a lack of clear information.  Some models treat the problem stochastically, which adds to the complexity of the model, but hopefully improves the resulting decisions.  Others, like Rath and Gutjahr [1], which I detailed in my previous post, seeks to look at the problem through the lens of trade-offs.  Argon and Ziya [2] tackle the problem of imperfect information head on by considering how well priority assignment systems work with imperfect information, how to prioritize with imperfect ‘signals’ of severity, and what systems best handle this problem.

Argon and Ziya look at a queuing system with different priorities of patients.  The specific instance that we will consider is that of an EMS dispatch system.  Patients arriving to the system are either type 1 patients who need immediate treatment or type 2 patients who should wait until all type 1 patients are served.  The dispatcher, however, only receives a signal that details how likely a patient is to be type 1.  More specifically, this is not necessarily strictly a probability, since as long as the signals can be ordered such that signals from type 1 patients are larger than from type 2 in likelihood ratio ordering.  The dispatcher must use these signals to assign patients to priority levels, where higher priority levels must all be served before a lower priority level receives any service.

It is worth noting that Argon and Ziya assume penalties are linearly related to waiting time for most of paper.  In the instance where linearity holds, increasing the number of priority levels that dispatchers can assign the patients to will never result in worse outcomes, and may in fact result in better outcomes.  Following this thought to its logical conclusion, the authors argue for a Highest-Signal-First (HSF) policy which serves patients in order from most likely to be type 1 to least likely.

A more important take-away to me is that a two-priority policy achieves a majority of the improvement HSF sees of First-Come First-Serve (FCFS) while being far more practical to implement.  Better yet, when the authors investigate nonlinear wait time penalties, the two-priority policy consistently outperforms HSF and at worst performs on par with FCFS.  Unfortunately, they only look at a single nonlinear function that increases the penalty quadratically with wait time.  This is not very representative of cardiac arrest patients who suffer most of their penalty in the first minutes after their call [3].

A worthwhile extension of this research would be to consider the case where patient penalties are exponentially decaying (similar to what we expect for cardiac arrest victims) and compare two-priority and three-priority policies to FCFS.  These policies are easier to implement and are used in practice.

Further, this can be combined with historic data on the accuracy of the ‘signal’ the dispatchers receive to determine best practices for when to assign a patient to high priority based on system load.  Argon and Ziya argue that as the system load increases, we should become less discriminate in and accept more patients as high priority, but this does not seem to necessarily hold in the exponentially decaying case.  Instead, it may move toward more discrimination in labeling patients as high priority since there is only a major benefit to serving a type 1 patient if it is done so quickly.

I believe that by looking at the possibility that our information is not quite accurate, we can develop better policies that work under a variety of conditions.  Whether this means using a deterministic policy only as a guide or better yet, determining a policy that best mitigates the effects of imperfect information as above, it is better than simply ignoring the problem.

 

[1] Rath, Stefan, and Walter J. Gutjahr. “A math-heuristic for the warehouse location–routing problem in disaster relief.” Computers & Operations Research 42 (2014): 25-39.

[2] Argon, Nilay Tanik, and Serhan Ziya. “Priority assignment under imperfect information on customer type identities.” Manufacturing & Service Operations Management 11.4 (2009): 674-693.

[3] Valenzuela, Terence D., et al. “Estimating effectiveness of cardiac arrest interventions a logistic regression survival model.” Circulation 96.10 (1997): 3308-3313.

Pareto Frontier Heuristics in Humanitarian Logistics

Last time I wrote about multi-objective programming.  Today, I would like to follow up with a few more details and more generally a discussion of the practical use of it in humanitarian logistics.

In the paper, Rath and Gutjahr use a variant of the bounded objective method called the adaptive epsilon constraint method.  Unfortunately, for anything beyond a bi-objective formulation, this method becomes quite nasty and complicated.  Suffice it to say, where the epsilon constraint method chooses predetermined bounds on the constrained objective, the AECM uses knowledge of the objective space from previous solutions (We are solving for the Pareto frontier) to create better constraint values for future searches. Hence, it adapts its constraints based on new data and is able to significantly decrease the total search time over the more naïve ECM.

Using these constraints, Rath and Gutjahr then seek to find the optimal objective value by narrowing an upper and lower bounds on the solution until they achieve equality and hence optimality.  From here, the primary contribution of the paper is in developing heuristics to aid in the computation of these bounds.  In each iteration, they add new constraints to the upper bound to make a better, but more computationally intense relaxation.  Further, they use basic heuristics to find a feasible lower bound.

All this effort is with the goal of finding a faster, if not quite as accurate solution.  So the practical question then is whether this still provides a useful solution and moreover, whether it is even necessary.

I think it would be hard to argue that even an approximate answer is not reasonably acceptable where an exact answer would have been useful.  This comes simply from the assumption of perfect knowledge.  Of all the assumptions, this is probably the worst.  As Sam pointed out in class, do we even know that all of the network connections (roads) are still in place?  Even if this is accounted for, isn’t it possible that they may be restored over time making our solution suboptimal?  Further, our knowledge of demand is limited to what information we have gathered so far- information that is itself inexact.

So the ability to solve the exact solution is of little use.  We are merely looking for guidance and for that a heuristic is just fine.  In fact, I would argue that in a real aid deployment, a heuristic is perhaps more useful, being faster and more understandable to non-practitioners while producing what is arguably an equally useful solution.

The other question is whether this complicated model is even worth solving.  As was discussed last week, finding the Pareto frontier is not an insignificant problem and perhaps best avoided if we are reasonably able.  Here, I think is the crux of the matter.  At least for the problem that they are considering, I question the usefulness of the multi-objective criteria and the necessity to minimize cost and maximize service at the same time. Either the organization is working under a given budget or it can be changed based on increased donations.  In either case, it makes as much sense to solve the Pareto optimal solution for the current budget, and resolve later if necessary.  The lack of perfect information would necessitate these resolves in any case.

The only real benefit in knowing the entire Pareto Frontier is to get a good idea for the trade-offs.  However, even this is of so much value given our lack of knowledge and the lag time between when an organization makes a decision to contribute resources and when those resources are actually deployed.  In that time not only the knowledge, but the actual situation on the ground and hence the Pareto frontier would likely have changed.

So I see the benefit of models like this being more prominent in domestic disasters where we have better knowledge, faster response, and more control over the budget of the operation.

Multi-Objective Optimization

Similarly to everyone else here, my mind is on the presentation I will be giving next week.  However, I will be saving most of the mathematical details of that paper* for my next blog post after I have given the presentation.  Instead, I would like to address one of the fundamental aspects of that paper- multi-objective optimization.

In the paper, Rath and Gutjahr consider the distribution of aid after a disaster.  This naturally requires an extension to the traditional supply routing problem, as we can optimize over both the placement of the warehouses at the outset and then the routing of supplies from those warehouses to the victims.  Further complicating matters, there is no guarantee that the supplies will be enough to meet demand, so we also want to maximize coverage- ensuring that the majority of victims receive some form of aid.

To solve this, Rath and Gutjahr employ a model which finds the Pareto frontier for these three objectives.  In brief, the Pareto frontier consists of every solution that is not dominated by another solution.  That is to gain a benefit in one area you must give up something in another area.  So for

\text{maximize} \;(A,B)\\ \text{subject to}\;A+B\leq 4

(3,1) is on the Pareto frontier but (2,1) is not, since in the latter case, we can increase A or B without decreasing the other.

In choosing to find the Pareto frontier, they leave the user with more control over how to define the optimal solution.  It does come at a cost however.  Most obviously, it increases the complexity of the answer.  In the Rath and Gutjahr example, we have a three-dimensional frontier and it is easy to imagine further dimensions being added to accommodate network restoration. So we must be careful when doing multi-objective optimization with the Pareto frontier to provide enough information to the decision makers so they can understand the trade-offs without being overwhelmed with data.  The goal is to provide clear decisions not simply dump the problem on someone else.

The second problem of using the Pareto frontier is computational.  To find the frontier often requires more time than would be required to find a single optimal objective value.  Further, it is often necessary to use less traditional and straightforward OR approaches like evolutionary programming or heuristics.

There are, of course, other methodologies for formulating multiple objectives.  We will consider a couple of the most common. For a more detailed survey see a “Survey of multi-objective optimization methods for engineering.”

In my current work on ambulance dispatch we have the problem of optimizing both survival for some patients and customer service for other less critical patients.  As we have a preference, survival is more important than customer service, we can use the weighted-sum method.  This entails adding the objective functions and weighting them according to preference.  The result is merely one of the solutions on the Pareto frontier.  The higher the weight on the survival relative to the weight on the customer service, the more we favor trading customer service for survival on the Pareto frontier.  So, this method limits our search and thus enables us to obtain a much quicker answer.

It is also briefly worth noting that by varying the weights on the objectives it is possible to find the Pareto frontier if the problem is convex.  There is, however, no guarantee that the necessary discretization of such a search will find all the relevant information.

Another common method is the bounded objective.  This requires a preference for which objective is most important.  This objective is then maximized(minimized) and the other objectives are bound the feasible region in the constraints.  This method suffers from both being possibly infeasible, if the bounds are not chosen with care, and not necessarily being on the Pareto frontier.  The preferred objective is clearly optimal, but nothing dictates that there is not a better solution in which the same preferred objective is obtained with better values for the objectives in the constraints.  It is however, a good solution in a case where ‘good enough’ rather than completely optimal is acceptable.

Finally, we consider goal programming.  Goal programming sets a desired level we want to reach for each of our objectives and then seeks to minimize the distance between the solution and the desired outcome.  These differences may be weighted depending on preference.  Traditional goal programming also suffers from the possibility of not achieving a solution on the Pareto frontier.  This has been addressed in more recent algorithms to some extent, however, goal programming can still suffer from computational time problems as it often involves the uses of nonlinear programming.

As can be seen in the brief survey, Rath and Guntjahr, provide a fairly good solution with their heuristic to determine the Pareto frontier.  So long as there is not too much information for the decision maker to handle, this may be the best possible choice.  Other methods in the field generally seek points on the frontier and do so in quicker time and with more precision, but require some knowledge of the decision makers’ preferences.  In practice, such an exact knowledge of preference can be exceedingly hard to come by.

 

*Rath, Stefan, and Walter J. Gutjahr. “A math-heuristic for the warehouse location–routing problem in disaster relief.” Computers & Operations Research 42 (2014): 25-39.

Uncertain Information

By Eric DuBois

Back in August 2011, I was in Massachusetts preparing for my first season as a teacher at Nature’s Classroom in Colebrook, CT.  Colebrook is located in the Berkshire Mountains in the rural northwest corner of Connecticut.  To get there requires driving for about an hour on small state and local roads.  Unfortunately, at the same time as I was preparing to leave, Hurricane Irene was hitting southern New England and by the time it was over, the region was a mess.

Many of the rivers across the region were flooded.  As many of the roads in the region either follow, or at a minimum cross, rivers, they had become impassable in the aftermath of the storm.  To further complicate matters, the huge number of downed trees and powerlines added additional roadblocks to my journey.  From the outside this appears to be a fairly straightforward OR problem.  All we must do is find the new shortest path. Right?

Unfortunately, in this instance as in most real disasters, the reality does not fit the model very well.  Specifically, most shortest path problem models assume perfect knowledge of the network or at the very least a good working knowledge of the probabilities that the roads will be open.  Two things worked against that in Connecticut.

  1. The ‘interdicted’ locations change over time. As the water proceeds down the mountains it floods progressively larger watercourses.  So when I first start out the major mountain streams may have flooded the local roads and the smaller rivers are beginning to flood.  By the time that I have reached the mountains, those small rivers have reached flood stage.  Worse yet, there is no guarantee that the local roads are now passable since they may have washed out or become impassible with debris left by the receding water.
  2. More importantly, information is quite scarce on where the blockages are. In the actual event, the State Police could provide little more than a rough sketch of what roads outside of the suburbs were underwater and almost no information on where debris had blocked transit.  It took me over two and a half hours to find a navigable route to Colebrook and that was after checking with the police and news sources for an hour.  Other teachers were not so lucky, having not properly checked the news, and didn’t arrive until the day after.

The moral of this tale is understanding the importance and difficulty in maintaining an accurate understanding of the state of the system during a disaster.  Significant literature is now looking at the use of social media and crowd-sourced information to flesh out the details of a disaster.  Unfortunately, this information is often inaccurate and misleading.  This can arise from something as simple as the lack of characters allowed in a tweet up to a complete misunderstanding of the situation by the individuals on the ground.  Unlike state police or disaster responders, these individuals have likely had no formal training in communicating accurately or previous disaster experience to gauge the conditions by.  So while the information provided may be better than nothing, it is certainly no panacea.

I can certainly see using the information to provide a gauge to determining where infrastructure restoration is most likely needed.  However, in the eventuality that we need to route emergency vehicles around these roadblocks, probabilities and guessing is not, in my opinion, a terribly great way to go about finding the optimal choice.  As operations researchers, how do you feel we can make use of this new source of data to inform out disaster response planning?

Using OR to find more equitable solutions

By Eric DuBois

Anyone that knows me at all or has spent at least two minutes in my office during NCAA hockey season knows that I am a huge hockey fan- especially women’s hockey.  This is partly from self-interest.  One of my alma maters, Clarkson, won the NCAA championships back in 2014. Further, if you look at Wisconsin, the women’s hockey team here has been consistently outstanding of late, the men’s team, not so much.  Both Clarkson and Wisconsin are in the Frozen Four again this year and it should be a great weekend for hockey.

One of the consistent problems facing women’s hockey is the same problem facing a lot of other women’s sports: namely, it is not considered ‘as good’ as men’s hockey and therefore, gets little attention from the NCAA.  So it came as no great surprise this year when the tournament bracket came out and it was a pretty sad farce of a thing showing very little commitment from the NCAA.  Really I get to see Clarkson play Quinnipiac again?  Didn’t we just play them less than a week ago in the ECAC tournament?  And I’m sure Boston College was just as pleased to see that they get to play Northeastern for the umpteenth time.  Real crowd pleasers there…

This reminded me of Eli’s post earlier in the year about his role modeling for the Center for Athletic Scheduling at UW- Stevens Point.  One of the benefits of scheduling with a model is that you can maximize the fan’s enjoyment of new matchups and not have to resort to replaying the same old games.  More to the point, though, operations research allows us to get a more objective solution than anything that can be produced by hand.

I think this is a benefit that is often ignored.  Rather, we tend to focus on the faults that can originate from basing our system on finding the best or most efficient solution.  However, given the variety of different groups that can be affected by public policy, it is worth considering the benefit of having an objective solution to the problem, especially if that solution has been constrained to provide a reasonably equitable solution.

Whether we like it or not, we all have unintended biases that affect what we would consider to be a reasonable.  I personally recommend looking at Project Implicit if this interests you.  I have little doubt that if I were to make the NCAA bracket, I would be highly susceptible to team pairings that would annoy many people as well.

In a similar way, in planning disaster response, I am sure that personal biases would get in the way.  For proof of this in action, look no further than what happened to the original San Francisco Chinatown during the 1906 earthquake.  For those not aware, Chinatown originally looked the same as the rest of the city.  It was only after the earthquake and in a bid to win white approval, that they sought to make it look ‘Oriental.’  That was mainly because the white controlled emergency response decided Chinatown was worth losing in its entirety to save the affluent neighborhoods nearby.

So while we may be worried about the inequalities that arise from looking only at efficiency, humans are hardly good arbiters of fairness.  Do you think the objectivity of operations research gives it an edge in producing good public policy solutions?

Ending Traffic Jams

By Eric DuBois

My post today is somewhat motivated by Sam’s comment last week about his brother avoiding stoplights even if it did not improve his overall drive time.  It reminded me of an interview I heard on the radio while hiking a couple years back.  The argument was that we could alleviate many types of traffic jams by simply moving slower and more constant rate.  There is actually quite a following for this theory and it has proven true so far when tested experimentally.

This works on two levels.  On the more objective traffic engineering level, it smooths out the ‘traffic waves’ where cars slow down in a given area (possibly to a stop) and then speed up outside of that area.  Essentially, stop and go traffic is a series of traffic waves.  This is obviously more gas efficient and safer, and better yet, it actually increases total throughput in that area.  More directly to queuing psychology, it means that rather than constantly having to stop, the driver is constantly feeling a measure of progress, which improves satisfaction with waiting in line.

A similar theory holds when traffic is trying to merge, say at an off-ramp.  If we leave room and allow drivers to merge with us, then we can all maintain a relatively constant, if slow speed.  Whereas by cramming together, the driver must force their way in and that can stop traffic entirely creating a new traffic wave

The big complaint with this is that it means allowing a gap to open between you and the driver ahead.  You need a large enough gap that in the time it takes you to reach the next car, they are moving again.  Now you may say (and I certainly have), that it is not fair to those of us waiting in line to have this new person drive past us, making us look like fools, and cut in line up ahead.  However, that extra car would only add a few seconds to your total commute and by choosing to spite them, you are making the situation noticeably worse for everyone following after.

In essence, we are focused on what queuing theory calls a skip, that is, they are skipping ahead of us in line and a slip- we are slipping further back in line.  On a very basic psychological level, this doesn’t seem fair and annoys most of us to no end (some more than others) by its violation of the First-In First-Out service rules we are taught as children.

What’s especially interesting about traffic, however, is that it isn’t a traditional queue.  The number of people ahead of us is only part of the equation determining what our what time will be since the ‘service rate’ is dependent on how we act towards each other.  By actively cooperating, we can decrease service time and finish service sooner.

In this instance, I think the Nash Equilibrium as it currently occurs enforces that traffic jams will continue to occur.  As much as we may want to cooperate and reach a better equilibrium, there will always be the feeling that if we don’t cooperate we can make someone else later deal with that one extra car and come out ahead ourselves.

From a public policy perspective, two ideas have been proposed.  One is to send rolling roadblocks of police through those areas at a slightly reduced speed which requires a fair bit of manpower and only seems worthwhile on particularly common or intractable jams.  The second is to adjust down the speed limit before the jam, decreasing inflow and again smoothing out the wave.  The latter while more practical, also assumes that people will obey the speed limit and we all know how often that happens.

The best case scenario may instead be to find some way to better incentivize cooperation.  They have certainly proven effective before in solving congestion problems.

Measuring System Performance and Campbell’s Law

by Eric DuBois

This week I would like to discuss measuring system performance and its unintended consequences.  I will share a story out of Larson’s 1987 paper “Perspectives on Queues: Social Justice and the Psychology of Queueing.”

No one particularly likes waiting around.  So naturally one would assume that a good objective measure of the performance of a queueing system is the average time spent waiting in the queue.  Lower the expected time so that people wait less and they will be happier with your service.  Except, of course, that humans are not so easily understood.

In one of my favorite examples of unintended consequences, Larson describes how early morning business passengers at a Houston airport would complain on a regular basis about having to wait for their luggage after deplaning.  The rub being that it wasn’t the wait that irked them so much as it was seeing their fellow bagless passengers proceed straight out the door to the waiting taxis while they waiting on average an additional 7 minutes to receive their baggage.

The baggage handlers were not taking especially long; it was simply that the airport had chosen the most efficient location for the passengers to deplane and leave the airport in the least amount of time.  That is, they chose a location so close to the exit that it only took about a minute from leaving the plane to get to the baggage carousel.  There was simply no way that baggage handlers could keep up.  The solution was simple- increase the distance between the deplaning location and the door.  Now everyone had to waste their time walking from one end of the terminal to the other, but no one felt cheated.  So despite objectively worsening performance, passengers were happier overall and “passenger complaints dropped to nearly zero.”

The point of this tale is a reminder that while our objective functions effect how we view the world and react to it, we shouldn’t forget that there is a very subjective reality aside from any objective measure we use on it.  One of the common worries with EMS service models is that in only providing rewards for serving patients quickly, you will simply abandon some patients to their fate.  Objectively it makes sense- if we only get credit for serving patients within 9 minutes, why bother even serving the patient that is 10 minutes out?  Worse yet, what if all signs point to them not surviving to discharge? should we still rush the nearest ambulance?

Of course we should still serve them.  Our subjective knowledge of customer service and feelings of fairness argue for serving all patients, even if it is not ‘objectively optimal.’

In many cases, the problems that we see stem from Campbell’s Law (Or the closely related Goodhart’s Law), which basically states that if people understand how they are being measured, the measure becomes useless as people seek to do well on the measure.

A common example is school testing.  Back when I taught in Massachusetts, we spent an inordinate amount of time teaching our students how to take the state test (the MCAS).  If they failed the test, they would have a difficult to well-nigh impossible time in graduating high school.  Moreover, we were judged on how many of our students passed their MCAS- a measure which clearly favored the affluent college-bound suburbanites over my urban, vocational students.

I remember on several occasions having to shutdown fruitful discussions on basic scientific principles, because we had to return to the curriculum defined by the state.  The former were clearly more important to their long-term education, but would never be tested on.  So we plodded along and rather than understanding why the Earth has an atmosphere, they learned how to best answer a multiple choice test.  Most of them did pass the MCAS and will be able to graduate high school, but in the true measure- how much they learned in high school, I fear they will be sorely lacking.

So what do you think? Is there better way to measure system performance without skewing the results or losing site of reality?