Исследование асимптотически оптимального алгоритма для решения задачи доставки грузов транспортом вместимости 2+
Аннотация
В данной работе рассматриваются задачи доставки грузов, частные случаи задачи нахождения гамильтонова цикла. В частности, рассматривается возможность построения асимптотически оптимального алгоритма для задачи доставки грузов транспортом вместимости 2+ и LIFO порядком. Цель работы – исследовать алгоритм, изложенный в статье «Toward Asymptotically Optimal One-to-One PDP Algorithm for Capacity 2+ Vehicles», попытаться довести его до конца или провести эксперименты, которые позволят сделать выводы о потенциальной возможности довести решение до конца.
Для проведения экспериментов производилось сравнение результатов исследуемого алгоритма с точным решением. Для корректировки доказательства алгоритма приведен контрпример и предложен метод избавления от найденного недостатка.
В результате работы получились графики, описывающие эффективность работы алгоритма, а также улучшено доказательство корректности его работы.
Результаты этой работы можно применить для дальнейшего изучения алгоритма, высказывания предположений о возможности довести его до конца или наоборот придумать контрпример.
We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean Space. In particular, an article «Towards Asymptotically Optimal One-to-One PDP Algorithms for Capacity 2+ Vehicles».
In this work presented results of experiments and some theoretical conclusions. Experiments were aimed at testing the hypothesis that the algorithm is correct. Experimental results are graphs of the ratio of the result of an approximate algorithm to the exact solution.
Also in this work are corrections of the proof of the correctness of the algorithm. They do not close all the spaces of the studied algorithm, but bring us to the end.
The results of this work can be used to complete proof of correctness of the algorithm under study.
Для проведения экспериментов производилось сравнение результатов исследуемого алгоритма с точным решением. Для корректировки доказательства алгоритма приведен контрпример и предложен метод избавления от найденного недостатка.
В результате работы получились графики, описывающие эффективность работы алгоритма, а также улучшено доказательство корректности его работы.
Результаты этой работы можно применить для дальнейшего изучения алгоритма, высказывания предположений о возможности довести его до конца или наоборот придумать контрпример.
We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean Space. In particular, an article «Towards Asymptotically Optimal One-to-One PDP Algorithms for Capacity 2+ Vehicles».
In this work presented results of experiments and some theoretical conclusions. Experiments were aimed at testing the hypothesis that the algorithm is correct. Experimental results are graphs of the ratio of the result of an approximate algorithm to the exact solution.
Also in this work are corrections of the proof of the correctness of the algorithm. They do not close all the spaces of the studied algorithm, but bring us to the end.
The results of this work can be used to complete proof of correctness of the algorithm under study.