Basic optimization leaves stops unassigned unnecessarily

[aardvarkk]

I think I may be encountering an interesting failure case of the optimizer, but perhaps I'm missing something. I am trying to optimize a route for a single vehicle with 3 stops and getting back a route with 1 unassigned stop when all 3 stops should be able to be performed in a straightforward manner.

The vehicle time window is 8 hours long. The 3 stops are very close to each other geographically, but each has a 2 hour service time.

This route should be fairly straightforward to optimize -- in fact, the order I expect it to return to me is exactly the order of the jobs as presented: 0, 1, 2. Job 0 is a delivery that can be started immediately (same time window as the vehicle). Jobs 1 and 2 are pickups that have been requested to start later in the day. The optimizer chooses to wait until just before the opening time for Job 1 before sending the vehicle out for a pickup, then perform the delivery for Job 0, and leaves the Job 2 pickup unassigned.

If I pass along steps to the vehicle with the order 0 (delivery), 1 (pickup), 2 (pickup) the optimization succeeds with no violations.

I've tried exploration factors 1-5 and none seem to provide the expected response.

Here's the smallest problem I could make that demonstrates the issue:

{
  "jobs": [
    {
      "id": 0,
      "location": [
        -123.382,
        48.455
      ],
      "service": 7200,
      "time_windows": [
        [
          1668531600,
          1668560400
        ]
      ],
      "delivery": [
        64
      ],
      "location_index": 1
    },
    {
      "id": 1,
      "location": [
        -123.381,
        48.455
      ],
      "service": 7200,
      "time_windows": [
        [
          1668539506,
          1668560400
        ]
      ],
      "pickup": [
        64
      ],
      "location_index": 2
    },
    {
      "id": 2,
      "location": [
        -123.383,
        48.455
      ],
      "service": 7200,
      "time_windows": [
        [
          1668539506,
          1668560400
        ]
      ],
      "pickup": [
        64
      ],
      "location_index": 3
    }
  ],
  "vehicles": [
    {
      "id": 0,
      "start": [
        -123.357,
        48.449
      ],
      "end": [
        -123.357,
        48.449
      ],
      "profile": "car",
      "time_window": [
        1668531600,
        1668560400
      ],
      "capacity": [
        768
      ],
      "start_index": 0,
      "end_index": 0
    }
  ],
  "options": {
    "g": true,
    "x": 1
  },
  "matrices": {
    "car": {
      "durations": [
        [
          0,
          310,
          303,
          306
        ],
        [
          307,
          0,
          10,
          41
        ],
        [
          306,
          10,
          0,
          40
        ],
        [
          303,
          47,
          40,
          0
        ]
      ]
    }
  }
}

[jcoupey]

Since I don't have access to your routing stack to reproduce, could you share a standalone version of the problem?

[aardvarkk]

@jcoupey Sorry about that -- I have updated the original question with the matrices.

[jcoupey]

Thanks for sharing the instance, I can confirm the 0 -> 1 -> 2 route is indeed valid, and with all jobs assigned.

What happens here is that all heuristic searches fail to include job 2, ending with a 1 -> 0 route which is untouched by local search.

None of the heuristic route seeding strategy pick job 2 as it is neither the nearest, the furthest, the one with higher amount, or the one with earliest deadline. So either job 0 or job 1 is included first (based on seeding strategy or cheapest cost), always resulting in 1 -> 0 as a next step for cost reasons.

On the other hand due to TW and service times, the only way to achieve a 3-job route is to start with job 0, which never happens here.

Any of the following tiny changes will "cheat" on the seeding strategy, including job 2 and resulting in the right solution: raising pickup by 1 for job 2; reducing deadline by 1 second for job 2; putting job 2 as first job in input.

It's no surprise that our heuristics have biases, the most embarrassing part here is that it shows up on a trivial instance. But based on the above explanation and the fact that tiny changes in input can untie the problem, I'd say this is a rather specific conjunction of facts.