The Travelling Librarian

I was thinking thinking about how libraries in the same council get books to each other. For instance, I can go into the City Library, and borrow books straight off the shelf. If I that particular library doesn't have the book I want, I can search through the catalogue of all the other connected libraries, and if one of them has it, I can put it on reserve, and through library magic, it'll be at the City Library for me to pick up next time (you get an email to tell you that it has arrived, so you don't have to keep going in to check whether it's there or not). Not just that, but if I borrowed a book that belonged to a connected library, I could still return it at the City Library, and it'd find its way back to its home library. I was wondering what method the library uses to pass books around. I'll probably end up asking ex-librarian extrodinaire Darren later, but I thought I'd try to solve the problem myself first.

So first we have to make some assumptions:
-lacking any data about user borrowing habits, let's just assume the worst case scenario: every library has books that it needs to give to each other library, and every library has books it requires from each other library.
-the truck(/van/car/rickshaw) has unlimited space, and so return trips to pick up an overflow of books are unneccesary.
-readers are impatient and they expect their books to arrive by at least the next working day(this may be the most unlikely assumption, but I'm making it because I think it makes sense. For instance, you could have a solution like "all books are shipped to Library A on Mondays, B on Tuesdays, C on Wednesdays, etc with a 'take yours pass the rest along' agreement" but that seems like a strange solution - though it might be efficient in terms of saving petrol and driver costs).
-the truck must return to its starting location at the end of each day (because that's where the driver has parked their car so that they can go home).
-the books are already sorted into their destinations, so sorting time doesn't need to be taken into account
-delivery is instantaneous (drop it down a chute or something), so that doesn't need to be taken into account.
-all the transportation is done after closing time, so you don't have to take into account a worse-worst case in which people are constantly queuing up reservations from the library furthest away to the library you're currently at (if any reservations are made after closing time, they are queued for the next day).

The obvious solution would be for each library to have a truck, and make deliveries at the end of the night to each of the other libraries. This is really inefficient though, as you need n trucks for n libraries and they each make n trips, so you end up with n^2 trips. Plus having to pay for n trucks and pay n drivers.

n trucks
n^2 arrows

The next solution I could think of involved one truck that made a circular trip picking up books along the way, dropping the books off at the last destination, and then circling back and dropping off all the other books along the way. This solution can partially take into account load limits, as you can drop off books at intermediate libraries while you're picking them up, so you can release some of your load. It's a bit like an elevator algorithm.'

1 truck
2(n - 1) arrows

The last solution I came up with featured two trucks, starting at opposite ends. They would travel towards each other, only picking up books for libraries they hadn't yet passed.

Truck 1 would pick up all books at Library A. At Library B, it would drop off any books from A destined for B, and only pick up books for library C, D or E.

Truck 2 would pick up all books at Library E. At Library D, it would drop off books from E destined for D, and only pick up books for library C, B or A.

At Library C, they would both drop off books destined for C, and Truck 1 would only pick up books for D or E, and Truck 2 would only pick up books for A or B. Timewise, this is faster than the second solution, but it requires 2 trucks, rather than one.

2 trucks
2n arrows


I'll ask Darren later and update this with what he says libraries actually do.