Optimal ice cream cone filling process on a conveyor belt with arbitrary distributed cones [closed]

Question

I have an algorithmic question that arose from a real-life production problem.

Setting. Empty ice cream cones are randomly distributed across a moving conveyor belt. The batcher equipment has a hosepipe that can move above the belt within some limits (considerably smaller than the length of the belt). In order to fill an empty cone the hosepipe is placed right above the cone and locked on it for some time until the filling process is over. So this means that the cone must remain in the hosepipe reach area while the filling is in progress. After it's done the hosepipe can move on to another cone. Clearly, if the speed is not big enough and filling process takes some time the system would miss some of the cones if cones are many enough and inconveniently placed. So the problem is to fill as much cones as possible by scheduling the order of filling beforehand.

Formally we have as input:

• U — speed of the belt

• V — speed of the hosepipe

• W — width of the belt

• L — length of the belt

• P — length of the hosepipe reach area

• T — time of the filling process

• cones — array of coordinates of cones on the belt

An output is ideally the list of cones to fill successively that ensures the maximum number of filled cones. Or at least an estimation of the maximal number of cones that are possible to fill.

Any suggestions on how to tackle this problem would be greatly appreciated!

Answer 1

Optimal cone-filling with a forward-only dispenser

Let's suppose the conveyor belt moves right-to-left. Below I'll describe a way to formulate and solve the problem in a way that fills the maximum possible number of cones, under the assumption that the dispenser never moves to the left faster than the conveyor belt does. For n cones, the basic algorithm has a very loose (see later) upper bound of O(n^3) time and O(n^2) space -- this should be feasible for up to 1000 cones or so. If you have more cones than this, you can break them into blocks of at most this size and simply process each block one after the other. There's also a way to relax the never-move-left-fast restriction somewhat, and thus potentially fill more cones, without the whole problem becoming exponential-time -- I'll describe this later.

Let's suppose that all cones have positive x co-ordinates, and that the hosepipe reach area, which initially extends from x = 0 leftwards to x = -P, moves rightwards over the cones, which themselves remain stationary. So at time t, the hosepipe reach area will extend from x = U * t leftwards to x = U * t - P. When describing the position of the dispenser, I'll always use the same (that is, absolute) co-ordinate system; we'll ensure that it remains a valid position (inside the hosepipe reach area) by ensuring that at any time t, its x location is between U * t - P and U * t. Notice that a (time, cone ID) pair is enough to completely determine the positions of both the hosepipe reach area and the dispenser, if we interpret it to mean that the dispenser is directly over the given cone at the given time. (Later this will help in simplifying the description of the system state.) Finally, I'll call any motion of the dispenser that does not decrease its absolute x co-ord (this includes any backward motion, relative to its enclosure, that is lower in speed than U, and also no motion at all) a "forward" motion, and any that does a "backward" motion.

Dynamic programming formulation

Sort the cones by increasing x position, breaking ties arbitrarily. Let (x_i, y_i) be the position of the ith cone in this sorted order.

Let e(i) be the earliest time at which we could feasibly position the dispenser over cone i if it was the only cone we cared about, and the dispenser was already "waiting" at the correct vertical position (namely, y_i) at the rightmost end of the hosepipe reach area: this is simply x_i / U.

Let m(i, j) be the time needed to move the dispenser from cone i to cone j, assuming that it's possible to do so without having to wait for either one to "scroll into view": this can easily be calculated for any pair (i, j) from their co-ordinates and the speeds V and U (this remains true even if the dispenser can simultaneously move at arbitrary speeds V_x and V_y in the x and y directions).

Now we come to the function that is the key to efficient solution of this problem:

Let f(i, j) be the earliest time at which we could finish filling cone i such that we have filled exactly j cones so far (including this one, so 1 <= j <= i), or infinity if this is not feasible. Let g(i, j) be a helper function that is defined the same way, except that we allow the last cone-filling step to push the dispenser too far to the left (you'll see why in a minute). We can calculate g(i, j) and, more importantly, f(i, j) as follows:

g(i, j) = max(e(i), minimum of f(k, j-1) + m(k, i) over all k s.t. j <= k < i) + T
f(i, j) = IF U * g(i, j) - P <= x_i THEN g(i, j) ELSE infinity

What a mess! Let's go part by part.

The f(k, j-1) + m(k, i) term is the smallest amount of time it takes to fill j-1 cones, ending with cone k, then move the dispenser to cone i. The max(e(i), ...) around this ensures that, if the movement implied by the above term would cause the dispenser to move too far to the right (i.e., to some x-co-ord > U * t), it won't be taken. Instead, we'll move the dispenser to (U * t, y_i) -- that is, to the correct y co-ord for cone i and as far right as possible -- then wait for cone i to scroll in (and thus appear directly below the dispenser) at time e(i). Regardless of which of these actions we take, it then takes a further T time units to fill cone i.

(Technically, the above calculation assumes that, if it's possible to move the dispenser to (x_i, y_i) by some given time t, then it's also possible to move it to (U * t < x_i, y_i) by that same time at the latest. But since our starting x location is <= U * t, the only way this could fail to hold is if the function describing the time needed to move between 2 given points violates the Triangle Inequality -- something which doesn't happen when the hosepipe moves relative to its enclosure at a constant speed V, or independently in 2 directions at constant speeds V_x and V_y, or indeed uses any non-crazy drive system.)

What about the left edge of the hosepipe reach area? U * g(i, j) - P is the position of the left edge of the this area at the time g(i, j). Since that time is the earliest possible time that we could have finished the task of filling j cones, the last of which is cone i, that expression gives the leftmost possible position that the left edge of the hosepipe reach area could be in when the task is completed. So if that position is still to the left of x_i, it means we can feasibly fill cone i after those j-1 earlier cones -- but if it isn't, we know that trying to do so will force the dispenser too far left (this might happen while trying to move to cone i, or while filling it -- it doesn't matter). So in the latter case we slam the time cost associated with task f(i, j) all the way to infinity, guaranteeing it won't be used as part of the solution to any larger subproblem.

Time and space usage

Calculating any particular f(i, j) value takes O(n) time, so calculating all O(n^2) of these values takes O(n^3) time. However in practice, we will hardly ever need to consider all possible values of k less than i in the above minimum. In addition to ensuring that the sequence of movements implied by f(i, j) remains feasible, the max(e(i), ...) is also the key to a big practical speedup: as soon as we happen on a k that causes the e(i) term to "kick in" (become the larger of the two terms compared by max()), it will remain the best feasible option -- since any subsequent k that purports to allow a faster completion of the task necessarily involves pushing the dispenser too far to the right in the final step. That means that we don't need to try any of those other k values: e(i) is indeed the real minimum.

If all we wanted to calculate was the minimum time needed to fill some given number of cones, we could actually do it in just O(n) space, by making use of the fact that when calculating f(i, j), we only ever access previous values of f() having second argument equal to j-1. But since what we actually really want is the sequence of actions corresponding to such a minimum time, we will need to record a table of predecessors p[i][j], and this does require O(n^2) space.

Pseudocode

Sort cone[1 .. n] by increasing x co-ord.
Compute e[i] for all 1 <= i <= n.
Set f[i][1] = e[i] + T for all 1 <= i <= n.
Set f[i][j] = infinity for all 1 <= i <= n, 2 <= j <= i.
maxCones = 0.
bestTime = infinity.

# Compute f(i, j) for all i, j.
For j from 2 up to n:
    For i from j up to n:
        g = infinity.             # Best time for f(i, j) so far.
        For k from j up to i-1:
            z = f[k][j-1] + m(k, i) + T.
            If z < g:
                p[i][j] = k.
                If z < e[i] + T:
                    g = e[i] + T.
                    Break out of innermost (k) loop.
                Else:
                    g = z.

        If U * g - P <= cone[i].x:
            f[i][j] = g.
            If maxCones < j or (maxCones == j and g < bestTime):
                maxCones = j.     # New record!
                bestI = i.
                bestTime = g.
        Else:
            f[i][j] = infinity.

# Trace back through p[][] to find the corresponding action sequence.
For j from maxCones down to 1:
    fill[j] = bestI.
    bestI = p[bestI][j].

After running this, maxCones will contain the maximum number of cones that can feasibly be filled, and if this is >= 1, then fill[1] through fill[maxCones] will contain a corresponding sequence of maxCone cone IDs (positions in the sorted sequence) to fill, and the total time needed will be in bestTime.

Possible enhancements

The above algorithm only solves the problem optimally under the restriction that the dispenser never moves backwards "too fast". This could be quite restrictive in practice: For example, a pattern of cones like the following

X X X X


 X X X X

will cause the dispenser make a long vertical move between every cone it fills (assuming it's able to fill all of them). Filling several cones in the same row and only then moving to the other row would save a lot of time.

The difficulty in solving the problem optimally without the restriction above is that it starts looking very much like certain NP-hard problems, like the Euclidean TSP problem. I don't have time to look for a formal reduction, but I'm confident that the unrestricted version of your problem is NP-hard, so the best we can hope to do with a polynomial-time algorithm is to look for good heuristics. To that end:

The DP solution above basically finds, for each cone i, the best way to fill j cones in total, ending at cone i and using only other cones to its left. We can solve a slightly more general problem by breaking the sorted sequence of cones into contiguous blocks of b cones, and then finding, for each cone i, the best way to fill j cones in total that ends at cone i and uses only the cones that are either (a) in an earlier block (these cones must be to the left of i) or (b) in the same block as i (these cones aren't, necessarily). The only solutions overlooked by this approach are those that would require us to fill a cone in some block and afterwards fill a cone in an earlier block (this includes, in particular, all solutions where we fill a cone in some block, a cone in a different block, and then another cone in the first block again -- at least one of the two moves between blocks must be a move to a previous block).

Obviously, if we pick b = n then this will find the overall optimum (in a million years), but b doesn't need to be anywhere near this large to get an optimal solution. Using a variation of the O(n^2*2^n) DP algorithm for solving TSP to assist in computing within-block optimal paths, choosing b = 10, say, would be quite feasible.

One more suggestion is that instead of fixing the block size at exactly b, cones could first be more intelligently split into blocks of size at most b, that is, in such a way that the (unknown) optimal solution seldom needs to fill a cone in a previous block. In fact, provided that it's possible to heuristically score breakpoint "quality" (e.g. by using the minimum distance between any pair of points in 2 blocks), calculating a blocking pattern that maximises the score can easily be done in O(bn) time, using a (different) DP!