Vehicle scheduling

Question

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.

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?

Answer 1

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, Goel, A. EURO J Transp Logist (2012) 1: 285.