Tag Archives: public

Buying Metrorail Tickets in Miami

(Credits: Thanks to my MBA student Mike Plytynski for the idea for this post.)

Instead of a subway system, Miami has surface trains like the one depicted below. This is known as our Metrorail system. The Metrorail connects to the Tri-Rail system (which takes you north as far as West Palm Beach) and also to the free-to-ride, fully-automated, electrically-powered Metromover.

If you are a (reasonably) frequent Metrorail rider, you may consider buying a rechargeable card at one of the ticket vending machines. There is a 1-day pass ($5.65), a 7-day pass ($29.25), and a monthly pass ($112.50) that offer unlimited rides, but let’s focus on the case when you don’t ride often enough to justify the cost of such passes.

The current cost of a one-way trip is $2.25, regardless of distance traveled. The vending machines at the entrance of each Metrorail station allow you to load the following pre-specified amounts onto your card: $1, $2.25, $3, $4.50, $5, $10, $20, and $40.

No one likes to waste time having to stop by the vending machine to reload the Metrorail card. Besides, by Murphy’s Law, the next train will arrive and depart exactly when you’re stuck in line at the machine trying to reload your card. Therefore, we’ll consider that our objective is to minimize the number of visits to the vending machine to load our card with enough money for n one-way trips. If we were free to load any amount on the card, we could simply load n times $2.25 and be done. The absence of this flexibility is what makes this situation both interesting and a reason for us to hate the Metrorail. So let’s write an optimization model to solve this problem.

Let variable x_1 be the number of times we go to the vending machine to load $1 on the card. Let x_2 be the number of times we load $2.25 on the card, and so on all the way to x_8 (how many times we load $40). To minimize the number of visits to the vending machine, we write the objective function

\min x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8

To make sure we load enough money on the card for n trips, we write the constraint

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 \geq 2.25n

If we are not careful, we may end up with unnecessarily too much money left on the card. So it’s wise to limit that excess with the constraint

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 - 2.25n \leq L

where L is a limit on what we’d be willing to have left on the card after the n trips are completed. Conceivably, this leftover amount could be applied toward your next batch of n trips. Hold that thought; we’ll return to it later.

I put together an Excel Solver spreadsheet model for this problem, which you can download from here (sheet named “standard” in the Excel file).

If you change the second constraint above to an equality and solve this problem for different values of n and L, you can create the following heat map. The numbers in the colored squares indicate the minimum number of required visits to the vending machine.

Interestingly, some values of n, such as 10, 18, and 20, are more friendly in the sense that they allow you to visit the machine at most twice while incurring a small leftover amount (no more than $0.50). On the other hand, to avoid visiting the machine more than twice when paying for 12, 14, or 16 trips, you must be willing to accept a much higher ending balance: $3, $8.50, and $4, respectively. In addition, some of the reload amounts that might at first seem useless, such as $5 and $10, actually do get used in the optimal solutions for some values of n and L.

Ending Balances As Multiples of $2.25

As we saw above, allowing for larger ending balances on the card can help reduce the number of visits to the vending machine. One way to make these balances useful is to apply them toward future trips. If the balance is a multiple of the cost of a one-way trip, even better. To do that, we can replace the second constraint above with

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 - 2.25n = 2.25k

where k is a new, non-negative integer variable. The sheet called “leftover is multiple” in this Excel file implements this version of the optimization model. The conclusion is that you pretty much only need 2 visits to the vending machine for n \leq 20, and the value of k seems to decrease as n increases. (See Excel file for detailed results.)

Now, if only I could get someone from Miami-Dade Transit to read this post…

Leave a comment

Filed under Applications, Integer Programming, Knapsack, Mathematical Programming, Modeling, Motivation, Promoting OR, transportation

An O.R. Vocabulary Test for Non-Experts

I was talking to my wife the other day recalling how much fun she has while overhearing words from some of my research-related phone calls. We started to think about what comes to people’s minds when they hear an OR-related term whose definition is not obvious to them. I’m not talking about obscure and technical mathematical terms such as a “contrapolymatroid“, but terms at which a non-expert would actually be able to take an educated guess, such as “large-neighborhood search“. So I made a list of ten such terms and asked three friends (named A, B, and C) to define them to the best of their ability. The only rule was that they had to do it on the spot, off the top of their heads; no Googling allowed. Because none of them have training in OR, some of the answers turned out to be pretty interesting.

1. A global constraint.

A) All the stuff in the world that’s holding us back.

B) All the factors that prevent the open market from being truly open: laws, politics, foreign/domestic policy, national borders, etc.

C) Gravity.

2. Complementary slackness.

A) A dude who hangs out in a bar with no job, but complements the decor and vibe perfectly.

B) An equal and opposite reaction to whatever sectors are experiencing growth in the marketplace.

C) Time off from performing a task or responsibility granted by a superior or by oneself.

3. An odd cycle.

A) When you get your period unexpectedly; or that cycle on the washing machine that no one ever uses.

B) An economic cycle (quarter, fiscal year, etc.) which displays characteristics unlike the ones that preceded or succeeded it. In other words, in a sustained period of economic growth, it’s the one segment that shows recession.

C) A phenomenon with awkward tendencies and characteristics that is repeated every so often.

4. A spanning tree.

A) A tree that creeps from your neighbor’s yard to yours. Usually makes a huge mess in yours.

B) Has something to do with Ethernet networks.

C) A rather large plant with either a long branch span or time span on planet Earth.

5. A cutting plane.

A) A wood working tool that both cuts and planes.

B) No freaking clue.

C) A slice that intersects a 3D object in order to provide another viewpoint.

6. A shadow price.

A) The hidden cost of owning things. Like the extra cost of owning and maintaining a house or a luxury car.

B) The true representative value of goods and services, compared to the value dictated by the supply/demand of the marketplace.

C) A value for an item or service which can be obtained but that requires the buyer to perform an extensive search.

7. A comb inequality.

A) When you have a better comb than I do.

B) huh?

C) Inadequacies that persist despite efforts to eliminate them.

8. Duality gap.

A) The gap between personalities in someone with multiple personality disorder.

B) Again no idea.

C) A two-faced abyss. In other words, an alternative that may seem unfortunate but that possesses some advantages.

9. A feasible region.

A) The region where it is possible for you to live given your income, wants, and available houses.

B) Sounds like agriculture. Sorry, I got nothing.

C) An area or scope which could be a viable alternative for several purposes.

10. The first-fail principle.

A) When you get to repeat a class the first time you fail it, if approved by your high-school principal.

B) The idea that early adopters in a new sector of the market who fail will provide secondary adopters guidance through their failure. Not literal guidance, of course, but the secondary adopters will come into the marketplace and make decisions based upon others’ prior failures.

C) If you fail miserably the first time, don’t try again.

The first lesson I learned from this very non-scientific experiment is: if you’re at a party and somebody asks you what you do, you’re probably better off using an example. For instance: “Do you ever wonder how hurricane paths are estimated? That’s what I do.” You’d of course replace “hurricane paths” with your favorite problem. If the example comes before “scary” words, I believe the end result will be much better. If things go well, the ideal reaction by other person will be: “That’s so cool! What kind of training do you need to do that?” From that point on, you proceed to convince them that math is cool.

Secondly, the amusing nature of the answers above notwithstanding, this experiment got me thinking about how to make OR more visible and accessible to the general audience. That’s one of the goals of the INFORMS Public Information Committee (PIC), of which I’ve recently become a member. We already have some ideas and initiatives lined up, but I’m open to your comments and suggestions. Feel free to send me your thoughts by e-mail or via the comments section below. By the way, if you feel like doing this experiment with your own friends, feel free to send me their answers and I’ll add them to the bunch.


Filed under INFORMS Public Information Committee, People, Promoting OR