# Category Archives: Motivation

## Enforcing a Restricted Smoking Policy on the UM Campus: a TSP Variant

The Coral Gables campus of the University of Miami is slowly transitioning into a smoke-free campus. (I can’t wait for that to happen.) Presently, there are a number of designated smoking areas (DSAs) around campus and nobody is supposed to smoke anywhere else. Here’s a map of campus with red dots representing DSAs (right-click on it and open it in a new tab to see a larger version):

Unfortunately, enforcement of this smoking policy is nowhere to be seen. The result? Lots of students smoking wherever they want and, even worse, smoking while walking around campus, which is a great way to maximize their air pollution effect. Don’t you love people who live in the universe of me, myself, and I? But let me stop ranting and return to operations research…

As someone who does not enjoy (and is allergic to) cigarette smoke, I started thinking about how to use OR to help with the enforcement effort. Let’s say there will be an enforcer (uniformed official) whose job is to walk around campus in search of violators. Based on violation reports submitted by students, faculty and staff, the University can draw a second set of colored dots, say black, on the above map. These black dots represent the non-smoking areas in which violations have been reported most often. For simplicity, let’s call them violation areas, or VAs.

In possession of the VA map, what is the enforcer supposed to do? You probably answered “walk around campus visiting each VA”. If you’re now thinking about the Traveling Salesman Problem (TSP), you’re on the right track. The enforcer has to visit each VA and return to his/her starting point. However, this is not quite like a pure TSP. Let me explain why. First of all, unlike the pure TSP, the enforcer has to make multiple passes through the VAs on a single day. Secondly, it’s also likely that some VAs are more popular than others. Therefore, we’d like the enforcer to visit them more often. Finally, we want the multiple visits to each VA to be spread throughout the day. With these considerations in mind, let me define the Smoking Policy Enforcement Problem (SPEP): We are given a set of $n$ locations on a map. For each location $i$, let $v_i$ be the minimum number of times the enforcer has to visit $i$ during the day, and let $s_i$ be the minimum separation between consecutive visits to location $i$. In other words, each time the enforcer visits $i$, he/she has to visit at least $s_i$ other locations before returning to $i$. The goal is to find a route for the enforcer that satisfies the visitation requirements ($v_i$ and $s_i$) while minimizing the total distance traveled.

After a few Google searches, I discovered that the SPEP is not a new problem. This shouldn’t have come as a surprise, given the TSP is one of the most studied problems in the history of OR. The article I found, written by R. Cheng, M. Gen, and M. Sasaki, is entitled “Film-copy Deliverer Problem Using Genetic Algorithms” and appeared in Computers and Industrial Engineering 29(1), pp. 549-553, 1995. Here’s how they define the problem:

There are a few minor differences with respect to the SPEP. In the above definition, $s_i=1$ for every location $i$. What they call $d_i$ is what I call $v_i$, and they require exactly $d_i$ visits, whereas I require at least $v_i$ visits.

I wasn’t aware of this TSP variant and I think it’s a very interesting problem. I’m happy to have found yet another application for it. Can you think of other contexts in which this problem appears? Let me know in the comments.

2 Comments

Filed under Applications, Motivation, Traveling Salesman Problem

## Don’t Get Discouraged! It Happens to Everyone

Once in a while, I feel a bit tired and discouraged, especially when I find myself stuck while trying to solve a particular problem. I attack it from different angles, try special cases, write down thousands of lines of code, and the little brat doesn’t give in. Sometimes, the best conclusion I am able to obtain is “none of these methods work”. Frustration sets in and, many years ago, I used to think to myself: “I wish I were as smart as person X; they never run into trouble like this.” But guess what? They do! An extremely successful researcher, whom I greatly respect and admire, once told me this:

At least half of my research has been unsuccessful.

Here’s another quote that I enjoy very much. It’s by Egon Balas and it appears in the epilogue of his book Will to Freedom:

…This is the flavor of mathematical discovery. It is an uneven process that often becomes hectic, with periods of sleepless of half-sleepless nights. It requires the kind of passionate concentration in the grip of which you forget about everything else for a while. To be successful at it, you must have “fire in your belly.” And it certainly helps if your basic inclination is to persist and not give up in the face of difficulties, not to become dejected in case of setbacks, but to try again and again until you manage to find the right way.

In the same book, Balas refers to a former colleague and collaborator of his, Grigore Moisil (a famous Romanian algebraist), who had some interesting views on how to do mathematics:

Mathematics is not necessarily done at your desk. Mathematics is done when you wake up in the morning and do not immediately get out of bed; it’s done in the bathtub; it’s done while sitting on the toilet; it’s done while you are dressing; and it’s done while you are taking a walk.

I agree with Moisil. That’s part of the fun with math; you can work on it just about anywhere. (I’m particularly fond of all kinds of waiting rooms: doctor’s/dentist’s office, airport gates, nail salon while waiting for wifey, etc.) In fact, changing your work environment may actually help. I’ve had many good ideas away from my desk.

Do you have a motivational quote or text to which you refer when feeling a bit discouraged? I’d love to read about them in the comments.

6 Comments

Filed under Motivation, Research