Skip to content

Too script compatibility check with setup time #1329

@jcoupey

Description

@jcoupey

In Input::set_extra_compatibility we add additional filtering for vehicle to job compatibility, basically by building an empty route for a vehicle then testing validity for adding a single job/shipment. The underlying assumption is that if a job/shipment can't be handled on its own in a dedicated route, then it's never doable anyway since adding other tasks around can only result in more constraints, especially time-wise.

Turns out this assumption is wrong in some edge cases involving same-location jobs, tight TW and setup time. Let's take jobs $j_1$ and $j_2$ with TW $[a_i, b_i]$, same location and setup times $s_i$. If $a_2 + s_2$ is greater than the vehicle TW deadline, then route $[j_2]$ is not doable, while $[j_1, j_2]$ may be totally valid, because then setup is not applied at $j_2$ so this job could start and end at $a_2$.

The implications are: such jobs/shipments would never end up assigned to the matching vehicles even if it may be possible in a "more complex" route. Also vehicle steps providing such a route would trigger an error based on assumed incompatibility while the route may be actually feasible.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions