New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

FIFO / LIFO in Pick and Drop #922

Open
GuyBenhaim opened this Issue Nov 6, 2018 · 16 comments

Comments

Projects
3 participants
@GuyBenhaim

GuyBenhaim commented Nov 6, 2018

Can you suggest a scheme to apply LIFO or FIFO constraint across the entire fleet?

  • For A and B, LIFO means that if A was picked (and not yet dropped), then B was picked, B must be dropped * before A is dropped.
  • For A and B, FIFO means that if A was picked, then B was picked, A must be dropped before B is dropped.

Seems complex, since we do not know in advance which Pick & Drop Nodes are served by each vehicle, and at what times ....

@Mizux Mizux added this to To do in Kanban 7.0 via automation Nov 6, 2018

@Mizux Mizux added this to the v7.0 milestone Nov 6, 2018

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Nov 13, 2018

Any response, good or bad ...

@Mizux

This comment has been minimized.

Collaborator

Mizux commented Nov 13, 2018

  • Bad news, not possible on master (i.e. any v6.x)

  • Good news will be available in v7.0 cf abseil branch

    #ifndef SWIG
    // Types of precedence policy applied to pickup and delivery pairs.
    enum class PickupAndDeliveryPolicy {
    // Any precedence is accepted.
    ANY,
    // Deliveries must be performed in reverse order of pickups.
    LIFO,
    // Deliveries must be performed in the same order as pickups.
    FIFO
    };
    #endif // SWIG

  • Bad news, it seems to not be wrapped (i.e. not available in Python, Java, .Net)

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Nov 14, 2018

And v7.0 is expected by end December?
Will all currently 'wrapped' functions be supported?

Could you direct to any document or correspondence on how to add wrappers to Routing.h using SWIG?
Or, at least, to the part that shows the SWIG part/code of the current software?

@jmarca

This comment has been minimized.

Contributor

jmarca commented Dec 4, 2018

something like this works for me:

    # Add a dimension for setting FIFO constraints
    def fifo_fn(a, b):
        """
        Just increment by one
        """
        return 1

    routing.AddDimension(
        fifo_fn,  # total time function callback
        0, # allowed time slack
        int(total_nodes),
        True,
        'FIFO')
    fifo_dimension = routing.GetDimensionOrDie('FIFO')

then later

early_condition = fifo_dimension.CumulVar(picku_a_index) <= fifo_dimension.CumulVar(picku_b_index)
fifo_constraint = fifo_dimension.CumulVar(deliv_a_index) <= fifo_dimension.CumulVar(deliv_b_index)
expression = solver.ConditionalExpression(
                early_condition,
                fifo_constraint,
                1)

solver.AddConstraint(
                expression >= 1
            )

If you just use time_dimension, you get issues because it has slack...the "FIFO" dimension above has zero slack and so can guarantee ever increasing values for each route.

If you have multiple vehicles, you have to add a "same vehicle" constraint as well to the conditional constraint.

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 5, 2018

Thx.
How do we get picku/deliv_a/b_index ? these are not known in advance.

@jmarca

This comment has been minimized.

Contributor

jmarca commented Dec 5, 2018

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 5, 2018

Node indices are known however, the visit order is not known in advance.
Seems that "early_condition" and "fifo_constraint" force Solver() always to pick a before b, and to drop a before it drops b.
This prevents Solver() to consider starting with b which might be cheaper. Correct?

@Mizux

This comment has been minimized.

Collaborator

Mizux commented Dec 5, 2018

No, it's means if the condition is verified i.e. "pickup a before pickup b" THEN "deliver a must be before deliver b".

Using a conditional expression mean the constraint will only be active only if the condition is respected.

It also means you have to write it in both direction hence the "two nested for loops" comment from @jmarca

note: Open question, I don't know if the condition should also check that node are active see #847 (comment)

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 5, 2018

Cool
Will check this.
Thanks, James.

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 5, 2018

If we are using explicit Node indexes, is it I correct that we would need such a conditions-set per each possible combination of tasks (task = pick+drop)?
So, for 10 tasks > 100 conditions?
Of could we make the condition generic?

@Mizux

This comment has been minimized.

Collaborator

Mizux commented Dec 5, 2018

Not sure we can make it generic AFAIK.

note: That's why I would push forward to have support of FIFO etc in v7.0 for any language IMHO.
note: now master HEAD is the v7.0 alpha, biggest changes are:

  • Now you have to register callback, then pass register index to AddDimension.
    # Define weight of each edge
    distance_evaluator = routing.RegisterTransitCallback(
    partial(create_distance_evaluator(data), manager))
    routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
    # Add Capacity constraint
    demand_evaluator_index = routing.RegisterUnaryTransitCallback(
    partial(create_demand_evaluator(data), manager))
    add_capacity_constraints(routing, data, demand_evaluator_index)

    pro: you can reuse several time the same callback ;)
  • index management in routing now use a RoutingIndexManager.
    # Create the routing index manager
    manager = pywrapcp.RoutingIndexManager(data['num_locations'],
    data['num_vehicles'], data['depot'])

    plan_output += ' {} Load({}) -> '.format(
    manager.IndexToNode(index), assignment.Value(load_var))
@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 5, 2018

FIFO and LIFO?

Would the above changes will accessible in all languages?

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 5, 2018

Does 7.0 actually auto-implement these NxN constraints, or uses a better way to manage State?

@jmarca

This comment has been minimized.

Contributor

jmarca commented Dec 5, 2018

Two points. First, to @Mizux point about considering active nodes, I've run this in lots of tests and have never had an issue, and nodes are dropped all the time in my tests.

Second it's not necessarily NxN constraints (where N is the number of pickups). You only have to set the conditional constraints on those pairs for which the B node falls inside of the A node service time. That is, if it is impossible to have A in the truck when picking up B, then there is no need to impose the conditional constraint at all. The only case in which there are NxN constraints is if the time windows for all pickups extend for the entire simulation. Note that I skipped those sorts of details in my original post because they seemed like an implementation detail. Yes it is O(N^2) constraints in the limit, but it depends on what you are solving.

And hopefully the underlying constraint solver can handle lots of constraints!

@GuyBenhaim

This comment has been minimized.

GuyBenhaim commented Dec 6, 2018

Thx,
Is: "nodes are dropped all the time in my tests." good or bad in this context?

I expressed a complex case where the only constraint on visit order is FIFO/LIFO.
Indeed, other constraints may allow to duilute the NxN conditions.
(Actually, N/2 x N/2 as each task involves two Nodes).

@jmarca

This comment has been minimized.

Contributor

jmarca commented Dec 6, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment