Solution optimale non trouvée et Récuperation de l'ordre de passage du livreur

[tawoudoumelone]

Hello, I am a student who used your algorithm to solve a route plan to collect parcels in the city of Paris. I have two problems:

• Sometimes my algorithm encountered too long to find an optimal solution for my number of addresses to visit n = 30. It encountered more than 2 hours of time. Is there a way to get around this concern.

• I cannot recover the order of passage it can start from point A to point C then from M to G. There is no consistency while the it should do from A to C Then from C to M and finally from M to G. How could I recover a well-ordered passage order.

---

library(tidyverse) #pour ordonner les données
library(ggplot2) #la visualisation
library(ompr) #resolution du tsp
library(ompr.roi) #resolution du tsp
library(ROI.plugin.glpk) ##resolution du tsp
library(tidygeocoder)#geocdage
library(knitr)
library(dplyr) # le pipe %>% ne serait pas utilisable
library(tibble) # Pour mon data frame
library(plotly) # Pour les graphes interactifs

set.seed(75)

routes<- data_frame(Nom = c("Chez Lloyd",
"Chez Nzulo",
"Chez les Jumeaux",
"Chez Kevin",
"Ikea Franconville",
"Université Evry",
"Chez Yann",
"Chez Waly",
"Chez Tc",
"Vuitton Champs",
"Chez Messi " ,
"Chez Drogba" ,
"Chez Batistuta" ,
" Chez Govou" ,
"Chez Mbappe",
"Chez Zidane",
"Université Nanterre",
"Univ Orsay",
"Univ Creteil",
"Univ Versailles"),

                Adresse =c("9 rue bausset, 75015 Paris, France",
                           "3 rue marcel gimond, 92350 Le Plessis-Robinson, France",
                           "18 rue charles Michels, 92220 Bagneux, France",
                           "21 rue de seine ,92220 Boulogne Billancourt, France",
                           "337 rue du Général Leclerc, 95130 Franconville, France",
                           " 23 Boulevard François Mitterrand, 91000 Évry , France",
                           " 33  rue de crimée, 75019 Paris, France",
                           " 10 rue  des prairies, 75020 Paris, France",
                           " 7 rue jean maridor , 75015 Paris , France",
                           " 101 Avenue des champs-élysées ,75008 Paris , France",
                           "38 Esplanade de l'Europe, 95100 Argenteuil, France",
                           "11 avenue de l'Europe, 92270 Bois-colombes, France",
                           "20 rue Georges Méliès, 78390 Bois-d'Arcy, France",
                           "1 Boulevard de la résistance, 95100 Argenteuil, France",
                           "2 rue Maurice Hartmann, 92130 Issy-les-Moulineaux, France",
                           "16 rue Maurice Ravel, 95280 Jouy-le-Moutier,  France",
                           "200 Avenue de république , 92000 Nanterre , France",
                           "15 rue Georges Clémenceau, 91400 Orsay , France",
                           "61 avenue du Général-de-Gaulle , 94000 Créteil , France",
                           "55  avenue de Paris , 78000 Versailles ,  France"))

n=nrow(routes)
routes=routes[c(1, 4,8, 11,18),]
localisation<- routes %>% geocode(Adresse, method='cascade')

#Pour rétirer la colonne osm que je trouve inutile.
localisation=localisation[,1:4]
cities=data.frame(id= 1:n , x=as.numeric(localisation$lat) , y=as.numeric(localisation$long))

distance <- as.matrix(stats::dist(select(cities, x, y), diag = TRUE, upper = TRUE))
dist_fun <- function(i, j) {
vapply(seq_along(i), function(k) distance[i[k], j[k]], numeric(1L))
}

colnames(distance)=routes$Nom
rownames(distance)=routes$Nom

model <- MIPModel() %>%

we create a variable that is 1 iff we travel from city i to j

add_variable(x[i, j], i = 1:n, j = 1:n,
type = "integer", lb = 0, ub = 1) %>%

a helper variable for the MTZ formulation of the tsp

add_variable(u[i], i = 1:n, lb = 1, ub = n) %>%

minimize travel distance

set_objective(sum_expr(dist_fun(i, j) * x[i, j], i = 1:n, j = 1:n), "min") %>%

you cannot go to the same city

set_bounds(x[i, i], ub = 0, i = 1:n) %>%

leave each city

add_constraint(sum_expr(x[i, j], j = 1:n) == 1, i = 1:n) %>%

visit each city

add_constraint(sum_expr(x[i, j], i = 1:n) == 1, j = 1:n) %>%

ensure no subtours (arc constraints)

add_constraint(u[i] >= 2, i = 2:n) %>%
add_constraint(u[i] - u[j] + 1 <= (n - 1) * (1 - x[i, j]), i = 2:n, j = 2:n)
model

result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))

solution <- get_solution(result, x[i, j]) %>%
filter(value > 0)
kable(head(solution, 3))

paths <- select(solution, i, j) %>%
rename(from = i, to = j) %>%
mutate(trip_id = row_number()) %>%
tidyr::gather(property, idx_val, from:to) %>%
mutate(idx_val = as.integer(idx_val)) %>%
inner_join(cities, by = c("idx_val" = "id"))

kable(head(arrange(paths, trip_id), 2*n))

cities$id=localisation$Nom
colnames(cities)=c("Nom", "lat","long")

paths=full_join(paths , cities , by=c("x"="lat"))[,1:6]

up=ggplot(paths, aes(x=x, y=y , label=Nom))+geom_point(aes(color=Nom))+
geom_line(data = paths, aes(group = trip_id))

pmobile=ggplotly(up)
pmobile

---

Thank you