Invalid Vehicle use with time_window and capacity at the same time

[SkyTik]

I'm trying to solve a problem have capacity of vehicles and delivery of jobs, combine with time_windows

Here is my code:

def get_time_matrix(distance_matrix, speed):
    time_matrix = [
        [0 for _ in range(len(distance_matrix))] for _ in range(len(distance_matrix))
    ]

    for i in range(len(distance_matrix)):
        for j in range(len(distance_matrix[i])):
            time_matrix[i][j] = int(distance_matrix[i][j] / speed)
            time_matrix[j][i] = int(distance_matrix[j][i] / speed)

    return time_matrix

def transform_time_window_to_minute(time_window):
    def time_to_minutes(time_str):
        time_obj = datetime.strptime(time_str, "%H:%M").time()
        return time_obj.hour * 60 + time_obj.minute

    return [time_to_minutes(time_window[0]), time_to_minutes(time_window[1])]

def create_jobs(nodes):
    jobs = []
    for i, node in enumerate(nodes):
        location = i + 1

        time_windows = node["time_windows"]
        time_windows_minute = [
            transform_time_window_to_minute(time_window) for time_window in time_windows
        ]

        job = vroom.Job(
            id=location,
            location=location,
            delivery=vroom.Amount([node["weight"]]),
            time_windows=[
                vroom.TimeWindow(time_window_minute[0], time_window_minute[1])
                for time_window_minute in time_windows_minute
            ],
            service=node.get("waiting_time", 0),
        )
        jobs.append(job)
    return jobs

# create list of vehicles
def create_vehicles(vehicles, max_travel_time, max_stop_point, time_window):
    return [
        vroom.Vehicle(
            id=vehicle["id"],
            start=0,
            end=0,
            max_travel_time=max_travel_time,
            time_window=vroom.TimeWindow(time_window[0], time_window[1]),
            max_tasks=max_stop_point,
            capacity=[vehicle["capacity"]],
        )
        for vehicle in vehicles
    ]

def handle(event):
    start_time = time.time()
    depot = event["depot"]
    depot_time_window = event["depot_time_window"]
    transport_mode = event["transport_mode"]
    nodes = event["nodes"]
    max_stop_point = event["max_stop_point"]
    max_distance = event["max_distance"]
    vehicles = event["vehicles"]

    depot_time_windows_minute = transform_time_window_to_minute(depot_time_window)

    jobs = create_jobs(nodes)
    max_travel_time = int(max_distance / 333)
    pyvroom_vehicles = create_vehicles(
        vehicles, max_travel_time, max_stop_point, depot_time_windows_minute
    )

    locations = [[node["lat"], node["lng"]] for node in nodes]
    locations.insert(0, depot)
    distance_matrix = get_osrm_distance_matrix(locations, transport_mode)
    time_matrix = get_time_matrix(distance_matrix, 333)

    problem_instance = vroom.Input()
    problem_instance.set_durations_matrix(profile="car", matrix_input=time_matrix)
    problem_instance.add_job(jobs)
    problem_instance.add_vehicle(pyvroom_vehicles)

I found out that it always use the vehicle that have higher capacity

Here is my input: input.json

If I change the capacity of first vehicle to 50, it will use the second one whose capacity is 120. But if I change the first one's capacity to 150, then tool will use the first one.

I find out that this case happen a lot if the time_window is short.

[SkyTik]

input.json If I use this input which have a lot of vehicles, if the depot's time_window start at 07:45, the result looks good:

Weights: 109.49000000000001 Vehicle's capacity: [120] Weights: 629.17 Vehicle's capacity: [1000] Weights: 3092.14 Vehicle's capacity: [5000]

But if I move the the start to, let say 14:47, something will be wrong

Weights: 109.49000000000001 Vehicle's capacity: [1000] Weights: 2426.88 Vehicle's capacity: [5000] Weights: 622.0999999999999 Vehicle's capacity: [5000] Weights: 224.64000000000004 Vehicle's capacity: [5000] Weights: 396.71000000000004 Vehicle's capacity: [5000]

Why use a vehicle with 1000 capacity for only 109.5 weight ?

[SkyTik]

I've tested many cases and it seems that the delivery of jobs/capacity of vehicles is not considered when combined with time windows

[jonathf]

This is outside the scope of my experties. @jcoupey is this expected behavior?

[SkyTik]

I tried to add cost for vehicles, and things work as expected. The more capacity of a vehicle, the more it will cost. So VROOM will try to use the most "low-cost" vehicles.

def create_vehicles(vehicles, max_travel_time, max_stop_point, time_window):
    print(max_travel_time)
    return [
        vroom.Vehicle(
            id=vehicle["id"],
            start=0,
            end=0,
            max_travel_time=max_travel_time,
            time_window=time_window,
            max_tasks=max_stop_point,
            capacity=[vehicle["capacity"]],
            costs=vroom.VehicleCosts(vehicle["capacity"]),
        )
        for vehicle in vehicles
    ]

Consider my example in the previous comment, here is the result:

Weights: 82.44999999999999 Vehicle's capacity: [120] Weights: 622.0999999999999 Vehicle's capacity: [1000] Weights: 447.32 Vehicle's capacity: [1000] Weights: 2627.95 Vehicle's capacity: [5000]

So I guess that if I do not set cost for vehicle, VROOM will use any vehicle and only ensure that sum weight is not over the capacity of a vehicle, and the vehicle will arrive at the location on time, it does not care about vehicle with the most suitable capacity.

[jcoupey]

VROOM will use any vehicle and only ensure that sum weight is not over the capacity of a vehicle, and the vehicle will arrive at the location on time, it does not care about vehicle with the most suitable capacity.

That's a good summary indeed. If there are "ties" in term of cost for vehicles (same routing profile, same travel time/distance costs), we don't really care about which vehicles are used or not since the solution evaluation is the same. As you found out, setting a fixed cost can be a way to hint toward using some vehicles over others if possible.

Now for a quick background: this happens because the heuristics we have in place usually start building routes for vehicles with higher capacity first. The rationale is that in situations where resources are scarce and not all tasks can be included in the solution based on capacity constraints, this usually tends to provide better solutions in term of total number of assigned tasks.

[SkyTik]

Thank you so much for your explanation, I will close this question.

[ptpmashish]

@jcoupey thank you! in our case, we wanted to use the smaller vehicle when the parcel is small and cost is not given. anyway we have figured out a way to hack it with cost. thank you! I understood the background with the heuristics you explained.