I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e. the ability to drop off an item from a vehicle and let another one pick it up.

Put otherwise, we could say we are allowing an item to be transported (sequentially) by more than one vehicle, e.g.:

  • at time $T^u$ vehicle $V_1$ takes the item from the pick-up location $P^u$
  • at time $T^d_1 \geq T^u$ vehicle $V_1$ drops it off at an intermediate point $P_1$
  • at time $T^u_1 \geq T^d_1$ vehicle $V_2$ picks it up from the intermediate point $P_1$
  • at time $T^d_2 \geq T^u_1$ vehicle $V_2$ drops it off at the intermediate point $P_2$
  • ...
  • at time $T^u_{n-1} \geq T^d_{n-1}$ vehicle $V_n$ picks it up from intermediate point $P_{n-1}$
  • at time $T^d \geq T^u_{n-1}$ vehicle $V_n$ delivers it to the final destination $P^d$.

In the VRP overviews I found this variant is not mentioned so I was wondering if anybody knew if it has been investigated at all.

note: the term handover is something I came up with to describe the problem: it may not be the one commonly used to denote this kind of variant. The intended meaning, w.r.t. the example above is that e.g. when vehicle $V_1$ drops off the object $O_1$ at $P_1$ and $V_2$ picks it up we could say that "$V_1$ hands over object $O_1$ to $V_2$ in $P_1$".

update: Reworded to clarify that I'm talking about multiple vehicles (it was just kind-of implicit in the original wording).


2 Answers 2


These problems are studied but with different terminology such as drop-off. See below and references therein.

The Finite Capacity Dial-A-Ride Problem, M. Charikar and B. Raghavachari, in Proceedings of the 39th Annual IEEE Conference on Foundations of Computer Science (1998)

Algorithms for Capacitated Vehicle Routing M. Charikar, S. Khuller and B. Raghavachari, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998).

Dial a Ride from k-forest ACM Transactions on Algorithms, 6(2):2010 Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan, and R. Ravi

  • $\begingroup$ Indeed it looks like the common terminology is "drop-off", but aren't those paper referring to the problem of a single vehicle? What about the case of multiple vehicles? $\endgroup$
    – CAFxX
    Dec 1, 2011 at 17:02
  • $\begingroup$ Sure but you need to say more about your problem regarding multiple vehicles. It is not clear to me what you want from the references. $\endgroup$ Dec 1, 2011 at 21:24
  • $\begingroup$ updated my question; hopefully it's clearer now. $\endgroup$
    – CAFxX
    Dec 8, 2011 at 12:53
  • 2
    $\begingroup$ @CAFxX if you wish to change the problem, you should clarify, or maybe even ask a different question. The answers here did answer the question you originally asked. At the very least, you should explain in your question via an update how the question has changed (since otherwise the answers don't make sense to a new visitor) $\endgroup$ Dec 8, 2011 at 18:52
  • $\begingroup$ @SureshVenkat the question is the same - at least, this is what I wanted to know in the first place. My bad if I wasn't able to convey it clearly. $\endgroup$
    – CAFxX
    Dec 8, 2011 at 22:03

In Spaa'11 there was a paper about what was called the Car-Sharing problem, where what they handover is the car :).

  • $\begingroup$ After reading the other answer it seems I have misunderstood the problem since what they handover here is the vehicle. I leave it since it might still be useful (for the references). $\endgroup$
    – Gopi
    Nov 28, 2011 at 16:15
  • $\begingroup$ Yep, sorry if the question wasn't clear enough. $\endgroup$
    – CAFxX
    Nov 29, 2011 at 8:19
  • $\begingroup$ no problem, it's my english that's bad :). $\endgroup$
    – Gopi
    Nov 29, 2011 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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