Maximum profit by two parameters

Question

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 (m³).

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 m³ (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.

Answer 1

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

Answer 2

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