Same Location Orders not picked up together in VRP

[Nepsi Bansal]

Hi,

I am facing a issue while using vehicle routing library.

I have 10 orders-C1,C2....C10. Order C1,C2,C3 have same location and another orders have different locations.

Sequence in which vehicle is picking orders -C1,C2,C4 and then C3. Why it is not picking C1,C2 ,C3 (as three orders have same location) together and then go to C4. Time window is large for all orders so there should be any problem related to time window constraint.

What constraint should I add so that a vehicle picks same location orders together.
Thanks.

[Ken Alton]

Hi,

Is there an incentive for the solver to find the minimal time or distance solution? Is there a span cost on the time dimension, or a transition cost between nodes that is zero between C1, C2, C3 and positive between C4 and {C1, C2, C3} so that a solution that visits C1, C2, C3 together is a lower cost solution? If so, have you tried using a metaheuristic to give the solver a chance to escape local minima?

Thank you,

Ken

--
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-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Nepsi Bansal]

Hi,

I am using Parallel cheapest insertion strategy. Related to cost -,For travel cost I am using distance between them and dividing it by speed.Yes,I have taken span cost approx to 30 .I have set the span cost using method- timedimension.SetSpanCostCoefficientForVehicle(30, vehicle);

As C1,C2,C3 orders have same location and also time window is same for these orders,So,it should get minimum cost if it picks C1,C2,C3 together and then move to C4 .

As you have written- use a metaheuristic to give the solver a chance to escape local minima -How I can do the same?

Thanks,

Nepsi

[Ken Alton]

Hi Nepsi,

To use a metaheuristic you will need to set the local_search_metaheuristic field on the RoutingSearchParameters, similar to how you set the first_solution_strategy to PARALLEL_CHEAPEST_INSERTION. We recommend you try GUIDED_LOCAL_SEARCH for the metaheuristic. See discussion at https://github.com/google/or-tools/issues/455.

If the solver is still not finding what seems like the optimal solution (with C1, C2, and C3 together), you might want to post the code creating the routing model so we can try reproduce the issue. In fact, it is somewhat surprising to me it is not finding the solution combining C1, C2, and C3 even without metaheuristics. So if you don't mind, you could post the modelling code anyway, so we can try to understand why that is happening.

Thanks,

Ken

--

[aca...@streamba.net]

Hey! Connecting to this idea of showing location with multiple pickups as different nodes - is there a way to ensure that if two vehicles decide to visit the same location at the same time; one would have to wait for the other to end?

[Vincent Furnon]

You could use IntervalVars for that, see this example https://github.com/google/or-tools/blob/master/examples/cpp/cvrptw_with_resources.cc to see how it's done.

The idea is that for each location you have a cumulative constraint linking all the IntervalVars corresponding to routing nodes at this location; you can then force at most one of these intervals to happen at the same time.

--

[aca...@streamba.net]

But since these are separate nodes, I can not set an interval var at each node right?

The example you mentioned is looking at depot locations, but I would be looking at arbitrary nodes within the route - some nodes would essentially be the same location but with transition 0 between them because they symbolise different bulks of pickup etc 

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Vincent Furnon]

You would need 1 interval var for each "routing" node (potentially several per location). They would just be there to make sure that if 2 nodes at the same location are visited by 2 vehicles, they cannot overlap. It's the same idea as for depot nodes.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

[Behnam Arjomandi]

Hi Ken,

Is there a similar option for a Scheduling problem? I am facing an issue where the solver does not find a solution even though one exists and it appears to be because some of the "shifts" that need to be scheduled to meet the constraints actually decrease the value of the objective function (which I am trying to Maximize). This seems to me to be the solver not being able to increase the value of the Objective Function when trying to add those shifts to meet the constraints, and giving up.

Thanks,

Ben

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Krishnakumar M]

@Nepsi, 

 Has the solution provided by Vincent Furnon work for you?

 Could you update?

On Wednesday, August 1, 2018 at 12:02:16 PM UTC+5:30, Nepsi Bansal wrote: