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.
Solution Stats
Problem Comments
5 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers2
Suggested Problems
-
2176 Solvers
-
5964 Solvers
-
1219 Solvers
-
112 Solvers
-
Create matrix of replicated elements
395 Solvers
More from this Author2
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
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.
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...
@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?
@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)
@Alfonso, the test suite has been updated per your suggestion. It does work against the author's reference solution.