Constraint for putting a set of nodes on the same vehicle (VRP)

[KeremAslan]

What version of OR-tools and what language are you using?
Version: 7.7.7810
Language: Java/Kotlin

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver

What operating system (Linux, Windows, ...) and version?
Mac OS

What did you do?
I want to set a hard constraint that enforces a set of nodes to be visited by the same vehicle. I found various links that describe this problem and the suggested approach, see here, here and 9.5.5.3 for examples.

Given this, I have crafted the following extension function in Kotlin:

fun RoutingModel.addVehicleEqualityConstraint(firstNodeIndex: Long, secondNodeIndex: Long) {
    val solver = this.solver()
    // This forces to solver to build solutions by adding both nodes, simultaneously. Otherwise, the solver
    // will add the nodes one by one, but that will never satisfy the pick-up and delivery constraint
    this.addPickupAndDelivery(firstNodeIndex, secondNodeIndex)
    // sets the constraint that each index should be handled by the same vehicle
    solver.addConstraint(
            solver.makeEquality(this.vehicleVar(firstNodeIndex), this.vehicleVar(secondNodeIndex))
    )
}

If you are unfamiliar with Kotlin, here is a short description of an extension function.

Anyway, my problem is that this suggested approach seems to work for a problem set with 2 nodes that have to be on the same vehicle, but not three.

Setting the constraint for two nodes is straightforward:

val firstIndex = routingIndexManager.nodeToIndex(firstNode)
val secondIndex = routingIndexManager.nodeToIndex(secondNode)
routingModel.addVehicleEqualityConstraint(firstIndex, secondIndex)

Setting the constraint on three nodes I would expect to do this:

val firstIndex = routingIndexManager.nodeToIndex(firstNode)
val secondIndex = routingIndexManager.nodeToIndex(secondNode)
val thirdIndex = routingIndexManager.nodeToIndex(thirdNode)
routingModel.addVehicleEqualityConstraint(firstIndex, secondIndex)
routingModel.addVehicleEqualityConstraint(secondIndex, thirdIndex)

However, OR-Tools seems to hang when I do this. This is the output in the search log:

I0916 13:03:19.088389 129110016 search.cc:254] Start search (memory used = 351.98 MB)
I0916 13:03:19.088438 129110016 search.cc:254] Root node processed (time = 0 ms, constraints = 35, memory used = 351.98 MB)
I0916 13:03:19.088558 129110016 search.cc:254] Solution #0 (2, time = 0 ms, branches = 34, failures = 1, depth = 33, memory used = 351.99 MB, limit = 0%)

Removing the addPickupAndDelivery() from addVehicleEqualityConstraint() seems to work, but I am suspecting that is something that works by chance rather than that is how it should work (as it contradicts all the comments and documentation).

I believe this is a bug?

Also, it'd be good to refactor the function name addPickupAndDelivery to something like addNodeAssociation as it is more generic than the pick up and delivery constraint.

[lperron]

Please use the mailing list. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mer. 16 sept. 2020 à 07:58, KeremAslan <notifications@github.com> a écrit :

…

*What version of OR-tools and what language are you using?* Version: 7.7.7810 Language: Java/Kotlin *Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)* Routing Solver *What operating system (Linux, Windows, ...) and version?* Mac OS *What did you do?* I want to set a hard constraint that enforces a set of nodes to be visited by the same vehicle. I found various links that describe this problem and the suggested approach, see here <#847 (comment)>, here <#1064 (comment)> and 9.5.5.3 <https://acrogenesis.com/or-tools/documentation/user_manual/manual/tsp/model_behind_scenes_overview.html> for examples. Given this, I have crafted the following extension function in Kotlin: fun RoutingModel.addVehicleEqualityConstraint(firstNodeIndex: Long, secondNodeIndex: Long) { val solver = this.solver() // This forces to solver to build solutions by adding both nodes, simultaneously. Otherwise, the solver // will add the nodes one by one, but that will never satisfy the pick-up and delivery constraint this.addPickupAndDelivery(firstNodeIndex, secondNodeIndex) // sets the constraint that each index should be handled by the same vehicle solver.addConstraint( solver.makeEquality(this.vehicleVar(firstNodeIndex), this.vehicleVar(secondNodeIndex)) ) } If you are unfamiliar with Kotlin, here is a short description of an extension function <https://kotlinlang.org/docs/reference/extensions.html>. Anyway, my problem is that this suggested approach seems to work for a problem set with 2 nodes that have to be on the same vehicle, but not three. Setting the constraint for two nodes is straightforward: val firstIndex = routingIndexManager.nodeToIndex(firstNode)val secondIndex = routingIndexManager.nodeToIndex(secondNode) routingModel.addVehicleEqualityConstraint(firstIndex, secondIndex) Setting the constraint on three nodes I would expect to do this: val firstIndex = routingIndexManager.nodeToIndex(firstNode)val secondIndex = routingIndexManager.nodeToIndex(secondNode)val thirdIndex = routingIndexManager.nodeToIndex(thirdNode) routingModel.addVehicleEqualityConstraint(firstIndex, secondIndex) routingModel.addVehicleEqualityConstraint(secondIndex, thirdIndex) However, OR-Tools seems to hang when I do this. This is the output in the search log: I0916 13:03:19.088389 129110016 search.cc:254] Start search (memory used = 351.98 MB) I0916 13:03:19.088438 129110016 search.cc:254] Root node processed (time = 0 ms, constraints = 35, memory used = 351.98 MB) I0916 13:03:19.088558 129110016 search.cc:254] Solution #0 (2, time = 0 ms, branches = 34, failures = 1, depth = 33, memory used = 351.99 MB, limit = 0%) Removing the addPickupAndDelivery() from addVehicleEqualityConstraint() seems to work, but I am suspecting that is something that works by chance rather than that is how it should work (as it contradicts all the comments and documentation). I believe this is a bug? Also, it'd be good to refactor the function name addPickupAndDelivery to something like addNodeAssociation as it is more generic than the pick up and delivery constraint. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2155>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3K35QQJLJNPLM3O6N3SGBHZBANCNFSM4ROI5HNA> .

[KeremAslan]

Posted on Google Groups https://groups.google.com/g/or-tools-discuss/c/ewH4VjfkvMg