search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.1k stars 2.11k forks source link

Wait time #765

Closed GuyBenhaim closed 5 years ago

GuyBenhaim commented 6 years ago

Hello, Probably addresses in the past, but I couldn't find this. How can I assign a wait duration for each Node, so solver considers waiting/service/visit time at each Node? (not just the travel time)

Maybe adding that time to the "Time" Dimension from each Node to the target Node? Maybe duplicate all the Nodes (with 0 cost to travel to the duplicated node) to emulate such wait times? Other? Thx

Mizux commented 6 years ago

Hi, simply add 'service time" to the transit callback cf the python example cvrptw.py Here I define a service time according to the capacity of each node: src: https://github.com/google/or-tools/blob/master/examples/python/cvrptw.py#L182 and then I add it to the transit function src: https://github.com/google/or-tools/blob/master/examples/python/cvrptw.py#L208

note: I add the service to the output edge i.e. Transit(A -> B): ServiceTime(A) + TravelTime(A -> B) so my Time Windows define an "arrival time constraint at node N".

GuyBenhaim commented 5 years ago

So, we get the departure time by adding the "service time" at that Node to the arrival time?

And the arrival time at the next Node will automatically include it - since you used: _total_time[from_node][to_node] = int( service_time(data, **from_node**) + travel_time(data, from_node, to_node))

right?

Mizux commented 5 years ago

Simply put. We use Time Windows on Arrival time thus time dimension add constraints on node arrival. We compute the transit cost as the sum of the travel time and the service time.

Computing Departure time is more tricky since it will also depends on waiting time aka SlackVar. ArrivalTime(B) = ArrivalTime(A) + Transit(A, B) + WaitingTime(A) and Tansit(A, B) == ServiceTime(A) + TravelTime(A,B) == TotalTime(A,B) so you may define DepartureTime as DepartureTime(A) = ArrivalTime(A) + ServiceTime(A) + WaitingTime(A)

note: ArrivalTime is the CumulVar() from the solver point of view note: WaitTime is the SlackVar() from the solver point of view note: CumulVar and SlackVar may be range interval note: SlackVar range is dependent of the CumulVar value but what we return can be see as the union of all range of SlackVar for all value of CumulVar.

GuyBenhaim commented 5 years ago

Thx. Isn't SlackVar really the maximum wait time allowed at a certain Node, that would still enable to meet the Arrival time constraints of all the following Nodes?

Also, when Solver() runs -- searching through a certain Vehicle/Route -- is it possible to get the service order of a certain Node? That is: Query the Solver() using the NodeIndex of the last Node in the search, and get its relative order, in the sequence of preceding Nodes, served before it along that route? (of course, as the search progresses the order of the Nodes increases)

GuyBenhaim commented 5 years ago

Can you please comment re the second question? (hoping the question was clear ...)

willwill2will54 commented 5 years ago

I'd hate to revive a 'dead' issue, but the issue here is also one I face, and the links above appear to be broken.

lperron commented 5 years ago

https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrptw.py

Mizux commented 4 years ago

@willwill2will54 Did you get all the answers you were looking for ?

wagjixiang commented 2 years ago

Simply put. We use Time Windows on Arrival time thus time dimension add constraints on node arrival. We compute the transit cost as the sum of the travel time and the service time.

Computing Departure time is more tricky since it will also depends on waiting time aka SlackVar. ArrivalTime(B) = ArrivalTime(A) + Transit(A, B) + WaitingTime(A) and Tansit(A, B) == ServiceTime(A) + TravelTime(A,B) == TotalTime(A,B) so you may define DepartureTime as DepartureTime(A) = ArrivalTime(A) + ServiceTime(A) + WaitingTime(A)

note: ArrivalTime is the CumulVar() from the solver point of view note: WaitTime is the SlackVar() from the solver point of view note: CumulVar and SlackVar may be range interval note: SlackVar range is dependent of the CumulVar value but what we return can be see as the union of all range of SlackVar for all value of CumulVar.

hello Mizux, I have a problem, as you say, we define a waiting time for each node, but I want to define the sum of vehicle waiting time, how to solve this kind of problem?

lperron commented 2 years ago

Please do not revive issues that are years old :-) Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le lun. 19 sept. 2022 à 12:07, wagjixiang @.***> a écrit :

Simply put. We use Time Windows on Arrival time thus time dimension add constraints on node arrival. We compute the transit cost as the sum of the travel time and the service time.

Computing Departure time is more tricky since it will also depends on waiting time aka SlackVar. ArrivalTime(B) = ArrivalTime(A) + Transit(A, B) + WaitingTime(A) and Tansit(A, B) == ServiceTime(A) + TravelTime(A,B) == TotalTime(A,B) so you may define DepartureTime as DepartureTime(A) = ArrivalTime(A) + ServiceTime(A) + WaitingTime(A)

note: ArrivalTime is the CumulVar() from the solver point of view note: WaitTime is the SlackVar() from the solver point of view note: CumulVar and SlackVar may be range interval note: SlackVar range is dependent of the CumulVar value but what we return can be see as the union of all range of SlackVar for all value of CumulVar.

hello Mizux, I have a problem, as you say, we define a waiting time for each node, but I want to define the sum of vehicle waiting time, how to solve this kind of problem?

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/765#issuecomment-1250820930, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3PLGBN3BSC4KTZZEULV7A3OBANCNFSM4FLRFTIQ . You are receiving this because you modified the open/close state.Message ID: @.***>

wagjixiang commented 2 years ago

Please do not revive issues that are years old :-) Laurent Perron | Operations Research | @. | (33) 1 42 68 53 00 Le lun. 19 sept. 2022 à 12:07, wagjixiang @.> a écrit : … Simply put. We use Time Windows on Arrival time thus time dimension add constraints on node arrival. We compute the transit cost as the sum of the travel time and the service time. Computing Departure time is more tricky since it will also depends on waiting time aka SlackVar. ArrivalTime(B) = ArrivalTime(A) + Transit(A, B) + WaitingTime(A) and Tansit(A, B) == ServiceTime(A) + TravelTime(A,B) == TotalTime(A,B) so you may define DepartureTime as DepartureTime(A) = ArrivalTime(A) + ServiceTime(A) + WaitingTime(A) note: ArrivalTime is the CumulVar() from the solver point of view note: WaitTime is the SlackVar() from the solver point of view note: CumulVar and SlackVar may be range interval note: SlackVar range is dependent of the CumulVar value but what we return can be see as the union of all range of SlackVar for all value of CumulVar. hello Mizux, I have a problem, as you say, we define a waiting time for each node, but I want to define the sum of vehicle waiting time, how to solve this kind of problem? — Reply to this email directly, view it on GitHub <#765 (comment)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3PLGBN3BSC4KTZZEULV7A3OBANCNFSM4FLRFTIQ . You are receiving this because you modified the open/close state.Message ID: @.***>

I'm sorry to take up your time! It may be simple for you, but i can't solve it by myself. So can you tell me how to solve this problem?
problem: limit the sum of vehicle waiting time. Thank you very much again!