search

luukvdmeer / sfnetworks

Tidy Geospatial Networks in R
https://luukvdmeer.github.io/sfnetworks/
Other
347 stars 20 forks source link

Solving the chinese postman problem #274

Open nikosGeography opened 2 weeks ago

nikosGeography commented 2 weeks ago

Hi, thank you for creating this amazing package. I am trying to solve the chinese postman problem (CPP). So far, I followed the tutorial found here, where I just set 10 points that the postman needs to pass from, given that the starting and ending point are the same. The code:

library(sfnetworks)
library(sf)
library(tidygraph)
library(dplyr)
library(purrr)
library(TSP)
library(igraph)

# Read road layer
r <- st_read("path/test_road.geojson")

# convert to linestring
r_lines = st_cast(r, "LINESTRING")

# Plot the road network (r)
plot(r_lines, col = "gray", lwd = 2, main = "Road Network with Points Overlay")

net = as_sfnetwork(r_lines, directed = FALSE) %>%
  activate("edges") %>%
  mutate(weight = edge_length())

plot(net)

set.seed(403)
rdm = net %>%
  st_bbox() %>%
  st_as_sfc() %>%
  st_sample(10, type = "random")

net = activate(net, "nodes")
cost_matrix = st_network_cost(net, from = rdm, to = rdm, weights = "weight")

# Use nearest node indices as row and column names.
rdm_idxs = st_nearest_feature(rdm, net)
row.names(cost_matrix) = rdm_idxs
colnames(cost_matrix) = rdm_idxs

round(cost_matrix, 0)

tour = solve_TSP(TSP(units::drop_units(cost_matrix)))
tour_idxs = as.numeric(names(tour))
tour_idxs

# Approximate length of the route.
# In meters, since that was the unit of our cost values.
round(tour_length(tour), 0)

# Define the nodes to calculate the shortest paths from.
# Define the nodes to calculate the shortest paths to.
# All based on the calculated order of visit.
from_idxs = tour_idxs
to_idxs = c(tour_idxs[2:length(tour_idxs)], tour_idxs[1])

# Calculate the specified paths.
tsp_paths = mapply(st_network_paths,
                   from = from_idxs,
                   to = to_idxs,
                   MoreArgs = list(x = net, weights = "weight")
)["node_paths", ] %>%
  unlist(recursive = FALSE)

# Plot the results.
plot(net, col = "grey")

colors <- c("red", "blue", "green")
plot(rdm, pch = 20, col = colors[2], add = TRUE)

plot_path = function(node_path) {
  net %>%
    activate("nodes") %>%
    slice(node_path) %>%
    plot(cex = 1.5, lwd = 1.5, add = TRUE)
}

walk(tsp_paths, plot_path) # Reuse the plot_path function defined earlier.

plot(
  st_as_sf(slice(net, rdm_idxs)),
  pch = 20, col = colors[3], add = TRUE
)
plot(
  st_as_sf(slice(net, tour_idxs[1])),
  pch = 8, cex = 2, lwd = 2, col = colors[3], add = TRUE
)
text(
  st_coordinates(st_as_sf(slice(net, tour_idxs[1]))) - c(200, 90),
  labels = "start/end\npoint"
)

Now I want to set a point (see the dput(p) below) which will serve as my starting and ending point but the postman needs to pass from every street (if possible) instead of 10 random points. I tried fe things without success (that's why I'm not posting ane example). I am very new to graphs so any help to point me to the right direction would be nice.

The dataset I am using:

> dput(p)
structure(list(FID = 0L, geometry = structure(list(structure(c(372565.229777976, 
4459009.54067835), class = c("XY", "POINT", "sfg"))), n_empty = 0L, crs = structure(list(
    input = "GGRS87 / Greek Grid", wkt = "PROJCRS[\"GGRS87 / Greek Grid\",\n    BASEGEOGCRS[\"GGRS87\",\n        DATUM[\"Greek Geodetic Reference System 1987\",\n            ELLIPSOID[\"GRS 1980\",6378137,298.257222101,\n                LENGTHUNIT[\"metre\",1]]],\n        PRIMEM[\"Greenwich\",0,\n            ANGLEUNIT[\"degree\",0.0174532925199433]],\n        ID[\"EPSG\",4121]],\n    CONVERSION[\"Greek Grid\",\n        METHOD[\"Transverse Mercator\",\n            ID[\"EPSG\",9807]],\n        PARAMETER[\"Latitude of natural origin\",0,\n            ANGLEUNIT[\"degree\",0.0174532925199433],\n            ID[\"EPSG\",8801]],\n        PARAMETER[\"Longitude of natural origin\",24,\n            ANGLEUNIT[\"degree\",0.0174532925199433],\n            ID[\"EPSG\",8802]],\n        PARAMETER[\"Scale factor at natural origin\",0.9996,\n            SCALEUNIT[\"unity\",1],\n            ID[\"EPSG\",8805]],\n        PARAMETER[\"False easting\",500000,\n            LENGTHUNIT[\"metre\",1],\n            ID[\"EPSG\",8806]],\n        PARAMETER[\"False northing\",0,\n            LENGTHUNIT[\"metre\",1],\n            ID[\"EPSG\",8807]]],\n    CS[Cartesian,2],\n        AXIS[\"(E)\",east,\n            ORDER[1],\n            LENGTHUNIT[\"metre\",1]],\n        AXIS[\"(N)\",north,\n            ORDER[2],\n            LENGTHUNIT[\"metre\",1]],\n    USAGE[\n        SCOPE[\"Engineering survey, topographic mapping.\"],\n        AREA[\"Greece - onshore.\"],\n        BBOX[34.88,19.57,41.75,28.3]],\n    ID[\"EPSG\",2100]]"), class = "crs"), class = c("sfc_POINT", 
"sfc"), precision = 0, bbox = structure(c(xmin = 372565.229777976, 
ymin = 4459009.54067835, xmax = 372565.229777976, ymax = 4459009.54067835
), class = "bbox"))), row.names = c(NA, -1L), class = c("sf", 
"data.frame"), sf_column = "geometry", agr = structure(c(FID = NA_integer_), class = "factor", levels = c("constant", 
"aggregate", "identity")))

And the road network

> dput(r)
structure(list(name = "Μάρκου Μπότσαρη", geometry = structure(list(
    structure(list(structure(c(372331.171496477, 372323.71387849, 
    372315.862455991, 4459265.71330238, 4459268.77085101, 4459272.10572613
    ), dim = 3:2), structure(c(372327.250114144, 372315.862455991, 
    4459029.02101375, 4459033.61097549), dim = c(2L, 2L)), structure(c(372425.998471711, 
    372355.28531116, 372332.212249386, 372315.862455991, 4459031.08096448, 
    4459074.98110706, 4459084.02118434, 4459091.27234815), dim = c(4L, 
    2L)), structure(c(372315.862455991, 372324.291625168, 372327.250114144, 
    4459002.16065687, 4459022.05371752, 4459029.02101375), dim = 3:2), 
        structure(c(372351.728687763, 372315.862455991, 4458925.62234998, 
        4458934.61508127), dim = c(2L, 2L)), structure(c(372388.120837829, 
        372315.862455991, 4458755.71257, 4458809.57067311), dim = c(2L, 
        2L)), structure(c(372315.862455991, 372331.171496477, 
        4459225.03108864, 4459265.71330238), dim = c(2L, 2L)), 
        structure(c(372315.862455991, 372350.443884868, 4459155.60275307, 
        4459144.19304877), dim = c(2L, 2L)), structure(c(372331.950279474, 
        372315.862455991, 4458883.63077904, 4458863.38710352), dim = c(2L, 
        2L)), structure(c(372411.1717889, 372405.546088531, 372327.250114144, 
        4458995.20117475, 4458997.47260873, 4459029.02101375), dim = 3:2), 
        structure(c(372331.171496477, 372339.4230625, 4459265.71330238, 
        4459287.6402455), dim = c(2L, 2L)), structure(c(372411.840269468, 
        372339.087098668, 372335.133547761, 372331.171496477, 
        4459233.81379162, 4459262.58138885, 4459264.1472726, 
        4459265.71330238), dim = c(4L, 2L)), structure(c(372351.728687763, 
        372331.950279474, 4458925.62234998, 4458883.63077904), dim = c(2L, 
        2L)), structure(c(372331.950279474, 372394.084331078, 
        372420.298520975, 372420.676438207, 372426.995384351, 
        4458883.63077904, 4458836.24479999, 4458816.25935896, 
        4458815.97538158, 4458811.43824502), dim = c(5L, 2L)), 
        structure(c(372350.443884868, 372362.70250718, 372364.584167143, 
        372366.193394179, 372368.262343077, 372371.680158149, 
        372393.942817164, 4459144.19304877, 4459194.66169088, 
        4459197.80543232, 4459198.9218549, 4459199.56415401, 
        4459199.50631908, 4459189.83605974), dim = c(7L, 2L)), 
        structure(c(372350.443884868, 372372.424553023, 4459144.19304877, 
        4459136.94805411), dim = c(2L, 2L)), structure(c(372379.443830498, 
        372351.728687763, 4458917.96946853, 4458925.62234998), dim = c(2L, 
        2L)), structure(c(372388.120837829, 372383.466500907, 
        372382.183500364, 4458755.71257, 4458749.05152587, 4458747.21292938
        ), dim = 3:2), structure(c(372393.942817164, 372372.424553023, 
        4459189.83605974, 4459136.94805411), dim = c(2L, 2L)), 
        structure(c(372372.424553023, 372399.381232882, 372415.366630053, 
        372449.231597598, 4459136.94805411, 4459126.23239483, 
        4459115.99109722, 4459087.31555485), dim = c(4L, 2L)), 
        structure(c(372379.443830498, 372381.393734811, 372411.1717889, 
        4458917.96946853, 4458923.13288549, 4458995.20117475), dim = 3:2), 
        structure(c(372475.683278166, 372379.443830498, 4458881.21058003, 
        4458917.96946853), dim = c(2L, 2L)), structure(c(372426.995384351, 
        372425.53092642, 372388.120837829, 4458811.43824502, 
        4458809.33115369, 4458755.71257), dim = 3:2), structure(c(372411.840269468, 
        372409.471279806, 372393.942817164, 4459233.81379162, 
        4459228.00235486, 4459189.83605974), dim = 3:2), structure(c(372401.541982607, 
        372442.909196322, 4459089.0659524, 4459072.02201132), dim = c(2L, 
        2L)), structure(c(372411.1717889, 372425.998471711, 4458995.20117475, 
        4459031.08096448), dim = c(2L, 2L)), structure(c(372494.146046746, 
        372421.972016296, 372414.346857794, 372411.1717889, 4458960.13252618, 
        4458990.63264047, 4458993.85947081, 4458995.20117475), dim = c(4L, 
        2L)), structure(c(372433.620073116, 372413.622587924, 
        372411.840269468, 4459286.60864481, 4459238.12508567, 
        4459233.81379162), dim = 3:2), structure(c(372495.652299343, 
        372411.840269468, 4459199.66355638, 4459233.81379162), dim = c(2L, 
        2L)), structure(c(372425.998471711, 372442.909196322, 
        4459031.08096448, 4459072.02201132), dim = c(2L, 2L)), 
        structure(c(372475.683278166, 372473.094452335, 372428.782129269, 
        372426.995384351, 4458881.21058003, 4458877.49028502, 
        4458813.99512675, 4458811.43824502), dim = c(4L, 2L)), 
        structure(c(372426.995384351, 372429.078410101, 372515.36947322, 
        4458811.43824502, 4458810.39260529, 4458770.66027468), dim = 3:2), 
        structure(c(372434.045880691, 372433.620073116, 4459287.6402455, 
        4459286.60864481), dim = c(2L, 2L)), structure(c(372433.620073116, 
        372438.047485502, 372460.573225249, 4459286.60864481, 
        4459284.9015573, 4459276.21524282), dim = 3:2), structure(c(372442.909196322, 
        372449.231597598, 4459072.02201132, 4459087.31555485), dim = c(2L, 
        2L)), structure(c(372442.909196322, 372526.073897295, 
        4459072.02201132, 4459037.19473621), dim = c(2L, 2L)), 
        structure(c(372449.231597598, 372493.080876287, 372493.63921011, 
        372495.652299343, 4459087.31555485, 4459193.44469101, 
        4459194.7787675, 4459199.66355638), dim = c(4L, 2L)), 
        structure(c(372494.146046746, 372498.08913557, 372496.71423948, 
        372462.341729796, 4458960.13252618, 4458972.02426502, 
        4458976.72204852, 4458998.05545602), dim = c(4L, 2L)), 
        structure(c(372488.155670444, 372475.683278166, 4458899.07611202, 
        4458881.21058003), dim = c(2L, 2L)), structure(c(372563.303381123, 
        372536.84456466, 372512.064818951, 372475.683278166, 
        4458833.59508018, 4458844.65699351, 4458859.95433999, 
        4458881.21058003), dim = c(4L, 2L)), structure(c(372487.950277632, 
        372485.883276946, 4459286.86688381, 4459287.6402455), dim = c(2L, 
        2L)), structure(c(372488.240924526, 372487.950277632, 
        4459287.6402455, 4459286.86688381), dim = c(2L, 2L)), 
        structure(c(372513.513434923, 372487.950277632, 4459277.25220729, 
        4459286.86688381), dim = c(2L, 2L)), structure(c(372633.626687507, 
        372578.910469327, 372498.198580993, 372493.450884199, 
        372489.29474097, 372488.155670444, 4458877.72041315, 
        4458894.55569152, 4458897.99586934, 4458897.87625933, 
        4458899.54540768, 4458899.07611202), dim = c(6L, 2L)), 
        structure(c(372521.493999088, 372518.164698517, 372492.156389154, 
        372488.155670444, 4458946.85693721, 4458942.09431686, 
        4458904.81557573, 4458899.07611202), dim = c(4L, 2L)), 
        structure(c(372521.493999088, 372515.055830117, 372508.937437037, 
        372494.146046746, 4458946.85693721, 4458950.37449769, 
        4458953.18714325, 4458960.13252618), dim = c(4L, 2L)), 
        structure(c(372495.652299343, 372497.461020307, 372498.028605268, 
        372525.851592997, 4459199.66355638, 4459204.02993922, 
        4459205.40827334, 4459272.62450014), dim = c(4L, 2L)), 
        structure(c(372578.886293424, 372495.652299343, 4459165.99039429, 
        4459199.66355638), dim = c(2L, 2L)), structure(c(372515.36947322, 
        372512.167432408, 4458770.66027468, 4458747.21292938), dim = c(2L, 
        2L)), structure(c(372529.362816795, 372523.178989589, 
        372521.28487648, 372519.285985315, 372517.403365714, 
        372515.85975603, 372514.827446265, 372513.513434923, 
        4459281.11479863, 4459283.56213745, 4459284.20484021, 
        4459284.18310855, 4459283.49320621, 4459282.2312991, 
        4459280.52771602, 4459277.25220729), dim = c(8L, 2L)), 
        structure(c(372525.851592997, 372513.513434923, 4459272.62450014, 
        4459277.25220729), dim = c(2L, 2L)), structure(c(372543.870374482, 
        372541.676052447, 372521.591784252, 372517.190023592, 
        372515.36947322, 4458816.01358656, 4458813.99653013, 
        4458784.5565358, 4458774.71556709, 4458770.66027468), dim = c(5L, 
        2L)), structure(c(372515.36947322, 372553.115669839, 
        4458770.66027468, 4458768.72335815), dim = c(2L, 2L)), 
        structure(c(372537.618111405, 372524.126228008, 372521.493999088, 
        4458969.95716384, 4458950.63203097, 4458946.85693721), dim = 3:2), 
        structure(c(372525.851592997, 372529.362816795, 4459272.62450014, 
        4459281.11479863), dim = c(2L, 2L)), structure(c(372526.073897295, 
        372528.353510463, 372576.659825342, 372578.886293424, 
        4459037.19473621, 4459042.75233817, 4459160.55401878, 
        4459165.99039429), dim = c(4L, 2L)), structure(c(372526.073897295, 
        372558.630099393, 372561.450711981, 372570.302410854, 
        4459037.19473621, 4459023.63139223, 4459022.45118744, 
        4459016.81654958), dim = c(4L, 2L)), structure(c(372529.362816795, 
        372530.799036789, 372532.055569381, 4459281.11479863, 
        4459284.57700274, 4459287.6402455), dim = 3:2), structure(c(372570.302410854, 
        372565.229777976, 372537.618111405, 4459016.81654958, 
        4459009.54067835, 4458969.95716384), dim = 3:2), structure(c(372537.618111405, 
        372541.799980722, 372568.95593452, 372589.436508272, 
        372631.232602099, 372652.878696574, 372656.086907454, 
        4458969.95716384, 4458967.7990554, 4458952.21737299, 
        4458945.74231598, 4458933.37785935, 4458923.89647952, 
        4458922.49880384), dim = c(7L, 2L)), structure(c(372579.276818351, 
        372621.754110409, 4459287.6402455, 4459270.53788831), dim = c(2L, 
        2L)), structure(c(372563.303381123, 372556.242055104, 
        372543.870374482, 4458833.59508018, 4458827.41873754, 
        4458816.01358656), dim = 3:2), structure(c(372543.870374482, 
        372565.277486888, 372553.115669839, 4458816.01358656, 
        4458796.39858156, 4458768.72335815), dim = 3:2), structure(c(372553.115669839, 
        372595.977764616, 4458768.72335815, 4458766.54477785), dim = c(2L, 
        2L)), structure(c(372618.599101946, 372610.606162934, 
        372574.578284407, 372563.303381123, 4458825.36617281, 
        4458827.47755904, 4458836.9688085, 4458833.59508018), dim = c(4L, 
        2L)), structure(c(372584.726863482, 372574.372338401, 
        372570.302410854, 4459037.49172549, 4459022.63260773, 
        4459016.81654958), dim = 3:2), structure(c(372679.726551937, 
        372672.681197858, 372670.47144127, 372665.665393329, 
        372574.322220816, 372570.302410854, 4458938.41067075, 
        4458946.26867454, 4458948.37121123, 4458952.34964005, 
        4459014.12823184, 4459016.81654958), dim = c(6L, 2L)), 
        structure(c(372578.886293424, 372581.166021074, 372618.747471308, 
        372621.754110409, 4459165.99039429, 4459171.55911175, 
        4459263.21599214, 4459270.53788831), dim = c(4L, 2L)), 
        structure(c(372653.596668956, 372646.708254502, 372645.567782149, 
        372578.886293424, 4459136.18173349, 4459139.21823795, 
        4459139.67052786, 4459165.99039429), dim = c(4L, 2L)), 
        structure(c(372625.942644341, 372584.726863482, 4459096.55422613, 
        4459037.49172549), dim = c(2L, 2L)), structure(c(372614.498239214, 
        372584.726863482, 4459016.64741106, 4459037.49172549), dim = c(2L, 
        2L)), structure(c(372595.977764616, 372596.718849921, 
        4458766.54477785, 4458747.21292938), dim = c(2L, 2L)), 
        structure(c(372595.977764616, 372620.913632743, 372621.772011451, 
        372628.290625758, 4458766.54477785, 4458765.50187876, 
        4458765.46517742, 4458765.18855659), dim = c(4L, 2L)), 
        structure(c(372618.599101946, 372620.325600058, 372629.282132992, 
        372632.048054892, 4458825.36617281, 4458831.41058767, 
        4458862.69312365, 4458872.37301422), dim = c(4L, 2L)), 
        structure(c(372620.879673557, 372618.892000295, 372618.599101946, 
        4458802.77662178, 4458812.49236602, 4458825.36617281), dim = 3:2), 
        structure(c(372620.879673557, 372642.925508908, 372647.036793566, 
        4458802.77662178, 4458807.37871436, 4458809.59660711), dim = 3:2), 
        structure(c(372628.290625758, 372626.754959935, 372620.879673557, 
        4458765.18855659, 4458772.96467082, 4458802.77662178), dim = 3:2), 
        structure(c(372621.754110409, 372624.565828037, 372628.766503267, 
        4459270.53788831, 4459277.39673353, 4459287.6402455), dim = 3:2), 
        structure(c(372621.754110409, 372712.434662919, 372715.069859153, 
        372719.676089948, 4459270.53788831, 4459233.66478364, 
        4459232.58769363, 4459230.88886116), dim = c(4L, 2L)), 
        structure(c(372653.596668956, 372648.733490527, 372625.942644341, 
        4459136.18173349, 4459129.21317058, 4459096.55422613), dim = 3:2), 
        structure(c(372715.466801415, 372670.34047184, 372643.702243635, 
        372625.942644341, 4459084.26153859, 4459092.76227017, 
        4459089.62559689, 4459096.55422613), dim = c(4L, 2L)), 
        structure(c(372638.282196632, 372633.456720675, 372628.290625758, 
        4458747.21292938, 4458754.31991252, 4458765.18855659), dim = 3:2), 
        structure(c(372632.048054892, 372632.978904671, 372633.626687507, 
        4458872.37301422, 4458875.62170157, 4458877.72041315), dim = 3:2), 
        structure(c(372724.832852838, 372716.066114533, 372640.848021844, 
        372640.130121939, 372632.048054892, 4458769.88800428, 
        4458779.57375349, 4458862.65328587, 4458863.45374942, 
        4458872.37301422), dim = c(5L, 2L)), structure(c(372633.626687507, 
        372656.086907454, 4458877.72041315, 4458922.49880384), dim = c(2L, 
        2L)), structure(c(372719.676089948, 372715.196484315, 
        372656.516459642, 372653.596668956, 4459230.88886116, 
        4459224.46895727, 4459140.37394422, 4459136.18173349), dim = c(4L, 
        2L)), structure(c(372719.147504804, 372661.448636493, 
        372660.42662954, 372653.596668956, 4459109.85942274, 
        4459133.29551955, 4459133.71249687, 4459136.18173349), dim = c(4L, 
        2L)), structure(c(372656.086907454, 372669.031695618, 
        372677.099807638, 372679.726551937, 4458922.49880384, 
        4458931.09639172, 4458936.4674968, 4458938.41067075), dim = c(4L, 
        2L)), structure(c(372707.349931356, 372660.058275154, 
        4458751.4293388, 4458795.51971857), dim = c(2L, 2L)), 
        structure(c(372707.349931356, 372703.356185608, 4458751.4293388, 
        4458747.21292938), dim = c(2L, 2L)), structure(c(372710.071099679, 
        372692.733999056, 372674.681590893, 4459023.56138954, 
        4459024.79777269, 4459038.07127213), dim = 3:2), structure(c(372679.726551937, 
        372683.259268735, 372687.754402132, 372704.82907403, 
        372705.968202779, 372707.001369804, 4458938.41067075, 
        4458941.62655015, 4458946.43618258, 4458974.99468618, 
        4458977.48483418, 4458979.7435988), dim = c(6L, 2L)), 
        structure(c(372702.057037585, 372685.674344918, 372679.726551937, 
        4458914.55006388, 4458932.03684992, 4458938.41067075), dim = 3:2), 
        structure(c(372688.091269934, 372702.057037585, 4458900.38463411, 
        4458914.55006388), dim = c(2L, 2L)), structure(c(372764.535710698, 
        372727.021065183, 372722.173972725, 372695.566719913, 
        4458820.92680644, 4458839.09195369, 4458840.13973362, 
        4458858.54294262), dim = c(4L, 2L)), structure(c(372775.231808861, 
        372702.057037585, 4458836.37999951, 4458914.55006388), dim = c(2L, 
        2L)), structure(c(372707.001369804, 372707.415048172, 
        372710.071099679, 4458979.7435988, 4458985.6103243, 4459023.56138954
        ), dim = 3:2), structure(c(372707.001369804, 372712.842938352, 
        372789.18838345, 4458979.7435988, 4458976.14744486, 4458929.18008191
        ), dim = 3:2), structure(c(372713.41145716, 372707.349931356, 
        4458757.83365505, 4458751.4293388), dim = c(2L, 2L)), 
        structure(c(372710.071099679, 372712.902102071, 372713.443452902, 
        4459023.56138954, 4459065.32907987, 4459070.19434417), dim = 3:2), 
        structure(c(372724.832852838, 372713.41145716, 4458769.88800428, 
        4458757.83365505), dim = c(2L, 2L)), structure(c(372728.225966652, 
        372724.737217865, 372713.41145716, 4458747.21292938, 
        4458748.59327748, 4458757.83365505), dim = 3:2), structure(c(372713.443452902, 
        372715.466801415, 4459070.19434417, 4459084.26153859), dim = c(2L, 
        2L)), structure(c(372713.443452902, 372717.7021737, 4459070.19434417, 
        4459069.56730723), dim = c(2L, 2L)), structure(c(372715.466801415, 
        372717.894811629, 372718.155463491, 372719.147504804, 
        4459084.26153859, 4459101.14217278, 4459102.98094148, 
        4459109.85942274), dim = c(4L, 2L)), structure(c(372717.882258916, 
        372717.7021737, 4459070.66350654, 4459069.56730723), dim = c(2L, 
        2L)), structure(c(372717.7021737, 372745.001838069, 372745.756845638, 
        372750.660237863, 4459069.56730723, 4459065.53138185, 
        4459065.41871334, 4459064.69199169), dim = c(4L, 2L)), 
        structure(c(372726.063380886, 372717.882258916, 4459077.19860946, 
        4459070.66350654), dim = c(2L, 2L)), structure(c(372719.270268044, 
        372716.983090029, 372717.882258916, 4459086.89548569, 
        4459070.80081742, 4459070.66350654), dim = 3:2), structure(c(372717.882258916, 
        372732.182819572, 4459070.66350654, 4459068.4013802), dim = c(2L, 
        2L)), structure(c(372719.147504804, 372740.840927592, 
        372750.853774418, 372757.302666213, 4459109.85942274, 
        4459159.15896159, 4459167.40641898, 4459181.16578941), dim = c(4L, 
        2L)), structure(c(372761.841132098, 372719.147504804, 
        4459093.27231908, 4459109.85942274), dim = c(2L, 2L)), 
        structure(c(372746.270160879, 372721.519308904, 372719.270268044, 
        4459093.32403754, 4459102.74652306, 4459086.89548569), dim = 3:2), 
        structure(c(372726.063380886, 372719.270268044, 4459077.19860946, 
        4459086.89548569), dim = c(2L, 2L)), structure(c(372759.267017047, 
        372723.789801374, 372719.676089948, 4459287.6402455, 
        4459236.7930812, 4459230.88886116), dim = 3:2), structure(c(372719.676089948, 
        372728.803985399, 372811.467851055, 4459230.88886116, 
        4459227.01518493, 4459191.87970394), dim = 3:2), structure(c(372764.535710698, 
        372748.307124369, 372742.249925305, 372724.832852838, 
        4458820.92680644, 4458790.59955852, 4458783.4401113, 
        4458769.88800428), dim = c(4L, 2L)), structure(c(372776.342907235, 
        372724.832852838, 4458747.21292938, 4458769.88800428), dim = c(2L, 
        2L)), structure(c(372746.270160879, 372726.063380886, 
        4459093.32403754, 4459077.19860946), dim = c(2L, 2L)), 
        structure(c(372732.182819572, 372726.063380886, 4459068.4013802, 
        4459077.19860946), dim = c(2L, 2L)), structure(c(372732.182819572, 
        372745.669239615, 372748.594016135, 372746.270160879, 
        4459068.4013802, 4459066.27515425, 4459092.44097239, 
        4459093.32403754), dim = c(4L, 2L)), structure(c(372750.660237863, 
        372753.964302776, 372761.841132098, 4459064.69199169, 
        4459085.11094719, 4459093.27231908), dim = 3:2), structure(c(372811.467851055, 
        372795.501737663, 372764.79484173, 372760.617880042, 
        372750.660237863, 4458986.09801078, 4458996.92654861, 
        4459025.86918926, 4459032.85707478, 4459064.69199169), dim = c(5L, 
        2L)), structure(c(372761.841132098, 372778.664880873, 
        372811.467851055, 4459093.27231908, 4459100.93858119, 
        4459115.88408619), dim = 3:2), structure(c(372761.841132098, 
        372769.513486753, 372774.856961648, 372811.467851055, 
        4459093.27231908, 4459086.79174529, 4459084.42541387, 
        4459068.2532027), dim = c(4L, 2L)), structure(c(372775.231808861, 
        372769.815975229, 372764.535710698, 4458836.37999951, 
        4458831.44150011, 4458820.92680644), dim = 3:2), structure(c(372810.610403678, 
        372811.467851055, 4459287.6402455, 4459287.17246919), dim = c(2L, 
        2L)), structure(c(372811.467851055, 372775.231808861, 
        4458867.06172629, 4458836.37999951), dim = c(2L, 2L)), 
        structure(c(372788.492465124, 372780.198428144, 372775.231808861, 
        4458818.8239395, 4458829.81184444, 4458836.37999951), dim = 3:2), 
        structure(c(372797.848654026, 372780.528834796, 4458766.92428906, 
        4458747.21292938), dim = c(2L, 2L)), structure(c(372783.746943732, 
        372789.18838345, 4458903.55635503, 4458929.18008191), dim = c(2L, 
        2L)), structure(c(372811.467851055, 372788.492465124, 
        4458831.32524682, 4458818.8239395), dim = c(2L, 2L)), 
        structure(c(372811.467851055, 372792.818645437, 372788.492465124, 
        4458800.06854494, 4458813.11045318, 4458818.8239395), dim = 3:2), 
        structure(c(372789.18838345, 372811.467851055, 4458929.18008191, 
        4458915.20126938), dim = c(2L, 2L)), structure(c(372811.467851055, 
        372797.848654026, 4458782.41268385, 4458766.92428906), dim = c(2L, 
        2L)), structure(c(372797.848654026, 372811.467851055, 
        4458766.92428906, 4458759.06070508), dim = c(2L, 2L))), class = c("XY", 
    "MULTILINESTRING", "sfg"))), n_empty = 0L, crs = structure(list(
    input = "GGRS87 / Greek Grid", wkt = "PROJCRS[\"GGRS87 / Greek Grid\",\n    BASEGEOGCRS[\"GGRS87\",\n        DATUM[\"Greek Geodetic Reference System 1987\",\n            ELLIPSOID[\"GRS 1980\",6378137,298.257222101,\n                LENGTHUNIT[\"metre\",1]]],\n        PRIMEM[\"Greenwich\",0,\n            ANGLEUNIT[\"degree\",0.0174532925199433]],\n        ID[\"EPSG\",4121]],\n    CONVERSION[\"Greek Grid\",\n        METHOD[\"Transverse Mercator\",\n            ID[\"EPSG\",9807]],\n        PARAMETER[\"Latitude of natural origin\",0,\n            ANGLEUNIT[\"degree\",0.0174532925199433],\n            ID[\"EPSG\",8801]],\n        PARAMETER[\"Longitude of natural origin\",24,\n            ANGLEUNIT[\"degree\",0.0174532925199433],\n            ID[\"EPSG\",8802]],\n        PARAMETER[\"Scale factor at natural origin\",0.9996,\n            SCALEUNIT[\"unity\",1],\n            ID[\"EPSG\",8805]],\n        PARAMETER[\"False easting\",500000,\n            LENGTHUNIT[\"metre\",1],\n            ID[\"EPSG\",8806]],\n        PARAMETER[\"False northing\",0,\n            LENGTHUNIT[\"metre\",1],\n            ID[\"EPSG\",8807]]],\n    CS[Cartesian,2],\n        AXIS[\"(E)\",east,\n            ORDER[1],\n            LENGTHUNIT[\"metre\",1]],\n        AXIS[\"(N)\",north,\n            ORDER[2],\n            LENGTHUNIT[\"metre\",1]],\n    USAGE[\n        SCOPE[\"Engineering survey, topographic mapping.\"],\n        AREA[\"Greece - onshore.\"],\n        BBOX[34.88,19.57,41.75,28.3]],\n    ID[\"EPSG\",2100]]"), class = "crs"), class = c("sfc_MULTILINESTRING", 
"sfc"), precision = 0, bbox = structure(c(xmin = 372315.862455991, 
ymin = 4458747.21292938, xmax = 372811.467851055, ymax = 4459287.6402455
), class = "bbox"))), row.names = c(NA, -1L), class = c("sf", 
"data.frame"), sf_column = "geometry", agr = structure(c(name = NA_integer_), class = "factor", levels = c("constant", 
"aggregate", "identity")))
> sessionInfo()
R version 4.4.1 (2024-06-14 ucrt)
Platform: x86_64-w64-mingw32/x64
Running under: Windows 10 x64 (build 19045)

Matrix products: default

locale:
[1] LC_COLLATE=English_United States.utf8  LC_CTYPE=English_United States.utf8   
[3] LC_MONETARY=English_United States.utf8 LC_NUMERIC=C                          
[5] LC_TIME=English_United States.utf8    

time zone: Europe/London
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] igraph_2.0.3     TSP_1.2-4        purrr_1.0.2      dplyr_1.1.4     
[5] tidygraph_1.3.1  sf_1.0-17        sfnetworks_0.6.4

loaded via a namespace (and not attached):
 [1] utf8_1.2.4             generics_0.1.3         tidyr_1.3.1           
 [4] spatstat.explore_3.3-2 class_7.3-22           lwgeom_0.2-14         
 [7] KernSmooth_2.23-24     tensor_1.5             spatstat.data_3.1-2   
[10] lattice_0.22-6         magrittr_2.0.3         spatstat.utils_3.1-0  
[13] grid_4.4.1             iterators_1.0.14       foreach_1.5.2         
[16] Matrix_1.7-0           spatstat.linnet_3.2-2  spatstat.sparse_3.1-0 
[19] e1071_1.7-16           DBI_1.2.3              mgcv_1.9-1            
[22] spatstat.model_3.3-2   fansi_1.0.6            scales_1.3.0          
[25] codetools_0.2-20       abind_1.4-8            cli_3.6.3             
[28] rlang_1.1.4            crayon_1.5.3           units_0.8-5           
[31] polyclip_1.10-7        splines_4.4.1          munsell_0.5.1         
[34] spatstat.univar_3.0-1  tools_4.4.1            sfheaders_0.4.4       
[37] deldir_2.0-4           colorspace_2.1-1       ggplot2_3.5.1         
[40] spatstat.geom_3.3-3    rpart_4.1.23           vctrs_0.6.5           
[43] R6_2.5.1               proxy_0.4-27           lifecycle_1.0.4       
[46] classInt_0.4-10        pkgconfig_2.0.3        pillar_1.9.0          
[49] gtable_0.3.5           glue_1.7.0             Rcpp_1.0.13           
[52] tibble_3.2.1           tidyselect_1.2.1       rstudioapi_0.16.0     
[55] goftest_1.2-3          nlme_3.1-166           spatstat.random_3.3-2 
[58] compiler_4.4.1
luukvdmeer commented 2 weeks ago

The Travelling Salesman Problem finds the optimal route visiting a set of nodes, while (if I am right) the Chinese Postman Problem finds the optimal route visiting a set of edges. How this could normally be solved is by converting the network to its linegraph, in which nodes become edges and vice versa, using tidygraph::to_linegraph(), and then solving a regular TSP. However I have not tried myself before if it works well with sfnetwork objects for this case, would be interesting to find out!