How to create objective function for time window violation?
OngoingHello,
I would like to create an objective for time window violation. I already asked this question before
for example as a simple model:
I have a graph with 6 nodes with 2 trucks
edges = [(1, 3, {'weight': 1}),(3, 1, {'weight': 1}),
(2, 3, {'weight': 2}),(3, 2, {'weight': 2}),
(4, 3, {'weight': 2}),(3, 4, {'weight': 2}),
(4, 5, {'weight': 2}),(5, 4, {'weight': 2}),
(4, 6, {'weight': 2}),(6, 4, {'weight': 2}),
(1, 5, {'weight': 4.9}),(5, 1, {'weight': 4.9}),
(2, 6, {'weight': 5.9}),(6, 2, {'weight': 5.9})]
truck 0 start point 1 to 5
truck 1 start point 2 to 6
group = {0: (1, 5), 1: (2, 6)}
I have a decision variable called x
x = {}
for edge in road_network.edges():
x[edge] = {}
for h, _ in group.items():
x[edge][h] = model.addVar(vtype=GRB.BINARY, name="{}".format("x" +str(edge)+str(h)))
based on some contain truck travels their shortest path and sometimes trucks travel a different path.
based on this graph:
truck0 shortest path is 1-5
truck1 shortest path is 2-6
after implementing constrain for the vehicle platooning problem. truck try to merge in point 3 and make a platoon at 3-4
I want to create a time violation objective function.
if minimize objective function the objective value will be 0
time violation = tracks travelling time - truck shortest path time.
if tracks travelling time >truck shortest path time that means time violation
Could you help me to build an objective function?
-
-
Gurobi Staff
Hi John,
Let me recap what I understood from your question.
- There are binary decision variables \(x_{jt}\) being equal to 1 if truck \(t\) traverses the edge \(j\) and 0, otherwise.
- For each truck \(t\), there is a known parameter \(p_t\), representing the shortest possible time it takes for truck \(t\) to travel from its origin node to the root node.
The travel time of truck \(t\) can be then represented as \(\sum_{j \in E} t_j x_{jt}\) where \(E\) is the edge set and \(t_j\) is the travelling time along the edge \(j\) (I guess "weight" in your code snippet represents the travel time associated with each edge).
You can then use Gurobi max_() general constraint helper function to model the objective function as \(\sum_t \max(\sum_{j \in E} t_j x_{jt} - p_t, 0)\), as below:
import gurobipy as gp
model = gp.Model()
x = model.addVars(num_edges, num_trucks, name="x")
y = model.addVars(num_trucks, name="y")
z = model.addVars(num_trucks, name="z")
model.addConstrs(
(y[i] == gp.quicksum(t[j] * x[j, i] for j in range(num_edges)) - p[i])
for i in range(num_trucks)
)
model.addConstrs(z[i] == gp.max_(y[i], 0) for i in range(num_trucks))
model.setObjective(y.sum())Please let us know if this does not answer your question.Best regards,Maliheh0 -
-
Hello Maliheh,
Thank you for your answer.I already have a model for the vehicle platoon problems with the objective minimize fuel cost. my task is to add a second objective to my model called minimizing time violation.
Both objectives are built by linear expression \[ gp.LinExpr() \]
After creating these two objective functions I need to use the epsilon constraint method to find the Pareto front.
I would like to create a second objective function(time violation) in a single function without separate constrain.
Code:saving_factor = 0.1
number_of_nodes = 6
node_list = []
for i in range(1,number_of_nodes+1):
node_list.append(i)
group = {0: (1, 5), 1: (2, 6)}
#group = {0:(1, 2), 1:(3, 4)}
graph = nx.DiGraph()
edges = [(1, 3, {'weight': 1}),(3, 1, {'weight': 1}),
(2, 3, {'weight': 2}),(3, 2, {'weight': 2}),
(4, 3, {'weight': 2}),(3, 4, {'weight': 2}),
(4, 5, {'weight': 2}),(5, 4, {'weight': 2}),
(4, 6, {'weight': 2}),(6, 4, {'weight': 2}),
(1, 5, {'weight': 4.9}),(5, 1, {'weight': 4.9}),
(2, 6, {'weight': 5.9}),(6, 2, {'weight': 5.9})]
speed = 1
graph.add_edges_from(edges)
road_network = graph
#shortest path time each truck = earliest_arrival_time_each_truck
earliest_arrival_time_each_truck={}
for h, locations in group.items():
earliest_arrival_time_each_truck[h] = nx.dijkstra_path_length(road_network, source=locations[0], target=locations[1])/speedMy First objective minimizes fuel cost:
objective_function_first_part = gp.LinExpr()
for edge in road_network.edges():
objective_function_first_part += road_network.get_edge_data(*edge)["weight"]*saving_factor * y[edge]
objective_function_second_part = gp.LinExpr()
for edge in road_network.edges():
for h, _ in group.items():
objective_function_second_part +=(1 - saving_factor) * road_network.get_edge_data(*edge)["weight"]*x[edge][h]
objective_function_main_first = objective_function_first_part + objective_function_second_partThe second objective function (time violation):
the travelling time of truck on each edge \[\begin{equation} x_ij^h * (d_ij^h/speed) \end{equation}\]objective_function_second_Ipart = gp.LinExpr()
for h,_ in group.items():
for e in road_network.edges():
objective_function_second_Ipart +=x[e][h]*(road_network.get_edge_data(*e)["weight"]/speed)My question is to help to complete this second objective.
How to subtract earliest_arrival_time_each_truck[h] from objective_function_second_Ipart?
the objective value of the second objective will be a time violation.
Based on the example code above: if the second objective minimizes the objective value will be = 0
if the second objective maximize the objective value will be = 0.2
I hope you understand my question0 -
-
-
Hi John,
Using your code snippet, let us define the total travel time for each truck as below:
total_travel_time_per_truck = {}
for h, _ in group.items():
total_travel_time_per_truck[h] = gp.LinExpr()
for e in road_network.edges():
total_travel_time_per_truck[h] += x[e][h] * (
road_network.get_edge_data(*e)["weight"] / speed
)For each truck \(h\), you have the parameter \(\texttt{earliest_arrival_time_each_truck[h]}\). Does your second objective function equal to the expression below?\[\sum_h \big(\texttt{total_travel_time_per_truck[h]} - \texttt{earliest_arrival_time_each_truck[h]}\big)\]If so, you can modify the above snippet as below:objective_function_second_Ipart = gp.LinExpr()
total_travel_time_per_truck = {}
for h, _ in group.items():
total_travel_time_per_truck[h] = gp.LinExpr()
for e in road_network.edges():
total_travel_time_per_truck[h] += x[e][h] * (
road_network.get_edge_data(*e)["weight"] / speed
)
objective_function_second_Ipart += (
total_travel_time_per_truck[h] - earliest_arrival_time_each_truck[h]
)If the above does not represent your second objective function, could you please clearly explain what \(\texttt{x[e][h]}\) represents in your code snippet and write the mathematical representation of your second objective function in terms of \(\texttt{x[e][h]}\) and \(\texttt{earliest_arrival_time_each_truck[h]}\)?Best regards,Maliheh0 -
-
Hello,
Thank you so much for your code that so helps full. your code is almost right for my model.
1. is that possible to a /[ gp.max_() \] in the objective function. on your first answer, you use max_() function in constraint. the formulatime_violation[i] = max(new_truck_route_path_lenght[i] / earliest_arrival_time_each_truck[i] - 1 , 0)
or
something like this I am not sureobjective_function_second_Ipart += max_(total_travel_time_per_truck[h] - earliest_arrival_time_each_truck[h],0)
2. I need to add waiting time to total_travel_time_per_truck. if time violation>0 = I need to add waiting time to the latest arrival time.
we assume that if trucks travel the shortest paths truck does not have waiting time.
waiting time means one truck wait for another truck at a merging point. in the example, truck 0 travel from 1 to 3 time take 1 min truck 1 travel from 2 to 3 take 2 min that means the truck 0 will wait for truck 1 for platoon at node 3 so waiting time {0:1,1:0}
second_objective = max((total travelling time[h]+waiting_time) - earliest_arrival_time_each_truck[h])
I need to find waiting time in the objective function too.
Thank you0 -
Please sign in to leave a comment.
Comments
4 comments