Prioritize Locations List on VRP

[Yukihiro Katagiri]

Hi all,

I have a prioritized locations: L1, L2, L3, ... , Ln

L1 has the highest priority and the Ln has the lowest one.

i.e. "priority of Lx" is grater than "priority of Ly" where x < y.

I'd like to create a route with the following rule.

1. L1 is the start and the end node.

2. The route can be a set of L1, L2, ... , Lk. (k <= n).

3. All locations from L1 to Lk must be in the route, but any of the other locations (Lk+1 to Ln) must not in the route.

So a location set of routes will be like [L1] , [L1, L2] , [L1, L2, L3, L4], but not like [L1, L3], [L1, L2, L5, L6, ..., Ln].

How to represent VRP constraints for locations? Can I do this by specifying location dropping penalties with AddDisjunction function?

Actually, I already tried several times with the AddDisjunction function, but the results will be varied by the first solution strategy (see attached .py file and the result.txt file).

I'm wondering if my code attached has wrong constraints, or all I need to care about is to set dropping penalties and the first solution strategy?

Best Regards,

Yukihiro Katagiri

[Gilberto Kaihami]

A possible solution would be create a transit matrix like the following

      L1       L2.     L3       L4

L1  0         1        1        1 

L2  0         0        1         9999

L3  0         9999  0        1

L4  0         9999 9999  0

Therefore you are applying  this matrix (adding to the ArcCost), you are forcing a route following L1 -> L2 -> ... -> Ln.

To split the routes you can set a Distance constraint, for example.

Note that, if the solution is unfeasible you must add a drop penalty, and/or increase the total number of vehicles (e.g: more than 1).

Cheers

[Mizux Seiha]

Something like that:
```py

# build list of all vehicle's end indices

ends = [routing.End(i) for i in range(manager.GetNumberOfVehicles())]

for node in all_node_except_l1[:-1]: # loop from l2 to ln-1
  index = manager.NodeToIndex(node)

  next = manager.NodeToIndex(node+1)

  routing.NextVar(index).SetValues([next] + ends) # Lk -> Lk+1 or any ends nodes

# special case for vehicle's start nodes

for vehicle in range(manager.GetNumberOfVehicles()):
  index = routing.Start(vehicle) # aka L1

  next = manager.NodeToIndex(L2)

  routing.NextVar(index).SetValues([next] + ends) # L1 -> L2 or any ends nodes

```

[Yukihiro Katagiri]

Gilberto, Mizux

Thanks for your comment.

but I’d like to take one step further.

A location set of the route, like I give you as examples, does not describe visiting order.

If the location set of a route is [L1, L2, L3], the possible routes are:

   L1 -> L2 -> L3 -> L1

   L1 -> L3 -> L2 -> L1

If the location set is [L1, L2, L3, … , Lk], the number of possible routes is (k-1)! patterns,

because only L1 is the fixed-ordered location, and the others aren’t. 

Does your suggestions still work for the case above? 

Best Regards,

Yukihiro Katagiri

2021/08/11 16:11、Mizux Seiha <mizu...@gmail.com>のメール:

-- 
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/Ptm9hRN1yh0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c4c3e67a-32f5-43ea-a0f0-8774adb348a3n%40googlegroups.com.

[Mizux Seiha]

If you don't have priority in the visit order then I would use this constraint instead:

```python

    # Constraint: allow to visit Lk if visit Lk-1 is performed

    for node in range(2, len(data["distance_matrix"])):

        index = manager.NodeToIndex(node)

        prev = manager.NodeToIndex(node-1)

        routing.solver().Add(routing.ActiveVar(prev) >= routing.ActiveVar(index))

    ##############

    # Allow drop #

    ##############

    visit_penalty = 1_000_000

    for node in range(len(data["distance_matrix"])):

        if routing.IsStart(node) or routing.IsEnd(node):

            continue

        index = manager.NodeToIndex(node)

        routing.AddDisjunction([index], visit_penalty)

    # Setting first solution heuristic.

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.first_solution_strategy = (

        #routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

        routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED)

```

 

Possible output on an example:

- I limit vehicle to 1500 max dist so vehicle can't visit all node
- distance metric is:

  if from_node != to_node:

            value = max(0, 200 - 20*max(0, to_node - from_node))

i.e. solver has incentive to visit "Ln-i -> Li" to minimize travel distance and thus we can verify constraint is still working

Objective: 5001500

Dropped nodes: 10 11 12 13 14 (5)

Route for vehicle 0:

0 Distance(0) -> 8 Distance(40) -> 1 Distance(240) -> 7 Distance(320) -> 2 Distance(520) -> 5 Distance(660) -> 4 Distance(860) -> 9 Distance(960) -> 3 Distance(1160) -> 6 Distance(1300) -> 0 Distance(1500)

Total Distance of all routes: 1500

[Yukihiro Katagiri]

Thanks a lot!

Your code is so helpful.

Best Regards,

Yukihiro Katagiri

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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/969739f6-9cef-459a-aa7b-6419a63469e6n%40googlegroups.com.