Bus barn dequeueing

The other day someone posed a question to me about how to dequeue buses from a bus barn to maximize the number of accessible buses. I don't have a particularly clever approach, but I can simulate a few strategies and measure their differences.

Let's consider three arrangements: flat parking in which every bus is accessible, deep parking in which all the buses are parked in a single queue, and a block arrangement with several moderately deep queues. These are easy to model using nested lists to represent individual queues:

(defn flat [n]
  (vec (repeat n [1])))

(flat 10)

[[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]]

(defn deep [n]
  [(vec (repeat n 1))])

(deep 10)

[[1 1 1 1 1 1 1 1 1 1]]

Creating a block arrangement is more complicated, since we might not have as many buses as an N by M grid allows:

(defn block [n queue-count]
  (let [depth (/ n queue-count)
        more (- n (* queue-count (Math/floor depth)))]
    (vec (for [i (range queue-count)]
           (vec (for [j (range (Math/ceil depth))]
                  (if (or (zero? more) (pos? j) (< i more))
                    1
                    0)))))))

(block 10 3)

[[1 1 1 1] [0 1 1 1] [0 1 1 1]]

Zeros represent parking spaces without a bus.

A bus is accessible if it is first in its queue, or if it's ahead of the first bus in a neighboring queue, since it's parallel parked and can wiggle free:

(defn side-exit? [position neighbor-queue]
  (when (seq neighbor-queue)
    (let [i (.indexOf neighbor-queue 1)]
      (or (= -1 i) ; empty queue
          (< position i)))))

(defn accessible [queues]
  (for [[i queue] (map-indexed vector queues)
        :let [head (.indexOf queue 1)]
        [position value] (map-indexed vector queue)
        :when (and (= 1 value)
                   (or (= position head)
                       (side-exit? position (get queues (dec i)))
                       (side-exit? position (get queues (inc i)))))]
    [i position]))

To simulate buses departing in random order, we'll create a deterministic version of Clojure's rand-nth, one that takes a random number generator:

(defn rand-nth [rng coll]
  (let [index (.nextInt rng (count coll))]
    (nth coll index)))

We'll drain the queues by randomly removing on accessible bus until no buses remain, and we'll return a list of how many buses were accessible after each departure:

(defn drain [queues choose]
  (loop [queues queues
         counts []]
    (if-let [coords (seq (accessible queues))]
      (recur (assoc-in queues (choose coords) 0)
             (conj counts (count coords)))
      counts)))

(let [rng (java.util.Random. 0)]
  (drain (deep 10) #(rand-nth rng %)))

[1 1 1 1 1 1 1 1 1 1]

With one hundred buses in a single deep queue, only one bus is accessible at each iteration:

In a wide and flat arrangement, in which each bus has its own parking space, every bus that hasn't departed is accessible:

Arranged in 10 queues, with buses departing from random lanes, the number of accessible buses becomes more interesting:

The general behavior can be modeled by averaging over many runs:

The curve smooths into one that plateaus at 14 or 15 buses typically being accessible.

Let's see if we can improve on this. Rather than taking from each queue equally, we should prioritize buses that will allow buses deeper in the pack to exit via a neighboring lane. Thinking of lanes in groups of three, we want to dequeue buses from the middle of group more often, since it makes buses from both side lanes accessible.

To implement this, here's a version of rand-nth that chooses items randomly by given weights:

(defn rand-nth-weighted [rng coll weights]
  (let [marks (reductions + weights)
        cutoff (.nextInt rng (last marks))
        index (count (take-while #(<= % cutoff) marks))]
    (nth coll index)))

To prefer buses depart from the middle of three queues, we can provide a weighing function that weighs middle queues, say, ten times more than non-middle queues:

(defn prefer-middle-of-3 [[queue-number]]
  (if (= 1 (mod queue-number 3))
    10
    1))

(let [rng (java.util.Random. 0)]
  (drain (block 10 3)
         #(rand-nth-weighted rng % (map prefer-middle-of-3 %))))

[3 3 3 5 6 5 4 3 2 1]

Let's see how it compares to uniform departures:

That's a big improvement. At its peak it all but triples the number of buses that can be extracted.

To find the theoretical maximum with this strategy, we can skip the randomness and always choose a bus from the middle lane of three, using a choose function like this:

(defn middle-of-3-first [coords]
  (->> coords
       (sort-by prefer-middle-of-3 >)
       first))

There are three flat spots on the left side of the curve, one at the base and two more on the way up. These are caused by the first bus departing from queues 2, 5, and 8, which don't make any additional buses accessible because the buses next to them could already pull out. The plateau on the right end of the curve happens because we have ten lanes, which aren't evenly divisible by 3. As a bus pull out of the ninth lane, it makes another bus accessible in the tenth lane, which keeps the number of buses that can pull out the same.

Let's see what happens when we use 12 lanes, which is evenly divisible by 3:

With this approach, once a third of the buses leave the other two-thirds become accessible.

Of course, we wouldn't want to always take one of the middle-of-3 buses, since the whole point of making other buses accessible is to occasionally get one of them out, but this shows the theoretical best case. Odds are one doesn't need so many buses to be accessible, only certain buses, which could be strategically located toward the front of queues.

If you have other strategies to experiment with, email me.