Time indexed based vehicle routing problem under given time budget
Answered
Hello,
I am modeling a problem of vehicle routing problem under a given time budget. Specifically, I discretized the time budget (e.g., 3 hours) into T intervals with equal length (e.g., 9 intervals, each interval is 20 minutes).
The truck starts from the depot and returns to the depot. It has to return to the depot before the last interval but does not need to return exactly at the last interval.
For example, if there are 3 stations (denoted as 1, 2, 3) and 1 depot (denoted as 0), the time budget is 10 intervals, each travel between any two stations takes 1 interval, then a possible scheme 0-1-2-3-0 would be:
t=0, station=0 --> t=1, station=1 --> t=2, station = 2 --> t=3, station = 3 --> t=4 --> station = 0
After t=4, the truck stays at the depot.
Now I am using binary variables x[`station_i, station_j`, time_interval_t] to represent truck starts to travel from station `i` to station `j` at time interval `t`. I could set
x[0(depot), `station_j,` 0] =1 and x[0(depot), `station_j`, `T`(budget)] =1 to constrain the departure and termination of the route to be the depot.
However, I don't know how to enable the possibility that the truck returns to the depot earlier than the budget and then stays at the depot, i.e.,
`x[0,0,t]=1` for all the t > t', where `x[i,0,t']=1` and ` i != 0`
It seems that this would require the returning interval `t'` at the depot to be another variable, which is used as an index of other variables, i.e., the index of variables becomes a variable.
Any ideas on the modeling of this problem would be appreciated!
Best,
Runqiu
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Runqiu,
Since you do not know the time interval when the vehicle returns to the depot, you need to leave it open. This means that you model the start of the vehicle and all intermediate stops with flow conservation constraints. Then, the only chance for the vehicle to end the tour is by going back to the depot in some time interval before T. The following constraints can be a starting point:
$$\sum_{j \neq 0} x[0,j,0] = 1$$
$$\sum_{i} x[i,j,t] = \sum_{k} x[j,k,t+1], \qquad \forall j \neq 0, \forall t = 1,\ldots,T-1$$
Instead of using index t+1 in the last set of constraints, you could of course use the actual travel time from j to k.
Best regards,
Mario0 -
Post is closed for comments.
Comments
2 comments