Как сделать математическую оптимизацию (TSP) в R, возможно с оптимизацией()

Question

Я работаю над созданием основной проблемы коммивояжера (TSP) в R, но я не нашел нужных ресурсов, чтобы помочь мне использовать optim() с импортированными данными. Или, может быть, optim() на самом деле не то, что я ищу. Я расскажу о своем примере и надеюсь, что вы можете указать мне в правильном направлении или помочь с конкретной проблемой.

Существует множество мест, в которых я пытаюсь найти кратчайший маршрут. Каждое место нужно посещать на маршруте один раз и только один раз. Маршрут должен начинаться и заканчиваться в Origin. Возможные решения:

от происхождения> для Location1> в LOCATION2> и обратно происхождения или

от происхождения> для LOCATION2> в Location1> и обратно происхождения

Я импортировал следующее данные в R:

distances <- read.csv("distances_test.csv") 

ORIGIN-----DESTINATION-----DISTANCE 

Origin-----Location2-------4.161917178 

Origin-----Location1-------31.16857564 

Location1--Location2-------30.75861336 

Location1--Origin----------31.16857564 

Location2--Location1-------30.75861336 

Location2--Origin----------4.161917178 

Теперь я пытаюсь определить, как сказать, что R:

целевая функция заключается в минимизации суммы O f - расстояния, умноженные на x, где x - переменная назначения (x = 0 или 1), указывающая, что выбран конкретный маршрут.

Ограничения являются:

(1) х равен от 0 до 1, х является целым числом (или, если есть ярлык с Optim(), чтобы указать, что х двоичный). (2) сумма x по всем исходным индексам = 1 (т. Е. Грузовик покидает каждое место один раз) (3) сумма x по всем целевым показателям = 1 (то есть грузовик-грузовик прибывает в каждое место один раз) (4) начальный индекс происхождения является Origin (5) окончательный индекс назначения происхождение

С optim(par, objective), я не ясно, о том, что исходные параметры были бы или, как я бы написать эту целевую функцию (т.е. min sum(i=1..n)sum(j=1...n) distance(i,j) * x(i,j))

Answer 1

R может помочь вам, если вы с помощью функции solve(), если хотите решить TSP с помощью простого алгоритма simplex. Вы также можете посмотреть на этом веб-сайте, где несколько эвристик для этой проблемы ar e, реализованный в R. https://operatiology.wordpress.com/2014/05/15/traveling-salesman-problem-in-r/