How to add waiting time to time window violation?
進行中Hello,
this is a continuation of my previous question. I want to create an objective function of time window violation for the vehicle platoon problems.
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})]
\[ min \ Z = \sum_h \sum_e x^h_{ij}(d_{ij}/v ) +w^h_i- s^h \]
h is trucks, s^h is the shortest path time of each truck, x^h_{ij} decision variable, v is speed
truck0 shortest path is 1-5 = 4.9 time
truck1 shortest path is 2-6 = 5.9 time
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)- earliest_arrival_time_each_truck[h]
I don't how to add waiting time to this objective please help me.
truck0 detour path is 1-3-4-5 = 5 time
truck1 detour path is 2-3-4-6 = 6 time
total time each truck= 11
w^h_i is 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}
step to find waiting time to objective function
- ensure trucks share any same edges p^h_{ij}
- find the merging point (in the example is 3).
- find max(reach the time of trucks at node merging point).
- change leaving time of each truck = max(reach time of trucks at node merging point).
After adding waiting time to the objective function expected output will be
truck0 detour path is 1-3-4-5 = 6 time
truck1 detour path is 2-3-4-6 = 6 time
total time each truck = 12
please help me how to add waiting time to objective function
Thank you
-
-
Gurobi Staff
Hi John,
Can you please give a detailed description of your vehicle routing/platooning problem?
Synchronization aspects are not easy to model in VRPs, so it is important to know the details before being able to suggest a modeling approach.Best regards,
Mario0 -
-
Hello Mario,
Thank you for your reply.
I have already explained my Vehicle platooning problem model in my previous question.I just want to create a second objective to my model called minimizing time violation. in this objective function, I need to add the waiting time of each truck to their travelling time. After that using epsilon constraint to find the Pareto front.
I prefer to create a model with waiting time something like in this paper.
Detailed description what is vehicle platooning problem you can see in this paper.
Thank you0 -
-
-
Hi John,
I saw your previous post but it involves only your code, not the problem description itself. From the code it is already difficult to extract the mathematical model, and it is even more difficult to extract the original problem definition.
Unfortunately, I have no access to this paper.
The question you have seems to be only related to the modeling part not to the code itself. It would be helpful if you would state the problem definition and your current mathematical model here. Then, we can see if we need additional variables and/or constraints to model your additional objective function.
Best regards,
Mario0 -
-
hello Mario,
I understand what you mean. currently, I have a mathematical model for a single objective vehicle platooning problem (minimize fuel cost).
c(e) = distance between edges i,j
Thank you
John Karippery0 -
-
-
Hi John,
Ok, now I think I understand the basic VPP, and with factor eta you can control the focus on platooning vs. individual shortest paths.
Still, it is not fully clear to me how this basic VPP is extended towards minimizing time window violation or minimizing waiting times. So, does each node in the network has a visiting time window associated? If trucks use the same edge in the network, do they all have to wait for each other at the first node of the edge and then jointly traverse the edge? That might not make sense since unnecessarily long waiting times might occur if a single truck arrives very late. So, it might make more sense to wait only for other trucks that are arriving soon (whatever "soon" actually means).
It is important that you first define the additional constraints in the problem definition before you try to formulate it as a mathematical model. Implementing the model in Python would be the third step.
Best regards,
Mario0 -
-
hello mario,
thank you for your reply. and I am so happy that you understand my model.I need to extend my model to minimize total time violations.
first I need to find platoon edges. ie if any truck shares the same edge. \(P_ij^(k,w)\) = Binary variable=1, if truck k and w drive as a platoon on edge \(e_ij\)
\(ST^k\) = shortest path time of each truck
- the maximum number of trucks in the platoon is equal to 5.
- find the truck that has max arrival time merging point i from the trucks origin point.( \( MT^k)\)
- the departure time of all trucks at platoon point i == last truck arrived at platoon( \( MT^k)\)
- waiting time of each truck = the departure time of truck at platoon point i - arrival time of truck platoon point i
- all truck reach their destination before the deadline. deadline of each truck is predefined ( \( TD^k)\)
The objective function for time violation for all trucks \(Min z = ∑_k(x_ij^k*t_ij +WT^k ) –ST^k\)
- Calculate travelling time of truck at edge ij \( t_ij=d_ij /v\)
I hope you understand constraints in mz model
0 -
-
-
Hi John,
This is a quite complex setup which is not trivial to model.
But there still seems to be something missing: You have an upper bound on the size of a platoon (5), but are the trucks forced to build a platoon? According to the objective function, they will always follow the shortest path and will never wait for another truck since that minimizes the travel time and leads to zero waiting times.Best regards,
Mario0 -
-
Hello Mario,
Yes upper bound on the size of a platoon <= 5not all trucks make platoons. based on this model if trucks have large distance differences in the shortest path and travelling distance (platoon path) then trucks decide to take the shortest path.
You can try with the graph above Modify the value 3-4,4-3 path distance to a greater value. the truck decided to take the shortest path.
#Constraint
for v in road_network.nodes():
for h, locations in group.items():
if locations[0] == v:
b = 1
elif locations[1] == v:
b = -1
else:
b = 0
model.addConstr(quicksum(x[edge][h] for edge in road_network.out_edges(v)) -
quicksum(x[edge][h] for edge in road_network.in_edges(v)) == b, name='flow_' + str(v) + "_" + str(h))
for edge in road_network.edges():
for h, locations in group.items():
model.addConstr(x[edge][h] <= y[edge])
you can try this code. all truck doesn't try to make platoon.
can you please help me? only this part is missing in my project. just add waiting time into the objective function. that is my request and I don't have mathematical modelling experience before.
I have already asked another question in the community based on this model.
Thank you
0 -
-
-
Hi John,
Please do not open any more threads that basically deal with the same issue. There are already 3 of them, and I just realized that you already had a long discussion with one of my colleagues. This is extremely inefficient!
What I tried to tell you is that the objective function minimizing the time violation does not make sense when you do not enforce platooning somehow. The trucks would never team up since this would lead to extra travel and waiting time. So, you need to define the problem appropriately before you can move to modeling and implementation.
Best regards,
Mario0 -
-
Hello Mario,
sorry for adding many questions. finally, I build a model for a time violation.
\(TA_i^h\) = arrival time of truck at node i
\(TD_i^h\) = departure time of truck at node i
\( TA_{o^h}^h = TD_{o^h}^h = 0 \) arrival time and departure time of origin node = 0
minimize time violation = sum of (arrival time of each truck - shortest arrival time of each truck )
\(TA_i^h = TD_{i-1}^h + d_{(i-1),i} / speed\) (to find arrival time of each truck h at node i = time of departure previous node \((i-1)\) of truck h + distance between node i,j divided by speed)\(TD_i^h = max[TA_i^H] \) (to find departure time of truck h at node i = max arrival time of all truck at node i )
that means minimize of time violation of truck is
\(MIN Z = \sum_k (TA_{D^h}^h - ST^h) \)based on the example graph above question.
truck0 travel 1-3-4-5
truck1 travel 2-3-4-5
arrival and departure time at origin point both truck = 0
here I explain step by step how my model work.
Please give me reply on how can I do this in gurobi.. I am 100% sure my model is right.. I kindly request you..0 -
-
-
Hi John,
Sorry, but there are still several open questions that need to be clarified first:
- Your description to model the arrival and departure time is not a valid mixed integer program. For example, you do not know the nodes i-1 and i for one particular truck, this is part of the decisions to make. Please take a closer look on how to model vehicle routing problems as mixed integer programs.
- Again, why should a truck team up with another to build a platoon when it is better for the truck to go the shortest path? Are there any incentives to build a platoon? Are the trucks forced to build a platoon? The objective function you propose will always lead to a solution where the trucks follow the shortest path.
Best regards,
Mario0 -
サインインしてコメントを残してください。
コメント
11件のコメント