Interest in compact-tour objective

leobudima commented 1 year ago

Hi @reinterpretcat - thanks again for an incredible project and so much amazing progress happening!

A couple of days ago, I was really excited to see the experimental work on "compact-tour" objective as it completely coincided with requirements I received and complaints about current solutions (routes overlapping, multiple vehicles in the same area instead of each having a separate one (even if it would be less efficient)).

Basically, I'd like to prioritize separating routes at expense of route costs - the routes should be separate as possible, so I tried with different combinations of options for the objective - e.g. both small (1) and large (1000) values for all options - but no particular difference or success in separating the routes.

I completely understand it's experimental, not even in the documentation etc - so was just hoping if I'm simply mistaken in how I'm using the objectives :)

let objectives = [
    [
        {
            type: 'minimize-unassigned'
        }
    ],
    [
        {
            type: 'compact-tour',
            options: {
                job_radius: 2,
                threshold: 2,
                distance: 0
            }
        },
        {
            type: 'minimize-cost'
        }
    ]
];

The solution looks like this:

https://imgur.com/a/PB7nOWB

where drivers are completely mixed in this area, despite each job serviceable by any vehicle, and then continue to further jobs, with more separation between them. There are enough drivers (some are left unutilized), so that's not forcing mixing...Capacity is also not an issue (they continue from this area each to its own next)...

Any hints potentially for the parameters, or is this simply not ready at this point - which is completely fine, of course, and I'm very grateful for sharing this project in any case! Thank you.

reinterpretcat commented 1 year ago

Hi @leobudima,

thanks for feedback!

Yes, compact-tour objective is experimental (I haven't tested it on data, just implemented it based on raw idea). However, there are few things you can try to:

you added two objectives on the same level which means they are equally important. This complicates search a bit and very sensitive to extra options which tells solver how to relax one objective a bit (distance and threshold properties are designed for that.

Have you tried to put compact-tour objective on its own level? E.g.:

let objectives = [
    [
        {
            type: 'minimize-unassigned'
        }
    ],
[
 {
            type: 'compact-tour',
            options: {
                job_radius: 2,
                threshold: 2,
                distance: 0
            }
        },
],
    [
        {
            type: 'minimize-cost'
        }
    ]
];

also you can play with options a bit.

leobudima commented 1 year ago

Hi @reinterpretcat - thanks a lot for your response - I've played around some more with the settings, and your suggestion helped achieve some more difference in the results. I haven't managed to achieve more complete separation of routes, though, which the customer is stubborn about, so currently looking into clustering jobs in the preprocessing etc.

In any case, this is a very exciting feature and I look forward to revisiting it at some later stage - warmest thanks again in the meantime for the great work :)

reinterpretcat / vrp

Interest in compact-tour objective #100