Complex shipping price calculations

Question

Our website works out shipping totals for orders, every item in our database has a cubic size and there is a size limit for using courier vs freight for an item. But we get orders with multiple items and I notice it's calling things freight when not needed.

The parcel limit is 0.15m3 per courier ticket, if bigger than that they have to go by freight instead. Incidentally freight cost more on small consignments only becuase there is a minimum charge, if there wasn't, this would not be a problem at all.

I'm asking here because our programmer has a limited time before he leaves the country and this was not one of the urgent tasks we gave him, if we are to get it done at all then I need to help him in the right direction - but alas, I am not a programmer.

The Problem:
An order came in with 2 items, both 0.106 each to a local address

• Website calls it a total of 0.212 and makes it freight @ $42
• We can ship 2 boxes on a courier, $10 total

But needs to only use freight if any ONE item is bigger than the limit of 0.15
so, it would see that order as (0.106=$5) and (0.106=$5) = $10

For example:

1. Suppose there was something more complex:
   10 items in cart, 0.02 each. Website would work it out as 0.2 and call it freight, but we could put it in 2 boxes and pay $10

2. 5 items in cart, 0.01 x 4 and 0.12 x 1. Website would work it out as 0.16 and call it freight, but we could send 2 cartons - 0.04 and 0.12 costing $10

Can it do this: if any ONE item is bigger than 0.15 make it all freight, otherwise add up how many tickets needed supposing we packed into biggest boxes possible example 2:

(0.01+0.01+0.01+0.01)=0.04=$5,
(0.12)=0.12=$5 
==$10

Tricky I know, but its just maths lol, and it matters most because a ridiculous shipping price might stop an order.

Answer 1

Like @AlistairIsrael said this is the bin packing problem which is not completely trivial to solve.

However below is one solution to this problem.

If we go through all combinations of ways to package the items and try and find the minimal cost, then we have a solution. Note that this solution is a brute-force solution, and as such will quickly slow down as the number of items grow.

To find all possible ways to partition the shipment into different boxes; we can use the algorithm from this answer for that:

Translating function for finding all partitions of a set from Python to Ruby

Next we loop through all the different combinations and search for the minimum cost. The solution then works like this:

> optimize_shipping([0.01, 0.01, 0.01, 0.01, 0.12])
Shipping type: courier
Total price  : $10
Packaging    : [[0.12], [0.01, 0.01, 0.01, 0.01]]

> optimize_shipping([0.01, 0.01, 0.12, 0.15, 0.12])
Shipping type: courier
Total price  : $15
Packaging    : [[0.01, 0.12], [0.15], [0.01, 0.12]]

> optimize_shipping([0.09, 0.09, 0.01, 0.12, 0.15, 0.12])
Shipping type: courier
Total price  : $25
Packaging    : [[0.12], [0.15], [0.12], [0.09, 0.01], [0.09]]

> optimize_shipping([0.01, 0.01, 0.01, 0.30])
Shipping type: freight

The code:

COURIER_LIMIT = 0.15
COURIER_PRICE = 5

class Array
  def sum
    inject(:+)
  end

  def partitions
    yield [] if self.empty?
    (0 ... 2 ** self.size / 2).each do |i|
      parts = [[], []]
      self.each do |item|
        parts[i & 1] << item
        i >>= 1
      end
      parts[1].partitions do |b|
        result = [parts[0]] + b
        result = result.reject do |e|
          e.empty?
        end
        yield result
      end
    end
  end
end

def optimize_shipping(boxes)
  if boxes.any? { |b| b > COURIER_LIMIT }
    puts "Shipping type: freight"
    return
  end

  # Try and find the cheapest most optimal combination of packaging
  smallest_box   = 9999
  cheapest_price = 9999
  cheapest_combination = []

  # Go through all paritions and find the optimal distribution
  boxes.partitions { |partition|
    # Add up sizes per box
    sizes = partition.map(&:sum)

    # Check if any box got too big for courier, and skip if so
    next if sizes.any? { |s| s > COURIER_LIMIT }

    # Calculate total price for this combination
    total_price = partition.length * COURIER_PRICE

    if total_price <= cheapest_price
      # Naive algo to try and find best average distriution of items
      next if total_price == cheapest_price && sizes.min < smallest_box

      # Save this new optimized shipment
      smallest_box         = sizes.min
      cheapest_price       = total_price
      cheapest_combination = partition
    end
  }

  puts "Shipping type: courier"
  puts "Total price  : $#{cheapest_price}"
  puts "Packaging    : #{cheapest_combination.inspect}"
end

Answer 2

There is no code shown, but basically, you would take your orders which may be a collection such as an array, and do this:

orders = [0.01,0.16,0.01,0.01]
freight = orders.any? {|item| item > 0.15 }

Of course, there will need to be more logic, but you can now use the freight as true or false as a boolean to continue on the needed work.

I believe count will be your friend here as well.