• Gurobi Staff

Hi John,

1. The decision variables are defined correctly. Alternatively, you can define them as below to remove the outer $$\texttt{for}$$ loop. To represent the set $$T$$ in the paper which is the set of equidistant time periods, let us use $$\texttt{time_steps}$$ instead of $$\texttt{time}$$ where $$\texttt{time_steps}$$ = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

# x_k_t_ij = 1 if truck k travels between time steps t and t+1 along the edge (i, j)x = model.addVars(trucks, time_steps, edges, vtype=GRB.BINARY, name="x")# delta_ijdelta = model.addVars(time_steps, edges, vtype=GRB.BINARY, name="delta")

2. The objective function, shown below, is not modelled correctly and needs to be re-written completely.

$\sum_t \sum_{ij \in e} c_{t, ij} = \sum_t \sum_{ij \in e} f_{ij} \big(\sum_k x^k_{t, ij} - \eta \delta_{t, ij} (\sum_k x^k_{t, ij} -1)\big)$

# Objective functionobjective = gurobipy.quicksum(    distance[(i, j)]    * (        x.sum("*", t, i, j)        - fuel_saving * delta[t, i, j] * (x.sum("*", t, i, j) - 1)    )    for t in time_steps    for (i, j) in edges)model.setObjective(objective, sense=GRB.MINIMIZE)
3. Constraints need to be re-written as well.
# Constraint 3.1model.addConstrs(    (        x.sum(k, t, "*", i) == x.sum(k, t + 1, i, "*")        for k in trucks        for t in time_steps[:-1]        for (i, _) in edges    ),    name="constr_3_1",)# Constraint 3.2model.addConstrs(    (x.sum(k, 0, vehicles_origin[k], "*") == 1 for k in trucks),    name="constr_3_2",)# Constraint 3.3T = len(time_steps) - 1model.addConstrs(    (x.sum(k, T, "*", vehicles_destination[k]) == 1 for k in trucks),     name="constr_3_3",)# Constraint 3.5model.addConstrs(    (delta[t, i, j] <= x.sum("*", t, i, j) for t in time_steps for (i, j) in edges),    name=constr_3_5")

Please be aware that given the current input, the model is infeasible. The origin node for truck 2 is 8 and the destination node is 1. However, in the set of edges, there is no edge leaving node 8 and there is no possible route for truck 2 to travel from node 8 to node 1.

Best regards,

Maliheh

Hello Maliheh,

In my logic, my graph(input) is bi-directional edges. that means there is a route from 8 to 1.
But I change input edges and distance like this.

edges = [(i, j) for i in nodes for j in nodes if i != j]distance = {(i, j): random.randint(5, 10) for i, j in edges}

time input I add to this model because I need to a constrain that ensure each truck reach their destination before the deadline.

Now I am so confused because of time_steps input.

t_max = [80,120]  #deadline of each truck

so now I write code like that remove time input and add t_ij parameter

time_ij = {}for i,j in edges:    time_ij[i,j] = distance[i,j]/v for truck in trucks:     mdl.addConstr(x.sum("*", t, i, j)*time_ij[i,j]for i,j in edges) <= t_max[truck])

Thank you

• Gurobi Staff

Hi John,

Sure, the graph can be bi-directional. We just need to make sure that the model knows about it :) What you did sounds alright to me.

Defining $$t_{ij}$$ as the travelling time from node $$i$$ to node $$j$$ and $$t^k_{\mathrm{max}}$$ as the total possible travelling time for truck $$k$$, I assume the new constraint is:

$\sum_{ij} t_{ij} \sum_{t} x^k_{t, ij} \leq t^k_{\mathrm{max}}, ~~ \forall k$.

You can then implement it as:

model.addConstrs(    (        gurobipy.quicksum(x.sum(k, "*", i, j) * time[(i, j)] for (i, j) in edges)        <= t_max[k]         for k in trucks    ),    name="constr_travelling_time",)

Best regards,

Maliheh

Hello,

constrain for travelling time doesn't make any changes to my model. something I miss in my model

for example, if track1 max time is 20 and start node 1 and end node is 5.

possible path  1: {(1,2):5, (2,3):5, (3,4):6, (4,5):5}

2:{(1,2):5, (2,3):5, (3,5):8}

path 1 total time is 21

path 2 total time is 18

select path 2 using time constrain:

moreover, I change  for getting complete graph

 edges = [(i, j) for i in nodes for j in nodes if j>i]

after changing to complete graph model doesn't have any solution.

Thank you.

• Gurobi Staff

Hi John,

One idea to debug your model is to write it into an LP format using the Model.write() method. You can then open the file using any text editor to figure out what it is missing in the model.

Best regards,

Maliheh

Hi Maliheh,

After so much reading and a lot of tries, I thought of covert this constrain to the objective function.

Currently, I have 2 objectives for my model I need to use the epsilon constrain method to optimize the solution

use networkx package for creating graph

minimize total time of all truck in system

\begin{align} min = \sum_h x^h_{i,j} \sum_e t_{i,j} \end{align}

h = truck

objective_function_main_second = quicksum(x[edge][h] * quicksum(time[edge] for edge in road_network.edges())for h, locations in group.items()) model.setObjective(objective_function_main_second, GRB.MINIMIZE)

I modified variables x and y

x = {}y = {}for edge in road_network.edges():x[edge] = {}y[edge] = model.addVar(vtype=GRB.BINARY)for h, locations in group.items():x[edge][h] = model.addVar(vtype=GRB.BINARY)

Could you please check my objective function is correct?