Relations parameter (type "any") works with one vehicle but has problems when there are more vehicles in the request

[tobra23]

Hi, first of all: amazing project! Keep up the great work!

I currently have a problem regarding the relations parameter within multi vehicle routing. I have several vehicles and want to use the relations parameter in order to make sure that shipments are bound to a specific vehicle. In addition I use the type "any" because I want the shipments to be optimized on this vehicle. This works perfectly, most of the time. In the example below, we need to have a look at the vehicle with ID "66_1". Several shipments are bound to the car via relations with type "any". Now, if you take a look at the response of the algorithm, you will see that the shipments for the vehicle "66_1" came back not optimized and in the same order as they were in the request. I have no clue why it works with the other 3 vehicles but not for this specific one. Do you have an idea? Thanks a lot in advance!

[Removed data to keep thread readable, please attach files instead ]

[reinterpretcat]

Hi,

thanks for feedback!

Few notes:

• the request had a wrong format, but I was able to convert it to pragmatic format used by the project
• there was no response example: it was just the same content as in request
• it is hard to analyze problem files when it is more than few jobs, so my thoughts are based on your problem description

At the beginning of the search, the tour (any) relation preassign all jobs into the tour without any constraint check (adding such check is in my TODO list). So, violation of any constraint can happen. If you don't like such behavior, you can simply use unique skill on the vehicle and jobs which should be assigned only to this vehicle (this is equal to any relation except constraint check behavior). Both approaches are not specifying any specific order of the jobs in the tour. There is one corner case which I guess you faced:

• you have a typical objective which wants to maximize assignment of the jobs at first (minimize-unassigned)
• one of the vehicles has more jobs specified in relation than can be assigned to it (e.g. total load exceeds capacity)
• the solver starts its optimization process from the initial solution where jobs are preassigned to the corresponding vehicles according to the relations definition.
• when the solver tries to rearrange jobs for an unreachable tour (e.g. tour with capacity violation), it cannot inserted all jobs back as constraint check logic will disallow that. So it fallbacks to original state.

As I mentioned above, I think you can replace any (tour) relation with unique skills for all vehicles:

• assign to each vehicle unique skill (e.g. 67_1)
• assign such skill to each job which was in the relation
• remove relations completely

I hope this helps

[tobra23]

Hi,

appreciate your quick answer! Sorry for not providing the correct response, first of all. I will attach you both, the original request and the response, to this answer (see attached "All vehicles_Request" and "All vehicles_Response").

Now, regarding your feedback:

1. I had exactly the same idea as you that I assigned the vehicle too many jobs so that the capacity exceeds. In order to be sure about this, I calculated the capacities of all jobs and compared them with the capacities of the corresponding vehicles.

Here is my result:

Actually, the capacity type 1 of the jobs exceeds the capacity type 1 of the vehicles at three of the four vehicles. But for two of them I got an optimized result back.

For another test, I gave the algorithm just the vehicle "66_1" with the exact same jobs and the exact same relations. Surprisingly, I got an optimized tour back with jobs that couldn't be assigned and the corresponding reason "capacity constraint" (see attached "Only vehicle 66_Request" and "Only vehicle 66_Response").

2. Thanks for the advice regarding using the skill-system. Unfortunately, this would not really solve my problem. I'll describe you why with an example:

My goal:
I give the algorithm 10 jobs and 3 vehicles. I want 2 jobs to be done by "vehicle 1", I want another 2 jobs done by another specific "vehicle 2". The 6 remaining jobs should be assigned in the best way possible on all 3 vehicles ("vehicle 1", "vehicle 2", "vehicle 3"). The 2 jobs for "vehicle 1" and the two jobs for "vehicle 2" should be definitely assigned to the two vehicles before the other jobs are assigned. But in case that there are too many "vehicle 1"-related jobs (capacity constraint), they should also be assignable to the 2 other vehicles (vice versa for vehicle2 related jobs).

If I would use skills, then I would give the first 2 jobs the skill "red", the other 2 jobs the skill "green" and the remaining 6 jobs get "yellow". "Vehicle 1" gets skill "red" and "yellow", "Vehicle 2" gets skill "green" and "yellow", "Vehicle 3" gets skill "yellow". In this constellation, I can't make sure that "Vehicle 1" and "Vehicle 2" really get the jobs with skill "red" respectively "green" prioritized and not only jobs with skill "yellow". It's possible that the 6 jobs with skill "yellow" are assigned to "Vehicle 1" and the jobs with skill "red" remain unassigned (e.g. because of "capacity constraints"). I could imagine that the value parameter on the jobs can help me out here. Nevertheless, I still have the problem that a job with skill "red" cannot be assigned to "vehicle 2" if it doesn't fit on "vehicle 1".

I hope I described it in a way that's understandable :-) Appreciate your help a lot!

All vehicles_Request.txt
All vehicles_Response.txt
Only vehicle 66_Request.txt
Only vehicle 66_Response.txt

[reinterpretcat]

For your goal, I think you can additionally try to use order feature:

• 2 jobs for vehicle 1 and 2 jobs for vehicle 2 should be given order: 1 (see documentation) if you want to assign them first in the tours or some non-zero value if you want to prefer them to be assigned over other jobs
• also these jobs and vehicles should have their specific skill specified as you described (e.g. red for vehicle 1 and green for vehicle 2)
• other 6 jobs don't need any skill as they can go to any vehicle. So, you don't need yellow skill at all
• as default behavior of order objective is not constrained (probably, I need to change that), you need to override objective (a bit different for value usage), e.g.

 "objectives": [
    [
      {
        "type": "minimize-unassigned"
      }
    ],
    [
      {
        "type": "tour-order",
        "isConstrained": true
      }
    ],
    [
      {
        "type": "minimize-tours"
      }
    ],
    [
      {
        "type": "minimize-cost"
      }
    ]
  ]