Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a bit general, but is there a name to this type of problem? It looks like a directed graph traversal problem, but you have multiple paths going on, and timing may be important.

You operate a public library system with multiple branches. Every day, people check out and return materials. Library users can return materials at any branch. Additionally, library users can place a hold on an item and ask to pick it up at any branch. Essentially, on any given day you have items that need to be delivered between library branches.

You have hired a set number of drivers to move materials between locations. Assume that the transit time between branches is known and time-invariant, the carrying capacity of the vehicles is unlimited, drivers are on for a set amount of time each day, and the drivers can start and end at any library branch. Given a list of what must be moved, is there an optimal set of delivery routes that minimizes driving time?

share|improve this question
Okay, so to clarify the problem: Given an edge-weighted graph $G = (V, E), w : E \rightarrow \mathbb{R}^+$, a set of ordered pairs of vertices $\{(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n) \}$, and a positive integer $m$, we want to find $m$ paths through $G$ such that: (1) For each pair $(v_i, w_i)$, one of the paths visits $v_i$ before $w_i$. (2) The maximum of the $m$ path lengths is minimal with respect to property (1). Correct? –  Daniel McLaury Sep 4 '11 at 20:39
My graph theory is not very strong, but the description that you give appears to be accurate. Property (1) being that the maximum of the $m$ (weighted) path lengths is bounded above by a constant. –  Michael Chen Sep 5 '11 at 1:57

1 Answer 1

up vote 0 down vote accepted

To keep things simple, I'll assume that any book that goes onto a truck must be delivered to its destination by that truck (and not, say, switched from one truck to another).
Let ${\cal M}$ be the set of ordered pairs of branches $(a,b)$ such that at least one book has to go from branch $a$ to branch $b$. Since the carrying capacity is unlimited, you just have to make sure that if $(a,b) \in {\cal M}$, there is a truck that is at $b$ at some time after it is at $a$. Let $\cal R$ be the set of all possible routes for trucks (i.e. lists of branches that could be visited in the given order within the time allotted). We may assume a branch can occur at most twice in a route. Let $c(R)$ be the total driving time for route $R$, and $P(R)$ the set of $(a,b) \in \cal M$ such that the first $a$ occurs before the last $b$ in route $R$ (so this route could deliver books from $a$ to $b$). Then what you have is an optimal set-covering problem: find a subset $\cal S$ of $\cal R$ with cardinality at most $d$ (the number of drivers) that minimizes $\sum_{R \in {\cal S}} c(R)$ subject to the constraint that $\bigcup_{R \in {\cal S}} P(R) = \cal M$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.