0
$\begingroup$

Problem statement

  • There is a number of towns $\{T_1 \dots T_n\}$, a number of items $\{I_1 \dots I_n\}$ and a number of lorries $\{L_1 \dots L_n\}$.

  • Each town $T_n$ has a market which offers a quantity $Q_{i}$ of items $\{I_{m < n}\}$ for buying (always a subset of $I_n$), but any item $I_n$ can be sold there at the same buying and selling price $P_{Tb} = P_{Ts}$.

  • Each item $I_n$ has a weight $W_n$ and a price $P_{Ci}$, which is different in every city $C_n$.

  • Each lorry $L_n$ has a given weight capacity $C_n$ and originates in a different town $T_n$. It is able to move between them at the same cost (the route between e.g. $C_m$ and $C_n$ is the same as between $C_p$ and $C_q$) and trade the items.

  • The trading company which owns the lorries has a given amount of money $M$.

  • Selling is akin to destroying, i.e. a sold item is off the market and can not be bought again; the supply is limited.

  • All prices and quantities of all items at every town are known.

Objective

Maximise the final profit per a number of trips until the market is depleted.

Simplification attempts

This problem seems to be very complex, which is why I've been trying to reduce the number of dimension and introduce constraints that would simplify it and still result in a good ‘optimal solution’ (somewhere around 90% of total maximum profit would be great).

The following constraints came to my mind:

  • There is always enough money to load every lorry to its maximum capacity.
  • The number of future trips by each lorry is equal and known in advance.
  • The number of different items per lorry is restricted to a small number, e.g. seven.
  • Moves occur sequentially, not in parallel.
  • Perhaps ignore the price-to-weight ratio because in my use case, the variance is fairly low.
  • Limit the number of lorries to one and make a separate solution for every lorry after each movement/transaction.

Naive solution

  1. For every town with a lorry, sort the available items according to their difference from the median global price, so an item whose price is at e.g. -15% below the median would rank higher than one whose price is at +5% below the median.
  2. Take the $n$ cheapest items that are required to stuff the lorry to its capacity.
  3. Calculate the profit from selling these items in every town and pick the most profitable one. Make sure that two or more lorries never end up in the same city (supply issues).
  4. Repeat for a given number of moves.

Question

I'd like your help to find a good optimal solution or perhaps even the best one, given a sufficiently low value of each variable, if you're able to brute-force it.

As you can see from the definition and approach, I have a lot to learn and as such, I'm looking especially for practical rather than academic sources and solutions – ideally an algorithmic/programmatic implementation.

Any tips, references, or even keywords will be welcome, as I can't even properly define what I'm looking for. To me, it seems like a blend of the knapsack problem and the travelling salesman problem where the minimisation of the distance is replaced with the maximisation of the profit and it's not necessary to visit all vertices.

I've read through various examples using genetic algorithms or ant colony optimisation, but they always involve much simpler problems, which are as clear as day. I'm not sure how I would even encode this for something like GA.

Thank you!

$\endgroup$
4
  • $\begingroup$ I don't understand what the notation $I_{m<n}$ means or what $Q_i$ represents. Perhaps you might be able to apply tools from operations research (e.g., ILP solvers?). $\endgroup$
    – D.W.
    Jan 8 at 8:12
  • $\begingroup$ Apologies, the notation may indeed be a bit confusing. The former was meant to represent a subset of items which is always smaller than all items on the market, the latter was supposed to be the quantity of a given item. For example, consider 10 different items overall on the market. $n < 10$ of these items would be available at every town at a random quantity $Q$ that is different for each individual item. I will look into ILP solvers, thank you for the suggestion! $\endgroup$ Jan 8 at 12:07
  • $\begingroup$ I'd try to see how you might solve or develop heuristics for a simpler version with one town, one market. Then generalize. $\endgroup$
    – TickaJules
    Jan 8 at 15:50
  • $\begingroup$ @TickaJules I'm sorry about the late reply! I'm not sure I understand what you mean, since the ‘main optimisation problem’ is which town to choose as the next destination and select items to maximise the profit in relation to that, which does not work if you have only one town where all items have the same sell and buy price (in that case I would simply maximise the price-to-weight ratio, since the more the cargo is worth, the more profit it may generate). Could you please expand on what you said or let me know if there's something unclear in order for me to improve the question? Thank you! $\endgroup$ Jan 12 at 2:04

Your Answer

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

Browse other questions tagged or ask your own question.