Составление маршрутов транспортных средств / Дизайн Алгоритма планирования Ресурса

Здесь мы точно говорим о полном алгоритме NP, кроме некоторого количества автомобилей и прицепов, это не будет задача, в которой вы получите лучшее решение из всех возможных решений, а затем будете возможность отбросить это и пойти снова, чтобы избежать самого длинного пути, как вы предлагаете. Если вы спроектируете свой алгоритм таким образом, очень вероятно, что однажды вы добавите немного больше автомобилей и трейлеров, и он никогда не завершит вычисление решения.

Вы, вероятно, захотите использовать алгоритм, который может достаточно быстро генерировать достаточно хорошее решение проблемы. Убедитесь, что вы создали метрику качества решения, у вас есть хороший способ оценить значение метрики для идеального решения, а затем установить себе некоторый процент, в пределах которого вы Я хочу, чтобы ваше решение основывалось на идеальном решении, и просто возьмите первое решение с метрикой в ​​границах. Это дает дополнительное преимущество: если этот алгоритм занимает слишком много времени для вычисления и вы его прерываете, вы все равно можете использовать решение с наименьшей вычисленной метрикой, даже если она выходит за ваши ожидаемые границы.

Я не уверен какой подход подойти к решению самой проблемы. Я бы посоветовал прочитать несколько статей после поиска на портале acm . Я предполагаю, что UPS и Fedex, вероятно, имеют схожие проблемы, если вы добавите их в качестве ключевых слов в поиск в Google, вы можете получить более полезные результаты.

Я не уверен, какой подход использовать для решения самой проблемы. Я бы посоветовал прочитать несколько статей после поиска на портале acm . Я предполагаю, что UPS и Fedex, вероятно, имеют схожие проблемы, если вы добавите их в качестве ключевых слов в поиск в Google, вы можете получить более полезные результаты.

Я не уверен, какой подход использовать для решения самой проблемы. Я бы посоветовал прочитать несколько статей после поиска на портале acm . Я предполагаю, что UPS и Fedex, вероятно, имеют схожие проблемы, если вы добавите их в качестве ключевых слов в поиск в Google, вы можете получить более полезные результаты.

I tend to agree with Robert. This sounds to me like a really great candidate for an evolutionary optimisation technique like the Genetic Algorithm implementation that he describes.

I have also had very good success on certain problems with the Particle Swarm Optimisation (PSO).Basically, you can think of each genome as a particle in some multi dimensional space. The coordinates of the particle are the paramters to your calculation (fitness function). Each particle is started of randomly with a random velocity. For each iteration of the simulation, you update the position of each particle with its current travel vector, and then you add components of other vectors like: direction to the best particle so far, direction to the best particle ever, direction to a local group best etc...

It may seem rather daunting at first to implement a GA or PSO but I assure you that it is easy to write a small framework that abstracts the algorithm (GA/PSO) from the actual problem domain that you are trying to optimise. You can always fall back to Wikipedia for details of the algorithms.

Once I have a framework, I normally start with a 2 parameter problem (probably a simplification of your problem, or X and Y locations on an image), so that I can easily visualise and tweak the algorithm so that I get good swarming behaviour. Then I scale it up to more dimensions.

I like this approach because it allows me to easily optimise for problems that have rather complex and intricate parts to the actual problem statement (like the cars and trailers).

Also, why the evolutionary techniques are attractive is because you can dedicate a fixed portion of time to the simulation and take the best answer so far when you decide to stop.

In my experience, you tend to take as much time tweaking the parameters to the GA or PSO (once you have an implementation) as you would writing a hard coded heuristic solution, but the benefit is that to change the strategy for finding the solution typically requires parameter changes only or swapping out very well defined algorithms with another implementation, as opposed to coding a completely different strategy to solving the problem heuristically from scratch.

Please give me a shout if you need guidance on designing the generic frameworks for either of the two algorithms. I must point out, that you get several good free 3rd party frameworks out there too. I sometimes like to code my own because I understand every aspect of the algorithm then and I know where I can adjust the strategy.

Общий подход:

Поскольку проблема небольшая, я бы предложил подход, при котором вы добавляете автомобили и прицепы до тех пор, пока не получите осуществимого решения, а не пытаетесь минимизировать автомобили и прицепы.

Решение:

Я добился меньшего успеха на ГА с ограничениями и еще меньшего успеха на ГА с ограничениями на целочисленные переменные (например, количество прицепов в месте расположения). Может быть, программирование ограничений - лучший подход, так как нужно просто сгенерировать выполнимое решение для заданного количества автомобилей и прицепов, а не пытаться минимизировать пройденное расстояние.

Наблюдение:

Вы решаете проблему в сети, где последним ходом может быть перемещение пустого прицепа.

Удачи!