<p>Your problem is the same as optimizing the total time, since you always have to spend <span class="math-container">$\sum_{i} d_i + s_i$</span>. The optimal solution is drive to the next resource, wait till the next time window that allows the resource to perform its function, let the resource perform its function and repeat.</p>

<p>I suggest you start with the following paper, and see if there are paper mentioning your version. Their problem is a strict generalization of yours. They have vehicle driver constraints. For example, regulations require the vehicle driver to rest after driving a number of hours.  </p>

<p><a href="https://doi.org/10.1007/s13676-012-0014-9" rel="nofollow noreferrer"><em>The minimum duration truck driver scheduling problem</em></a>, Goel, A. EURO J Transp Logist (2012) 1: 285. </p>

CC BY-SA 4.0
2019-04-22T19:33:41.947Z
2019-04-22T19:33:41.947Z
Chao Xu
<p>Suppose there are <span class="math-container">$n$</span> resources which can do some work. Each resource has a number of time windows: <span class="math-container">$tw_{i,k}=\{start_{i, k},stop_{i, k}\}$</span>, such that the resource can perform its functions only within these time windows.</p>

<p>There is a vehicle, which needs to drive to each resource in a <strong>fixed order</strong> and it takes <span class="math-container">$d_i$</span> time to drive from resource <span class="math-container">$i$</span> to resource <span class="math-container">$i+1$</span>. Each resource requires time <span class="math-container">$s_i$</span> to do its work.</p>

<p>If the vehicle arrives earlier than resource's time window start, it has to wait for <span class="math-container">$w_i$</span> units of time.</p>

<p>The vehicle starts at time <span class="math-container">$t_0$</span>, drives for <span class="math-container">$d_0$</span> units of time to the first resource, waits for <span class="math-container">$w_0$</span>, then the first resource performs some work for <span class="math-container">$s_0$</span> units and the the vehicle drives to the next resource.</p>

<p><a href="https://i.sstatic.net/RqfYA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/RqfYA.png" alt="Time diagram"></a></p>

<p>Given that the order of resources is fixed and <span class="math-container">$d_i, s_i, tw_{i, k}$</span> are constants I need to find vehicle's start time <span class="math-container">$t_0$</span>, which minimizes the total waiting time <span class="math-container">$w=\sum _n w_i$</span>, where <span class="math-container">$w_i=\min_k(\max\{0, tw_{i,k}|start-t_i\})$</span> and <span class="math-container">$(t_i+w_i,t_n+w_n+s_n)\subseteq tw_{i,k}$</span></p>

<p>Is there an efficient algorithm for this problem?  Has it been studied in the literature?</p>

<reference-request><optimization>
Vehicle scheduling
Max
# Vehicle scheduling

(Asked by: username_0 on 2019-04-20)

Suppose there are $n$ resources which can do some work. Each resource has a number of time windows: $tw\_{i,k}=\{start\_{i, k},stop\_{i, k}\}$, such that the resource can perform its functions only within these time windows.

There is a vehicle, which needs to drive to each resource in a **fixed order** and it takes $d\_i$ time to drive from resource $i$ to resource $i+1$. Each resource requires time $s\_i$ to do its work.

If the vehicle arrives earlier than resource's time window start, it has to wait for $w\_i$ units of time.

The vehicle starts at time $t\_0$, drives for $d\_0$ units of time to the first resource, waits for $w\_0$, then the first resource performs some work for $s\_0$ units and the the vehicle drives to the next resource.

[![Time diagram](https://i.sstatic.net/RqfYA.png)](https://i.sstatic.net/RqfYA.png)

Given that the order of resources is fixed and $d\_i, s\_i, tw\_{i, k}$ are constants I need to find vehicle's start time $t\_0$, which minimizes the total waiting time $w=\sum \_n w\_i$, where $w\_i=\min\_k(\max\{0, tw\_{i,k}|start-t\_i\})$ and $(t\_i+w\_i,t\_n+w\_n+s\_n)\subseteq tw\_{i,k}$

Is there an efficient algorithm for this problem? Has it been studied in the literature?

**Tags:** reference-request, optimization

---

## 1 answers

### Answer by username_1 on 2019-04-22. Score: 3

Your problem is the same as optimizing the total time, since you always have to spend $\sum\_{i} d\_i + s\_i$. The optimal solution is drive to the next resource, wait till the next time window that allows the resource to perform its function, let the resource perform its function and repeat.

I suggest you start with the following paper, and see if there are paper mentioning your version. Their problem is a strict generalization of yours. They have vehicle driver constraints. For example, regulations require the vehicle driver to rest after driving a number of hours.

[*The minimum duration truck driver scheduling problem*](https://doi.org/10.1007/s13676-012-0014-9), Goel, A. EURO J Transp Logist (2012) 1: 285.


---

