Add constraints on assignment problem_ Vehicle assignment

[vuphamngoctan1612]

I have problem: How to choose best solution about cost for assign vehicles to routes. I want to use assignment problem algorithm in OR tool to resolve it

• List routes

  • Start_time
  • End_time
  • List locations of route

• List internal + external vehicles

  • Cost

I want to add constraints: time management https://colab.research.google.com/drive/1od_0IxyUKM5b4ITVbvsGo0pMmzbrXp90?usp=sharing

But it's not working. Why? and how to resolve it?

[lperron]

as usual, you write imperative code and not declarative code.

• You cannot use a variable as a boolean or integer value. variables are opaque objects.
• You cannot use python operators like or, and, min, max as they will silently create code that makes no sence.

I suggest:

• switch to CP-SAT as (a) it is a better solver, and (b) it will not fail silently
• look at ortools/sat/samples/assignment*.py
• look at https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md to understand how to write declarative code for tests

[vuphamngoctan1612]

When I run normal Assignment Problem, I have this result :

I want to create a constraint: if car 1 is assigned to route A and B, solution is wrong because start - end of A and B are duplicate.
You have solution?

[lperron]

You mean overlap. Just add all incompatibilities. Le mer. 20 mars 2024, 07:11, Vũ Phạm Ngọc Tân ***@***.***> a écrit :

…

image.png (view on web) <https://github.com/google/or-tools/assets/71437616/d115b827-afc7-4c44-a21e-0a668e147eb6> When I run normal Assignment Problem, I have this result : image.png (view on web) <https://github.com/google/or-tools/assets/71437616/d50e1962-e09d-4c27-af2c-37f2c4c42cb6> I want to create a constraint: if car 1 is assigned to route A and B, solution is wrong because start - end of A and B are duplicate. You have solution? — Reply to this email directly, view it on GitHub <#4138 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MHDIJNSSP4M3WFCLLYZER7NAVCNFSM6AAAAABE5AXEVKVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DQNBYHAYTC> . You are receiving this because you commented.Message ID: ***@***.***>

[vuphamngoctan1612]

How to add all incompatibilities? I don't understand u

[lperron]

interval x overlap with interval y for all workers w: assign[w][x] + assign[w][y] <= 1 Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mer. 20 mars 2024 à 10:14, Vũ Phạm Ngọc Tân ***@***.***> a écrit :

…

How to add all incompatibilities? I don't understand u — Reply to this email directly, view it on GitHub <#4138 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MFYD4SWDCLOBKQK4TYZFHO7AVCNFSM6AAAAABE5AXEVKVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DQNJQGMYTA> . You are receiving this because you commented.Message ID: ***@***.***>

[vuphamngoctan1612]

In my result, worker 0 is assigned to 2 tasks: 0 and 1
But task 0 start at 8 and end at 10;
task 1 start at 8.5 and end at 11;
So this solution is wrong, and algorithm have to find other solution

[lperron]

exactly my point Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mer. 20 mars 2024 à 11:32, Vũ Phạm Ngọc Tân ***@***.***> a écrit :

…

In my result, worker 0 is assigned to 2 tasks: 0 and 1 But task 0 start at 8 and end at 10; task 1 start at 8.5 and end at 11; So this solution is wrong, and algorithm have to find other solution — Reply to this email directly, view it on GitHub <#4138 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3NSQQ3K3GKBUT5HIY3YZFQTLAVCNFSM6AAAAABE5AXEVKVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DQNJRGA4DS> . You are receiving this because you commented.Message ID: ***@***.***>