reinterpretcat / vrp

A Vehicle Routing Problem solver
https://reinterpretcat.github.io/vrp/
Apache License 2.0
348 stars 69 forks source link

A simple problem breaks when adding objectives #91

Closed Esya closed 1 year ago

Esya commented 1 year ago

Hello, using a build from master, all jobs fail with NO_REASON_FOUND when adding any objective - Here it is with minimize-cost then minimize-arrival-time, but I've also tried no objective at all. When I remove the objectives section entirely, I do get a solution. I'm not sure what the reason is here. Any idea ?

Problem

{
  "fleet": {
    "profiles": [{ "name": "car" }],
    "vehicles": [
      {
        "capacity": [100000],
        "costs": { "distance": 1, "fixed": 1, "time": 1 },
        "profile": { "matrix": "car", "scale": 1 },
        "shifts": [
          {
            "start": {
              "earliest": "2022-12-06T09:00:00.000+01:00",
              "location": { "lat": 48.59384, "lng": 1.5860837 }
            },
            "end": {
              "latest": "2022-12-06T18:00:00.000+01:00",
              "location": { "lat": 48.59384, "lng": 1.5860837 }
            }
          },
          {
            "start": {
              "earliest": "2022-12-07T09:00:00.000+01:00",
              "location": { "lat": 48.59384, "lng": 1.5860837 }
            },
            "end": {
              "latest": "2022-12-07T18:00:00.000+01:00",
              "location": { "lat": 48.59384, "lng": 1.5860837 }
            }
          }
        ],
        "typeId": "type_3",
        "vehicleIds": ["vehicle_3"]
      }
    ]
  },
  "plan": {
    "jobs": [
      {
        "id": "job_15",
        "services": [
          {
            "places": [
              {
                "duration": 3600,
                "location": { "lat": 48.9147, "lng": 2.29764 }
              }
            ]
          }
        ]
      },
      {
        "id": "job_16",
        "services": [
          {
            "places": [
              {
                "duration": 3600,
                "location": { "lat": 48.93144, "lng": 2.27157 }
              }
            ]
          }
        ]
      }
    ]
  },
  "objectives": [
    [{ "type": "minimize-cost" }],
    [{ "type": "minimize-arrival-time" }]
  ]
}

Cost matrix

{"travelTimes":[0,381,4629,363,0,4638,4597,4643,0],"distances":[0,3464,78071,3376,0,79686,79401,79295,0],"profile":"car"}

Output

{
  "statistic": {
    "cost": 0.0,
    "distance": 0,
    "duration": 0,
    "times": {
      "driving": 0,
      "serving": 0,
      "waiting": 0,
      "break": 0,
      "commuting": 0,
      "parking": 0
    }
  },
  "tours": [],
  "unassigned": [
    {
      "jobId": "job_16",
      "reasons": [
        {
          "code": "NO_REASON_FOUND",
          "description": "unknown"
        }
      ]
    },
    {
      "jobId": "job_15",
      "reasons": [
        {
          "code": "NO_REASON_FOUND",
          "description": "unknown"
        }
      ]
    }
  ]
}
Esya commented 1 year ago

After digging a bit deeper, it seems that if I add minimize-unassigned as the first objective it does not happen. Is this objective mandatory in my situation ?

reinterpretcat commented 1 year ago

Yes, it needs to be added. Otherwise you're telling the solver that you want to minimize cost at first and don't care about amount of unassigned jobs. Zero assigned and zero cost - it looks like a best solution.

Actually, it would be nice to add validation rule to prevent this, but it is not yet there

Esya commented 1 year ago

Ah - that makes sense now that you mention it. I'll close my comment then! Thanks a lot.