exupero's blog
RSSApps

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:

Average number of accessible busesNumber of departed buses0123456789100102030405060708090100

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

Average number of accessible busesNumber of departed buses01020304050607080901000102030405060708090100

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

Average number of accessible busesNumber of departed buses01234567891011121314151617180102030405060708090100

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

Average number of accessible busesNumber of departed buses01234567891011121314150102030405060708090100

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:

Average number of accessible busesNumber of departed buses012345678910111213141516171819202122232425262728293031323334350102030405060708090100

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))
Average number of accessible busesNumber of departed buses0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960610102030405060708090100

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:

Average number of accessible busesNumber of departed buses0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566670102030405060708090100

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.