0
$\begingroup$

Suppose we have two markets. Each market has various buy & sell orders that we can sell to or buy from respectively. Each order represents a specific number of a particular item type that someone is selling or buying for a specific price per item and we can buy/sell any amount of items from/to any order. Each item type has its own volume per item (m3).

We have transportion that can transport a specific amount of volume and some budget amount.

Our goal is to form such transport cargo load of items that would maximize our profit by going from station A to station B assuming our limited cargo capacity and budget.

The algorithm I'm using is the following:

  1. Sort sell orders of the source station by price_per_item in ascending order and group them by item_type.
  2. Sort buy orders of the destination station by price_per_item in descending order and group them by item_type.
  3. For each item type, form pairs of sell-buy orders based on the amount available in both markets (e.g. [Item, Quantity, Buy At, Sell At]: [Apple, 25, 50, 75], [Apple, 5, 50, 70], [Apple, 20, 60, 70])
  4. Perform one of the following actions based on user input:
    • (A) Sort pairs by profit per m3 (sell_price - buy_price / volume_per_item) in descending order.
    • (B) Sort pairs by profit / buy price ratio ((sell_price - buy_price / volume_per_item) / buy_price in descending order.
  5. Take as many items as possible from each pair of the sorted list until either budget = 0 or cargo_capacity = 0 or there are no pairs left.

When using option (A), the described algorithm doesn't take the budget into account while forming the list of most profitable pairs so it gives poor results with a limited budget. When the budget is high, due to the variety of the market the following algorithm uses a full budget amount while cargo space is usually almost empty (which I don't consider the acceptable result as I need to mitigate risks of losing cargo and having large losses due to low ROI).

When using option (B), the gives good profit compared to the amount used to buy the items but it doesn't utilize available budget efficiently.

So the task is to maximize total_profit / total_buy_price ratio while utilizing available budget_amount and cargo_capacity as much as possible.

Does this fall under some type of mathematical problem that can be solved in a mathematical way, and if so, can you suggest some sources to read up on in detail? Thanks.

$\endgroup$
1
$\begingroup$

If you are handling only one truck/cargo in your problem, then this is a typical Knapsack problem. If you are handling the bigger problem of distributing all items on how many trucks, then it is a variant of Bin Packing problem. Both problems are NP-Complete, however Knapsack has approximate algorithms with guaranteed bounds from optimality.

I suggest you use a somehow mangling compromise between A and B:

  1. Solve using A, then solve using B and take the best answer.
  2. Do both sortings, keep 2 arrays, then at each step compare A choice to B choice and select the better choice (greedy approach)
  3. Assign a weight to each factor then sort an array C according to your weight function. If you don't know the weights then make it equal (half for each factor). If you value price more make its weight above 0.5 if you value volume more then give it a higher weight. This is called multiplicative weight
$\endgroup$
1
  • $\begingroup$ Thanks for the reply! This particular problem turned out to be the Bounded Knapsack Problem. However, the mentioned problem doesn't include the budget limitations. $\endgroup$
    – Vladyslav
    May 12 '20 at 18:20
-1
$\begingroup$

this is an eve online question hahaha just take the profit per item and divide it by it's size and sort descending then fill in your cargo with as much as you can this way you hit both in the same time

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to Computer Science! This question asks for a mathematical perspective on the problem. This means that beyond suggesting a method to solve the problem, we want to know how effective this method is in the general case, and find a mathematical proof of this fact. I think that your heuristic seems reasonable in the context where you apply it, but it may not be the most efficient method in general. Additionally, we prefer that answers are written carefully with full punctuation, and not how you would be sending chat messages. $\endgroup$
    – Discrete lizard
    Nov 20 '20 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.