[Question, Not an issue] Early shift completion of vehicles causing dropping of stations

[aravindsuresh93]

Hi James Marca,

Sorry for raising this as an issue. I read your amazing blog on tsp multi days (which was better than any google doc available online) and thus came to your github profile. Could you please help me with the below problem that im facing?

Im using the below code for my vrp. Im trying to achieve the following

• A vehicle should work only during its shift timings and a max of 11 hours (660 minutes)
• A station should be visited only during its alloted time windows
• A station should not be visited during break times
• A mandatory break of 30 mins should be given to all vehicles The problem im facing is that, say a trucks shift is from 6am to 5pm. The truck does trips until like 10,10:30AM and does not do any more trips after that even though it has time till 5pm. Due to this some stations for example that can be visited from 2pm to 6pm window are being dropped.

Thank you so much :)

def add_time_dimension(routing, manager, data, time_evaluator_index):
    time_dim = 'Time'

    routing.SetArcCostEvaluatorOfAllVehicles(time_evaluator_index)
    routing.AddDimension( time_evaluator_index, 60, 3000, False, time_dim)
    time_dimension = routing.GetDimensionOrDie(time_dim)
    time_dimension.SetGlobalSpanCostCoefficient(10)

    """
    Vehicle Level TW
    """
    for vehicle_id in range(manager.GetNumberOfVehicles()):
        start_index = routing.Start(vehicle_id)
        end_index = routing.End(vehicle_id)
        time_dimension.CumulVar(start_index).SetRange(data['vehicle_tw'][vehicle_id][0], data['vehicle_tw'][vehicle_id][0])
        time_dimension.CumulVar(end_index).SetRange(data['vehicle_tw'][vehicle_id][0] , data['vehicle_tw'][vehicle_id][1])
        routing.solver().Add(time_dimension.CumulVar(end_index) - time_dimension.CumulVar(start_index) <= 660)

    """
    Station level TW
    """
    for location_idx, time_window in enumerate(data['time_windows']):
        if data['station_type'][location_idx] == "d":
            continue

        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

        slack_var = time_dimension.SlackVar(index)
        routing.solver().Add(slack_var == 0)
        routing.AddToAssignment(slack_var)

    """
    Vehicle Breaks
    """
    node_visit_transit = [0] * routing.Size()
    print('ssssss',routing.Size())
    break_intervals = {}
    for v in range(manager.GetNumberOfVehicles()):
        break_intervals[v] = [
            routing.solver().FixedDurationIntervalVar(
                data['vehicle_tw'][v][0] + 240, 
                data['vehicle_tw'][v][1], 
                30, 
                False,  
                f'Break-{v}')
        ]
        time_dimension.SetBreakIntervalsOfVehicle(break_intervals[v], v, node_visit_transit)

    """
    Station Breaks
    """
    for e, sb in enumerate(data['station_breaks']):
        if not len(sb):
            continue
        index = manager.NodeToIndex(e)
        time_dimension.CumulVar(index).RemoveInterval(sb[0], sb[1])

[jmarca]

Hi. Respectfully, I am a consultant and answer these sorts of questions for a living. I will occasionally help for free on the OR Tools mailing list, but that is based on my time and interest in the question.

I did see your original message on the mailing list, but answering properly would take a bit of work and given my current schedule, I am not inclined to do that work for free. Ironically, the less busy my work is, the more likely I am to answer harder questions like this for free.

My wild guess is that you are not setting the maximum time for the dimension properly, or that the slack is not large enough to allow the vehicle to get back to work. But those are just guesses without having looked at your code in any detail.

Of course, if you would like to hire us to do this work, let me know and I'll get back to you directly.

Otherwise, I've made a note of this question, and the next time I have time to write a blog post maybe I'll work on your problem.

Good luck with this,

James

[aravindsuresh93]

Understood James, no worries. Thank you so much for your reply :)

Thanks Aravind