3
$\begingroup$

I want to figure out what problem I'm dealing with so I can move in the right direction of research. I'm still at the very beginning of formulating the problem. What I've done so far is figure out just enough to understand how little I know about optimization problems. So for me it is also about the bascis.

The problem is probably a combination of several.

The minimization goal: I want to minimize the total time $t$, or the costs, for the process.

Details:

  • There is one vehicle.
  • The vehicle has limited capacity.
  • The vehicle moves from point / node to another to complete a task. So I think that nodes are equivalent to tasks in this problem?
  • There is a distance between nodes. This is part of the costs, since this means travel time.
  • A task $T_n$ takes a certain amount of time $t_T$, e.g. $t_{T_n}=3\text{minutes}$.
  • Material is consumed per task.
  • The vehicle starts fully loaded and can recharge the material at any station.
  • There are at least two stations.

Why I am not making progress in my research: The complexity comes from the fact that a task has to happen twice in one place. Let's call them two types of tasks, "prepare" and "finish".

  • Two task types. Both have to be done per location.
  • There must be a certain amount of time between "prepare" $T_{pn}$ and "finish" $T_{fn}$, e.g. 10 minutes.
  • However, only a certain amount of time may elapse, not more, e.g. $t_{max} = 30\text{minutes}$.

I had the feeling that this is about time windows, but what I find difficult is the fact that the task must be done twice in the same place or same node, but then with the different time windows. That means there are dependencies and they specify the starting points. So the start of $T_{f1}$ will be determined by $T_{p1}$. At the same time I do not really care when a time window starts to begin with $T_{p1}$, work just has to be done. It is OK, when $T_{p5}$ is done before $T_{p1}$, this is flexible. And also, when $T_{p1..7}$ have been done, $T_{f1..7}$ can be done afterwards sequentially but do not have to. Tasks just need to be fulfilled within the time frame that is made up by $T_{pn}$.

So I think the only hard dependency is the point of time $tp$ after $T_{pn}$ has been done:

So, $T_{fn}^{tp}$ lies within $[ ( T_{pn}^{tp} + 10\text{minutes} ) , ( T_{pn}^{tp} + 30\text{minutes} ) ]$

ps. Sorry, but I am not very sure about how to express all of this in the correct mathematical way w.r.t. optimization problems, this is something I would like to catch on in the near future, as soon as I know in which direction I should head now.

So by what I know so far this is some kind of vehicle routing problem VRP with time windows TW. But TW is not very strict, so is this more about scheduling?

And when I would start to implement a solution, what tools could I use for that?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ So you want to find a single route to serve all tasks in the shortest amount of time? Then you have a resource constrained shortest path problem. That is often solved by a labeling algorithm, which is a dynamic programming approach. $\endgroup$
    – gmn
    Sep 23, 2022 at 9:03
  • $\begingroup$ Why don't you just aggregate those two tasks as one? $\endgroup$
    – overboxed
    Sep 24, 2022 at 0:40

3 Answers 3

Reset to default
4
$\begingroup$

I think that the keyword you are looking for is "temporal constraints". Here are a few articles related to this topic:

  • "Combined vehicle routing and scheduling with temporal precedence and synchronization constraints" (Bredström et Rönnqvist, 2008) DOI
  • "The vehicle routing problem with time windows and temporal dependencies" (Dohn et al., 2011) DOI
  • "A constraint-programming based decomposition method for the Generalised Workforce Scheduling and Routing Problem (GWSRP)" (Bourreau et al., 2020) DOI
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Adding to that: "An exact solution method for a rich helicopter flight scheduling problem arising in offshore oil and gas logistics" (Nafstad et al., 2021) handles a minimum time requirement between two visits in a route in a labeling algorithm. sciencedirect.com/science/article/pii/S0305054820302756 $\endgroup$
    – gmn
    Sep 23, 2022 at 12:09
2
$\begingroup$

If you want to view the problem as a VRP, it might help to clone all the nodes. Rather than having a single node $N_j$ for task $j,$ you have node $N_j^p$ for the preparation portion of the task and node $N_j^f$ for the finishing portion of the task. You will also end up cloning arcs, so that arc $(N_i, N_j)$ becomes $(N_i^h,N_j^k)$ for all combinations of $h,k\in \lbrace p,f\rbrace.$ (You may also want to include arcs $N_j^p \rightarrow N_j^f$ with distance/travel time 0 to allow the vehicle to stick around after a prep task until the time window for the finish task opens.) Preventing a visit to the finish copy of a node before the visit to the prep copy is handled by the time window constraints.

Improve this answer
$\endgroup$
2
$\begingroup$

You have a vehicle routing problem (VRP) here. Because you only have one vehicle, the problem can be reduced to a traveling salesman problem (TSP). Every Vehicle routing is an assignment problem. Basically, VRP is about the combination of assignments and knapsack. You assign a vehicle for each node and a knapsack for the commodity carried for each vehicle. From your description, besides Time Windows there are two keywords that you might perhaps want do some little digging into, which are dependent VRP and Multi-Trip VRP.

For the tools, you might want to consider approximate technique (meta or heuristics) because VRP is NP-hard.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Additional keyword: Multi-depot, Split-delivery $\endgroup$
    – overboxed
    Sep 23, 2022 at 15:51

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.