Сформируем кратчайший круговой маршрут, являющийся приближенным решением задачи коммивояжера для населённых пунктов Можгинского района.
Ранее мы вычислили для них матрицу расстояний (пояснения)…
> require("igraph")
> mozhga <- read.csv("mozhga.csv", sep = ";", dec = ",")
> mozhga.graph <- graph.data.frame(mozhga, directed = FALSE) # Формируем граф,
> mozhga.dist <- shortest.paths(mozhga.graph) # вычисляем матрицу расстояний
> d <- mozhga.dist[grep("_", colnames(mozhga.dist), invert = T),
+ grep("_", rownames(mozhga.dist), invert = T)] # и избавляемся
> # от лишних узлов (предварены символом "_").
… и определили порядок их обхода (пояснения).
> require("TSP")
> mozhga.tsp <- TSP(d)
> mozhga.tour <- solve_TSP(mozhga.tsp, method = "2-opt")
> mozhga.tour.labels <- labels(mozhga.tour)
Элемент списка $vpath, возвращаемого функцией get.shortest.paths {igraph}, содержит номера вершин, составляющих кратчайший маршрут между двумя из них, заданными в качестве параметров.
Функция get.vertex.attribute {igraph} возвращает имя для данного номера вершины.
Код, формирующий список имен населённых пунктов в порядке их участия в маршруте:
> way <- sapply(1:(length(mozhga.tour.labels) - 1), function(x) {
+ get.shortest.paths(mozhga.graph,
+ mozhga.tour.labels[x],
+ mozhga.tour.labels[x + 1])$vpath[[1]][-1]
+ }) # Собираем номера вершин графа, в порядке движения по маршруту.
> way <- unlist(way)
> fullway <- c(mozhga.tour.labels[1], unlist(sapply(way, function(x) {
+ get.vertex.attribute(mozhga.graph, "name", index = x)
+ }))) # Преобразуем номера вершин в названия населённых пунктов и перекрёстков.
> head(fullway) # Выводим начало…
[1] "Ломеслуд" "_1" "_2" "_3" "Полянское" "_3"
> tail(fullway) # … и конец маршрута.
[1] "_2" "_1" "Ломеслуд" "Камышлы" "Ломеслуд" "Кр. Яр"
Итоговый маршрут обхода (общая протяженность — 568.4 км) представлен на иллюстрации.
