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

<p>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)</p>

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

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

CC BY-SA 3.0
2011-12-01T17:02:50.720Z
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?
CAFxX
CC BY-SA 3.0
2011-12-01T21:24:30.173Z
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.
Chandra Chekuri
CC BY-SA 3.0
2011-12-08T12:53:18.480Z
updated my question; hopefully it's clearer now.
CAFxX
CC BY-SA 3.0
2011-12-08T18:52:29.860Z
@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)
Suresh Venkat
CC BY-SA 3.0
2011-12-08T22:03:09.913Z
@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.
CAFxX
CC BY-SA 3.0
2011-11-28T16:05:23.280Z
2011-11-28T16:05:23.280Z
Chandra Chekuri
<p>In Spaa'11 there was a paper about what was called the <a href="http://dl.acm.org/citation.cfm?doid=1989493.1989518" rel="nofollow">Car-Sharing problem</a>, where what they handover is the car :).</p>

CC BY-SA 3.0
2011-11-28T16:15:08.020Z
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).
Gopi
CC BY-SA 3.0
2011-11-29T08:19:03.577Z
Yep, sorry if the question wasn't clear enough.
CAFxX
CC BY-SA 3.0
2011-11-29T09:05:00.397Z
no problem, it's my english that's bad :).
Gopi
CC BY-SA 3.0
2011-11-27T19:57:41.033Z
2011-11-28T16:13:52.343Z
2011-11-28T16:13:52.343Z
Gopi
<p>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 <em>handovers</em> between multiple vehicles, i.e. the ability to drop off an item from a vehicle and let another one pick it up. </p>

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

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

<p>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. </p>

<hr>

<p>note: the term <em>handover</em> 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$ <em>hands over</em> object $O_1$ to $V_2$ in $P_1$". </p>

<hr>

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

<ds.algorithms><reference-request><graph-theory><graph-algorithms><optimization>
Capacitated multiple vehicle routing problem with handovers
CAFxX
# Capacitated multiple vehicle routing problem with handovers

(Asked by: username_0 on 2011-11-27)

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

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms, optimization


---

## 2 answers

### Answer by username_1 on 2011-11-28. Score: 6

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

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: updated my question; hopefully it's clearer now.  
> **username_2**: @username_0 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)  
> **username_0**: @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.  

---

### Answer by username_3 on 2011-11-27. Score: 2

In Spaa'11 there was a paper about what was called the [Car-Sharing problem](http://dl.acm.org/citation.cfm?doid=1989493.1989518), where what they handover is the car :).

> **Comments:**
> **username_3**: 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).  
> **username_0**: Yep, sorry if the question wasn't clear enough.  
> **username_3**: no problem, it's my english that's bad :).  

---

