7
$\begingroup$

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).

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\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 '11 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$ – Chandra Chekuri Dec 1 '11 at 21:24
  • $\begingroup$ updated my question; hopefully it's clearer now. $\endgroup$ – CAFxX Dec 8 '11 at 12:53
  • 1
    $\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$ – Suresh Venkat Dec 8 '11 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 '11 at 22:03
2
$\begingroup$

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

$\endgroup$
  • $\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 '11 at 16:15
  • $\begingroup$ Yep, sorry if the question wasn't clear enough. $\endgroup$ – CAFxX Nov 29 '11 at 8:19
  • $\begingroup$ no problem, it's my english that's bad :). $\endgroup$ – Gopi Nov 29 '11 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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