Time indexed based vehicle routing problem under given time budget

回答済み

RUNQIU Hu

• 2022年01月26日 09:11
• 編集済み

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

0

• 

  Mario Ruthmair

  Gurobi Staff

  • 2022年02月18日 14:30
  • 編集済み

  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,
  Mario

  0

サインインしてコメントを残してください。