What's the best strategy to improve the configuration?

[williamrijksen]

First of all, a big applause for this library. It provides a lot of functionality out of the box and is really good documented.

My question is about tweaking my problem.json and configuration. I experience most of the times an inconsistent result, mostly resulting in UNASSIGNED jobs. Mostly I could see theres enough space in the time window to fit more jobs in the tour.

How could I tweak this problem the best? @reinterpretcat Is it an option to send my problem.json in a DM to find out what is my mistake?

Thanks in advance! 🙏🏼

[reinterpretcat]

Thanks for feedback!

Yes, convergence to the similar (and good!) results over multiple runs is one of the challenging problems. Due to non-determenistic nature of internal algorithm, stability of the results depends on different characterestics of the configuration and problem itself, e.g.:

• problem complexity in terms of:

  • size (e.g. amount of jobs and different vehicle types),
  • type of constraints, their combination, values distribution, etc.

• configuration of the algorithm:

  • exploration vs exploitation dilemma
  • running time

So, my general recommendation would be to play with:
* running time, e.g. increase time quota to help algorithm to converge to the same local optimum
* switch hyper-heuristic. There are two: dynamic and static, controlled by heuristic argument in cli
* switch search mode: broad vs deep. Generally speaking, deep has more greedy behavior. Internally, it switches to use naive elitism mechanism to maintain a pool of discovered solutions. broad mode uses my custom algorithm called rosomaxa which tries to maintain diverse set of solutions.

There are more parameters to tweak using configuration file. Unfortunately, I don't have a clear documentation for them. An example of such config is there: https://github.com/reinterpretcat/vrp/blob/master/examples/data/config/config.full.json

Regarding analysis of your problem.json, I can take a look: maybe I can find some trivial fixes, but without any warranty. Description of your use case also would be nice - maybe problem can be reformulated in more effective way.

[williamrijksen]

@reinterpretcat Thanks for the reply. Indeed I checked already what I could do with the configuration, but so far no success. How could I reach you out to send you the problem.json?

[williamrijksen]

The json files can be found here:

• https://gist.github.com/williamrijksen/2d157b6b2130529f7f7e1b77068b0efe (matrices.json)
• https://gist.github.com/williamrijksen/475da43fae75c0eb3627fc165f17f07c (problem.json)

[reinterpretcat]

Thanks, I'll check them once have time. From the first glance, I have some doubts about objective:

"objectives": [
        [
            {
                "type": "minimize-unassigned",
                "breaks": 0
            }
        ],
        [
            {
                "type": "minimize-tours"
            },
            {
                "type": "minimize-cost"
            }
        ]
    ]

Here, minimizing tours` conflicts with cost minimization. It would be better to redefine objective as:

"objectives": [
        [
            {
                "type": "minimize-unassigned",
                "breaks": 0
            }
        ],
        [
            {
                "type": "minimize-tours"
            }
       ],
       [
            {
                "type": "minimize-cost"
            }
        ]
    ]

[williamrijksen]

Okay really nice you'll help me on this. Do you have an ETA for the solution?

[reinterpretcat]

As it is about algorithm logic, it is hard to say. I would say it will be hard to improve with reloads, but maybe pickup&delivery approach will bring better results already?

[williamrijksen]

Is it possible to use the pickup&delivery approach with the same features as reloading? What is the preferred way to define the pickup list using the duplicated geo-locations? Should I define for each delivery one pickup? It might be good for me to have an example for these cases.

[reinterpretcat]

Yes, it is possible to use, but reload is not for p&d jobs, but only for single pickup or single delivery. You can mix all jobs types and all features in the same problem definition as I'm trying to avoid incompatible features by making underlying algorithms generic.

For your particular json file, you would need to turn every delivery job to p&d jobs, e.g.:

{
                "id": "2680",
                "deliveries": [
                    {
                        "demand": [
                            1,
                            430
                        ],
                        "places": [
                            {
                                "duration": 300,
                                "location": {
                                    "lng": 52.052774,
                                    "lat": 5.23609
                                },
                                "times": [
                                    [
                                        "2021-02-27T07:00:00.000Z",
                                        "2021-02-27T11:00:00.000Z"
                                    ]
                                ]
                            }
                        ]
                    }
                ]
            }

to:

            {
                "id": "2680",
                "pickups": [
                    {
                        "demand": [
                            1,
                            430
                        ],
                        "places": [
                            {
                                "duration": 600,
                                "location": {
                                    "lat": 5.208162,
                                    "lng": 52.058838
                                }
                            }
                        ]
                    }
                ],
                "deliveries": [
                    {
                        "demand": [
                            1,
                            430
                        ],
                        "places": [
                            {
                                "duration": 300,
                                "location": {
                                    "lng": 52.052774,
                                    "lat": 5.23609
                                },
                                "times": [
                                    [
                                        "2021-02-27T07:00:00.000Z",
                                        "2021-02-27T11:00:00.000Z"
                                    ]
                                ]
                            }
                        ]
                    }
                ]
            }

Here, the new definition has pickup task with location of depot (reload place) and the corresponding duration. reloads in this case should be removed completely from vehicle's shift definition.

Expectation that you will get multiple stops in the tour in the depot place with grouped pickup activities mixed with delivery stops to job's locations.

[williamrijksen]

Nice! It seems that moving from reloads towards p&d jobs solves indeed the problem and makes the calculations more stable. Thank you very much for helping me out!