So i have this problem where a food place with only 1 delivery man has to deliver food to customers. It has all the orders in the morning and at noon he will start delivering. Each customer i has ti(time for food preparation and delivery) and vi(value of importance to the food place). So if customer j is the first customer his order will be delivered in time Xj = tj. If customer's f food get prepared and delivered after customer j, his food will be delivered in time Xf = Xj + tf. About the importance factor, the aim of the delivery man is to have the least sum of lateness where lateness is: sum from i=1 to n (where n number of customers) of vi * Xi.
For example:
I have this list of customers
CUSTOMER DISTANCE IMPORTANCE
1 10 8
2 1 8
3 5 7
4 5 3
5 3 7
If i sort them by delivering each time to the nearest customer without taking into consideration his importance i will get the sum of:
(if 2 have the same distance then choose one with most importance)
The sum by distance is :333
(8*1+7*4+7*9+3*14+8*24 = 333)
And this will be the order of the delivery
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
4 5 3
1 10 8
I also tried selecting each time the most important customer with the sum being:
(if 2 have the same importance then choose one with least distance)
The sum by importance is :399
(8*1+8*11+7*14+7*19+3*24 = 399)
And the order of the deliveries:
CUSTOMER DISTANCE IMPORTANCE
2 1 8
1 10 8
5 3 7
3 5 7
4 5 3
So in this scenario selecting always the closest one did calculate a smaller sum than the selecting always the most important one, but this doesn't work every time. I have to come up with something that will give me the optimal sum in every given list. I know that both distance and importance have to be taken into consideration but i cannot figure out the formula that i will have to apply to always get the least sum. If someone knows any greedy algorithm technique that will be in use in this scenario i would appreciate it. Thanks.
Note: neither of the greedy approaches that you mentioned results in an optimal solution.
Behold this order:
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
1 10 8
4 5 3
With the resulting sum of 323. This happens because 10 * 3 = 30 < 40 = 5 * 8.
The question becomes: Can we build on top of this observation?
Lets look at the case of only two customers:
c1 d1 i1
c2 d2 i2
If we take c1 first, its cost will be d1 * i1. At the same time, he will increase the cost of every subsequent customer cx by cx * d1. The same works the other way around for the customer c2. Which one do we pick first then?
c1 first: c1_sum = d1 * i1 + (d1 + d2) * i2 = d1 * i1 + d1 * i2 + d2 * i2
c2 first: c2_sum = d2 * i2 + (d1 + d2) * i1 = d2 * i2 + d1 * i1 + d2 * i1
d1 * i1 appears in both sums. Same for d2 * i2. The only difference is the d1 * i2 vs d2 * i1. This means that c1_sum < c2_sum <=> d1 * i2 < d2 * i1.
Now let us consider the original task with multiple customers c1, ... cn. The customer ck should have priority if for every other customer cl (l=0..n, l != k) this is true: dk * il < dl * ik.
Why is that?
For a customer, the only thing that matters is the sum of times of the preceding customers since his own time * importance score is fixed. So we will want to compare how much we will hold up the other customers as opposed to holding this single customer.
Do we have to recompute everything at every step?
If at every step, we have to compute this comparison for every pair of elements, we would be in the not-so-nice territory of O(n3). Polynomial complexity is manageable, however 3 in the exponent is rather annoying and it would be for the best if we could prevent it. For example by ordering the nodes.1 Can we do that?
Note: kudos to @รยקคгรђשค, I forgot that the division existed and got wee bit tangled in the indices.
So since the relation is an order, we can sort by it. Sort is O(n log(n)) and then we can just grab the pieces greedily in order.
1 By the distance / importance ratio.