Problem 44718. Optimize the Tollbooths

Created by Aamod Garg

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Your company has recently built its own highway from which they hope to generate some revenue. The highway has no branches or intersections, it is a simple line segment. Your company also has access to simple data from some potential customers that describe their start and endpoint locations and their budget.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Tollbooths are also located on various locations on the highway. The total toll a customer pays is the sum of all tolls on the tollbooths that lie between their start and end locations. If a customer cannot afford the total toll they must pay, then they simply don't make the trip and end up paying nothing.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>The customer wants to start or end their destination at the precise location of a tollbooth, so we can represent the problem as follows. We have a graph that is a simple path with N nodes. Each node represents a potential start or end location of a customer and there is a single tollbooth located on each node. So the total toll a customer pays is the sum of the tolls on the nodes they cross to reach their endpoint. Both the start point and end point are also toll booths.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Your task is to set the tolls on each of the tollbooths to generate the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>maximum revenue</w:t></w:r><w:r><w:t> for your company. The answer is the pricing of each toll booth.</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: normal; text-decoration: none; white-space: normal; "><div style="display: block; min-width: 0px; padding-top: 0px; transform-origin: 332px 171px; vertical-align: baseline; perspective-origin: 332px 171px; "><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 42px; white-space: pre-wrap; perspective-origin: 309px 42px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">Your company has recently built its own highway from which they hope to generate some revenue. The highway has no branches or intersections, it is a simple line segment. Your company also has access to simple data from some potential customers that describe their start and endpoint locations and their budget.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 42px; white-space: pre-wrap; perspective-origin: 309px 42px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">Tollbooths are also located on various locations on the highway. The total toll a customer pays is the sum of all tolls on the tollbooths that lie between their start and end locations. If a customer cannot afford the total toll they must pay, then they simply don't make the trip and end up paying nothing.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 52.5px; white-space: pre-wrap; perspective-origin: 309px 52.5px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">The customer wants to start or end their destination at the precise location of a tollbooth, so we can represent the problem as follows. We have a graph that is a simple path with N nodes. Each node represents a potential start or end location of a customer and there is a single tollbooth located on each node. So the total toll a customer pays is the sum of the tolls on the nodes they cross to reach their endpoint. Both the start point and end point are also toll booths.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; transform-origin: 309px 21px; white-space: pre-wrap; perspective-origin: 309px 21px; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="">Your task is to set the tolls on each of the tollbooths to generate the</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style=""> </span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style="font-weight: bold; ">maximum revenue</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; transform-origin: 0px 0px; perspective-origin: 0px 0px; "><span style=""> for your company. The answer is the pricing of each toll booth.</span></span></div></div></div>

Your company has recently built its own highway from which they hope to generate some revenue. The highway has no branches or intersections, it is a simple line segment. Your company also has access to simple data from some potential customers that describe their start and endpoint locations and their budget.

Tollbooths are also located on various locations on the highway. The total toll a customer pays is the sum of all tolls on the tollbooths that lie between their start and end locations. If a customer cannot afford the total toll they must pay, then they simply don't make the trip and end up paying nothing.

The customer wants to start or end their destination at the precise location of a tollbooth, so we can represent the problem as follows. We have a graph that is a simple path with N nodes. Each node represents a potential start or end location of a customer and there is a single tollbooth located on each node. So the total toll a customer pays is the sum of the tolls on the nodes they cross to reach their endpoint. Both the start point and end point are also toll booths.

Your task is to set the tolls on each of the tollbooths to generate the *maximum revenue* for your company. The answer is the pricing of each toll booth.

Solve

Solution Stats

11 Solutions
2 Solvers

Last Solution submitted on Aug 23, 2020

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

J. S. Kowontan on 4 Aug 2018

Hi, Aamod, this is quite an interesting problem. I'll appreciate your clarification on test case 2. The toll pricing strategy that maximized the profit was stated as [10, 5, 0]. . Hence, for the given option and budget, the total profit will be 30. But a quick check shows that a toll pricing strategy of [5, 10, 0], which is valid for the given option and budget, also gives a total profit of 30. Unfortunately, the test suite assumes uniqueness of the profit maximizing toll strategy. In such situation, how are we to proceed? Thanks.

Alfonso Nieto-Castanon on 23 Aug 2020

I agree, the problem as stated has multiple valid solutions. Could you please change the testsuite to accommodate that?: e.g. by changing "assert(isequal(toll_pricing_strategy(option,budget),y_correct))" to "y=toll_pricing_strategy(option,budget); assert(sum((option*y').*(option*y'<=budget))==sum(option*y_correct'));" which checks whether the solution results in the same revenue as your "optimal" solution...

goc3 on 29 Sep 2020

@Alfonso, I tested your suggestion against the reference solution provided by Aamod Garg (problem author). His solution worked for test cases 2 and 3, but failed 1, 4, and 5 due to that modification (therefore, I reverted to its original state). Do you have a further suggestion to fix this?

Alfonso Nieto-Castanon on 29 Sep 2020

@goc3, I would suggest "y=toll_pricing_strategy(option,budget); revenue=@(x)sum((option*x(:)).*((option*x(:))<=budget)); assert(revenue(y)>=revenue(y_correct))". That should allow equivalent or better alternatives to the author's reference solutions (if I am not mistaken this is necessary because in problems 4 and 5 the reference solution does not appear to be optimal; e.g. in problem 5, tolls [18 33 9 14 13 11 12 10] result in 330 revenue, while the reference solution results in 280 revenue)

goc3 on 3 Oct 2020

@Alfonso, the test suite has been updated per your suggestion. It does work against the author's reference solution.

Problem Recent Solvers2

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44718. Optimize the Tollbooths

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers2

Suggested Problems

More from this Author2

Problem Tags

Community Treasure Hunt

Problem 44718. Optimize the Tollbooths

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers2

Suggested Problems

More from this Author2

Problem Tags

Community Treasure Hunt

Players