Tag Archives: transportation

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

Find Out What Happens to Mr. Lovr

I’ve had a number of people tell me that they like my Valentine’s Day post, but many of them did not solve the Excel Spreadsheet. That’s the most important part of the post! You have to see what happens to Mr. Lovr! There’s no set-up necessary; just open Excel Solver (it’s an add-in you have to enable in Windows and a separate program in the Mac), and click on the “Solve” button. You’ll be glad you did.

Leave a comment

Filed under INFORMS Monthly Blog Challenge, Love, Valentine's Day

Transporting Flowers with Love

Mr. Lovr, a lonely gentleman, does not want to spend Valentine’s day alone in 2011. As one of his New Year’s resolutions, he intends to send roses to nine of his lady friends. Being an avid procrastinator, however, he waits until the last minute and finds out that only eight flower shops in his city still have roses available. For lack of better names, let’s call those flower shops F1, F2, F3, …, F8. The number of bouquets of roses available at each shop are, respectively, 4, 4, 3, 2, 2, 2, 2, and 1. Based on how well he knows each of his potential valentines, whom we’re going to call V1, V2, V3, …, V9, he calculates how many bouquets he needs to send to each of them to increase his chances of going on at least one date. The numbers are, respectively, 3, 2, 2, 2, 2, 2, 2, 2, and 3. At this point, a light bulb goes off in Mr. Lovr’s head, and he remembers from his Operations Research class that this is a transportation problem. But there’s something missing…Ah! The costs! He calls each of the eight flower shops and asks how much it would cost to ship one bouquet of roses to the addresses of each of his nine lady friends. He then compiles the following table of costs (in dollars):

He also remembers that because the total supply is equal to the total demand, he can write all of the constraints in this problem as equalities. Essentially, he has to say that, for each flower shop, the number of bouquets that it ships has to be equal to the number of bouquets that it has. Similarly, he needs one constraint for each valentine saying that the number of bouquets that they receive has to be equal to the number that they want (according to his estimates above). To avoid suspicion, he also decides that it’s better for each flower shop to send no more than one bouquet to the same person. So far, so good, but he needs a specific shipment plan because he’s running out of time.

He opens up an Excel spreadsheet and creates the following layout of cells (he chose pink to make it more romantic):

Somewhere else in his spreadsheet he also typed the table of costs shown above. To his surprise, he even remembered to use the SUMPRODUCT function to calculate the total cost expression. He clicks “Solve” and finds out that the cheapest way to send all 20 bouquets will cost him $38. Not bad…but wait a second…something amazing happened! He cannot believe his eyes! The optimal solution exhibits a very curious pattern! Could it be a Valentine’s Day miracle? Could it be the power of love? If you want to see for yourself, download Mr. Lovr’s spreadsheet, open Excel Solver, and solve the model (no setup necessary, just click the “Solve” button). (NOTE: this spreadsheet has been tested with Excel 2007 under Windows XP, and with Excel 2008 under Mac OS X Snow Leopard. I’m not sure the “trick” will work in earlier Excel versions. For a free download of Excel Solver for Mac OS X, go here.)

Thanks to my love for giving me the idea for this blog post.


Filed under Exam Fun, INFORMS Monthly Blog Challenge, Love, Valentine's Day