Scheduling Problem

[Filipe Matos]

Hello, 

I am trying to solve a vehicle and crew scheduling problem. The problem itself corresponds to assign vehicles and people to a set of shifts (trips) that are strictly timetabled. In order to get familiar with OR-Tools I have simplified my problem to only assign vehicles to the trips but I am having some trouble. To begin with I am using the employee scheduling example as my approach also using the example at: https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py

Some problems I already have: 
  -> How can I constrain my vehicles to not be assigned for two trips that may overlap? The trips have different starting and ending times (as they can be from different routes, so they are not necessarily sequential)

Thank you 

[Filipe Matos]

I have tried to add intervals to each vehicle that cannot overlap and adding the AddNoOverlap but now the there is no feasible solution.

for vehicle_id in all_vehicles:

    intervals = []

    for trip in trips.itertuples():

        duration = model.NewIntVar(0,120,"Trip_Duration_%i_%i" % (vehicle_id,trip.Index))

        shifts[vehicle_id,trip.Index] = model.NewBoolVar('v_%i_trip_%s_%s_%i' % (vehicle_id,trip.start_location,trip.end_location,trip.start_time))

        intervals.append(model.NewIntervalVar(trip.start_time,duration,trip.end_time,'interval_%i_%i' % (vehicle_id,trip.Index)))

    shifts_intervals.append(intervals)

#Bus cannot make two trips simultaneously

for vehicle_id in all_vehicles:

    model.AddNoOverlap(shifts_intervals[vehicle_id])

    model.AddNoOverlap(shifts_intervals[0])

[Laurent Perron]

Why don't you start with a simple approach.

If shift1 and shift2 overlaps.

  for all workers a:

    model.AddBoolOr(assign(a, shift1).Not(), assign(a, shift2).Not())

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--Laurent

[Filipe Matos]

Thanks for the suggestion Laurent. I am now trying to implement that but I don't understant the command assign(), shouldn't it be a list with my shift assigned BoolVar?? Moreover the AddBoolOr only accepts one argument not two as you mentioned.  

However would be nice to learn to work with the NoOverlap method for this situation as it will be useful as I have several shifts.

Thanks, 

Filipe

[Laurent Perron]

Sorry, AddBoolOr([ .. ])

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--Laurent

[Filipe Matos]

Thank you Laurent, that solve the problem :) 

Now I have a problem with the transition between shifts. I need to associate a cost for some of the transition times (in my case when the Bus travels from one terminal to another without passengers (deadhead trip) which is a bit to implement as I cannot access the ordered positive shifts assignments. 

[Laurent Perron]

Please have a look at that example:

https://github.com/google/or-tools/blob/stable/examples/contrib/scheduling_with_transitions_sat.py

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le jeu. 28 févr. 2019 à 15:29, Filipe Matos <fm1...@gmail.com> a écrit :

Thank you Laurent, that solve the problem :) 

Now I have a problem with the transition between shifts. I need to associate a cost for some of the transition times (in my case when the Bus travels from one terminal to another without passengers (deadhead trip) which is a bit to implement as I cannot access the ordered positive shifts assignments. 

--

[Filipe Matos]

Thank you Laurent for the suggestion. I have now tried to implement that approach to my case but I easily run out of memory whereas before this was not a issue at all. Here is the sub-code I have implemented:

I have 70 trips and 30 vehicles in total

switch_literals = []

for vehicle_id in all_vehicles:

    arcs = []

    vehicle_tasks_rank = v_tasks_rank[vehicle_id]

    for trip_x in trips.itertuples():

        # Initial arc from the dummy node (0) to a task.

        start_lit = model.NewBoolVar('')

        arcs.append([0, trip_x.Index + 1, start_lit])

        # If this task is the first, set both rank and start to 0.

        model.Add(vehicle_tasks_rank[trip_x.Index] == 0).OnlyEnforceIf(start_lit)

        # Final arc from an arc to the dummy node.

        arcs.append([trip_x.Index + 1, 0, model.NewBoolVar('')])

        # Self arc if the task is not performed.

        arcs.append([trip_x.Index + 1, trip_x.Index + 1, shifts[vehicle_id,trip_x.Index].Not()])

        model.Add(vehicle_tasks_rank[trip_x.Index] == -1).OnlyEnforceIf(

        shifts[vehicle_id,trip_x.Index].Not())

        for trip_y in trips.itertuples() :

            if trip_x == trip_y:

                continue

            lit = model.NewBoolVar('%i follows %i' % (trip_x.Index, trip_y.Index))

            arcs.append([trip_x.Index + 1, trip_y.Index + 1, lit])

            model.AddImplication(lit, shifts[vehicle_id,trip_x.Index])

            model.AddImplication(lit, shifts[vehicle_id,trip_y.Index])

            # Maintain rank incrementally.

            model.Add(vehicle_tasks_rank[trip_y.Index] == vehicle_tasks_rank[trip_x.Index] + 1).OnlyEnforceIf(lit)

            # Compute the transition time if task j is the successor of task i.

            switch_literals.append(lit*100)#deadhead_times[trip_x.Index,trip_y.Index])

model.AddCircuit(arcs)

[Filipe Matos]

Just to add some info I am getting the following error: 

terminate called after throwing an instance of 'std::bad_alloc'

  what():  std::bad_alloc

Aborted (core dumped)

[Laurent Perron]

Yes, memory is exhausted.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Filipe Matos]

Do you have any ideia why is this happening from the above code? Because it only get's so much memory when I add the circuit constraint

[Filipe Matos]

Okay I haven't managed to solve the memory issue when I try to minimize the transitions. However without trying to minimize the transitions I still cannot get the right trip assigned ranking. Here is the code I am using 

switch_literals = []

for vehicle_id in all_vehicles:

    arcs = []

    for trip_x in trips.itertuples():

        # Initial arc from the dummy node (0) to a task.

        start_lit = model.NewBoolVar('vehicle %i' % vehicle_id)

        arcs.append([0, trip_x.Index + 1, start_lit])

        # If this task is the first, set both rank to 0.

        model.Add(v_tasks_rank[vehicle_id,trip_x.Index] == 0).OnlyEnforceIf(start_lit)

        # Final arc from an arc to the dummy node.

        arcs.append([trip_x.Index + 1, 0, model.NewBoolVar('')])

        # Self arc if the task is not performed.

        arcs.append([trip_x.Index + 1, trip_x.Index + 1, shifts[vehicle_id,trip_x.Index].Not()])

        model.Add(v_tasks_rank[vehicle_id,trip_x.Index] == -1).OnlyEnforceIf(

        shifts[vehicle_id,trip_x.Index].Not())

        for trip_y in trips.itertuples():

            if trip_x == trip_y:

                continue

            lit = model.NewBoolVar('%i follows %i' % (trip_x.Index, trip_y.Index))

            arcs.append([trip_x.Index + 1, trip_y.Index + 1, lit])

            model.AddImplication(lit, shifts[vehicle_id,trip_x.Index])

            model.AddImplication(lit, shifts[vehicle_id,trip_y.Index])

            # Maintain rank incrementally.

            model.Add(v_tasks_rank[vehicle_id,trip_y.Index] == v_tasks_rank[vehicle_id,trip_x.Index] + 1).OnlyEnforceIf(lit)

            # Compute the transition time if task j is the successor of task i.

            if(trip_x.end_location != trip_y.start_location):

                switch_literals.append(lit)

    model.AddCircuit(arcs)

[Laurent Perron]

You need to link the start time of the tasks with the circuit.

Otherwise, any solution is valid.

Then, you can reuse the boolean variables of the arcs for something else, like maintaining the rank of variables.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Filipe Matos]

Thank you Laurent, with that hint I successfully got the right ranking :). However now (and with the previous code shown as well) I am forcing the model to use all the vehicles where without the circuit constraint the model minimizes the used vehicles well. Any ideia why is this happening? 

switch_literals = []

for vehicle_id in all_vehicles:

    arcs = []

    for trip_x in trips.itertuples():

        # Initial arc from the dummy node (0) to a task.

        start_lit = model.NewBoolVar('vehicle %i' % vehicle_id)

        model.AddImplication(start_lit,shifts[vehicle_id,trip_x.Index])

        arcs.append([0, trip_x.Index + 1, start_lit])

        # If this task is the first, set both rank  and start_time to 0.

        model.Add(v_tasks_rank[vehicle_id,trip_x.Index] == 0).OnlyEnforceIf(start_lit)

        #model.Add(v_starts[vehicle_id,trip_x] == trip_x.start_time).OnlyEnforceIf(start_lit)

        # Final arc

        #from an arc to the dummy node.

        arcs.append([trip_x.Index + 1, 0, model.NewBoolVar('')])

        # Self arc if the task is not performed.

        arcs.append([trip_x.Index + 1, trip_x.Index + 1, shifts[vehicle_id,trip_x.Index].Not()])

        model.Add(v_tasks_rank[vehicle_id,trip_x.Index] == -1).OnlyEnforceIf(

        shifts[vehicle_id,trip_x.Index].Not())

        for trip_y in trips.itertuples():

            if trip_x == trip_y:

                continue

            lit = model.NewBoolVar('%i follows %i' % (trip_x.Index, trip_y.Index))

            arcs.append([trip_x.Index + 1, trip_y.Index + 1, lit])

            model.AddImplication(lit, shifts[vehicle_id,trip_x.Index])

            model.AddImplication(lit, shifts[vehicle_id,trip_y.Index])

            # Maintain rank incrementally.

            model.Add(v_tasks_rank[vehicle_id,trip_y.Index] == v_tasks_rank[vehicle_id,trip_x.Index] + 1).OnlyEnforceIf(lit)

            model.Add(v_starts[vehicle_id,trip_y.Index] > v_starts[vehicle_id,trip_x.Index]).OnlyEnforceIf(lit)

            # Compute the transition time if task j is the successor of task i.

            if(trip_x.end_location != trip_y.start_location):

                switch_literals.append(lit)#deadhead_times[trip_x.Index,trip_y.Index])

    model.AddCircuit(arcs) 

[Filipe Matos]

For me it seems it always forces the circuit to have a beginning in a trip with the start_lit. If this is the case how could I solve it? 

[Laurent Perron]

You need self looping arcs on optional visits. Please read the python reference manual for CP-SAT on GitHub. 

Le mer. 6 mars 2019 à 20:35, Filipe Matos <fm1...@gmail.com> a écrit :

For me it seems it always forces the circuit to have a beginning in a trip with the start_lit. If this is the case how could I solve it? 

--

[Filipe Matos]

Thank you :) I now have a full working prototype. However now I am running scalability tests and ran into severe problems: 

1º If I use several CPUS in parallel by calling parameters.num_search_workers = X, the RAM memory used is X times of the one with a single worker. 

2º If I set parameters.num_search_workers = 1, the problem takes much more time to solve then using 4 cores (the ones I have), i.e takes at least 10x times more time, while still using a enormous ammount of memory. 

All of this is cause only by the piece of code that we have been discussing recently which is below

deadheads = []

#Ficticious trip

for vehicle_id in all_vehicles:

    for trip in range(n_trips):

        model.AddBoolOr([shifts[vehicle_id,n_trips].Not(),shifts[vehicle_id,trip].Not()])

#Count all the deadhead trips

for vehicle_id in all_vehicles:

    arcs = []

    for trip_x in trips.itertuples():

        

        # Initial arc from the dummy node (0) to a task.

        start_lit = model.NewBoolVar('vehicle %i' % vehicle_id)

        model.AddImplication(start_lit,shifts[vehicle_id,trip_x.Index])# - not necessary

        arcs.append([0, trip_x.Index + 1, start_lit])

        

        # If this task is the first, set both rank  and start_time to 0.

        model.Add(v_tasks_rank[vehicle_id,trip_x.Index] == 0).OnlyEnforceIf(start_lit)

        

        # Final arc from an arc to the dummy node.

        arcs.append([trip_x.Index + 1, 0, model.NewBoolVar('')])

        

        # Self arc if the task is not performed.

        arcs.append([trip_x.Index + 1, trip_x.Index + 1, shifts[vehicle_id,trip_x.Index].Not()])

        model.Add(v_tasks_rank[vehicle_id,trip_x.Index] == -1).OnlyEnforceIf(

        shifts[vehicle_id,trip_x.Index].Not())

        for trip_y in trips.itertuples():

            if trip_x == trip_y:

                continue

            lit = model.NewBoolVar('%i follows %i' % (trip_x.Index, trip_y.Index))

            arcs.append([trip_x.Index + 1, trip_y.Index + 1, lit])

            model.AddImplication(lit, shifts[vehicle_id,trip_x.Index])

            model.AddImplication(lit, shifts[vehicle_id,trip_y.Index])

            # Maintain rank incrementally.

            model.Add(v_tasks_rank[vehicle_id,trip_y.Index] == v_tasks_rank[vehicle_id,trip_x.Index] + 1).OnlyEnforceIf(lit)

            model.Add(v_starts[vehicle_id,trip_y.Index] > v_starts[vehicle_id,trip_x.Index]).OnlyEnforceIf(lit)

            

            # Compute the transition time if task j is the successor of task i.

            if(trip_x.end_location != trip_y.start_location):

                deadheads.append(lit)#deadhead_times[trip_x.Index,trip_y.Index])

    model.AddCircuit(arcs)

[Filipe Matos]

Is there a way to use other heuristic methods such as tabu search, column generation, local search? The way I have implemented it just uses too much memory to become useful in a real world application

[Laurent Perron]

You can implement Large Neighborhood Search easily.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le lun. 11 mars 2019 à 18:07, Filipe Matos <fm1...@gmail.com> a écrit :

Is there a way to use other heuristic methods such as tabu search, column generation, local search? The way I have implemented it just uses too much memory to become useful in a real world application

--

[Filipe Matos]

Thank you for the suggestion. Do you have any tip to begin implementing the large neighborhood search using the OR-Tools python API? I just find information on it using C++

[Laurent Perron]

Encapsulate the method that creates the model in a function.

Once you have a solution, build the cp_model.

Store the number of constraints, 

Start looping:

  - compute the set of variables to freeze, 

  - resize the list of constraints of the model to the stored number of constraints

  - for each variable frozen, add a constraints var == value in solution.

  - solve

  - if an better solution is found, update the reference solution

Possible improvement:

  - Add solution hinting on non frozen variables to the value in the solution (search or-tools-discuss on how to to that)

Another way to solve the model would be to decompose, usually geographically in smaller problems, then solve each sub-model independently.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Filipe Matos]

Thank you for the suggestion Laurent :) . I have been trying to implement that first approach but I am running into a question: How do I remove a constraint from the model? I guess that's what the second point is about but I don't see how

[Laurent Perron]

https://developers.google.com/protocol-buffers/docs/reference/python-generated#fields

on the CpModelProto inside the CpModel class.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mer. 13 mars 2019 à 11:16, Filipe Matos <fm1...@gmail.com> a écrit :

Thank you for the suggestion Laurent :) . I have been trying to implement that first approach but I am running into a question: How do I remove a constraint from the model? I guess that's what the second point is about but I don't see how

--

[Filipe Matos]

Thank you Laurent. I have successfully implemented the LNS as you suggested. However I now notice something weird. When using LNS I don't want to use model.Minimize as at this point I have already minimized what I could optimally. Therefore I just use the cp_solver method Solve(). Weirdly, when I remove the minimize() command the solver takes much more time to get a feasible solution than when using minimize. Why is this happen? I basically just want a feasible solution. 

[Laurent Perron]

No, you launch LNS on a feasible solution to try to improve it.

You need to minimize the objective to reach a local minimum.

--

--Laurent

[Filipe Matos]

I think I was not very clear sorry. What I observed is that get a feasible solution (without asking the model to minimize any objective) is slower than when I ask for a solution that minimizes an objective with a model that begins with the optimal objective already. 

[Filipe Matos]

In my code for the vehicle and crew scheduling problem I have the following restrictions which allow me to assign one vehicle per driver. 

for driver in range(max_crew):

       for trip_x in trips.itertuples():

         for trip_y in trips.itertuples():

           if trip_x.vehicle_id != trip_y.vehicle_id:

             model.AddBoolOr([crew_shifts[driver,trip_x.Index].Not(),crew_shifts[driver,trip_y.Index].Not()])

However as we  increase the max_crew and the number of trips this becomes extremely memory hungry as it creates millions of BoolVars becoming completely unfeasible. Any suggestion for a memory friendly alternative?

[Laurent Perron]

decompose the problem :-)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

De : Filipe Matos <fm1...@gmail.com>
Date : mar. 14 mai 2019 à 16:56
À : or-tools-discuss

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/19d5f62c-c932-4952-a4f4-9e3bc112d071%40googlegroups.com.