Discussion :

[itachis]

Bonjour,

Je dois développer une application de partage de trajet, via l'application google map comme taxi G7 ou Uber.

Mon application doit pouvoir grouper les demandes de trajet partant d'un point de départ A vers plusieurs points d'arrivées et ainsi établir un itinéraire pour chaque groupes de destinations. Ainsi, se retrouverons dans un même groupe, tous les trajets qui ont la même destination et/ou des destinations très proches.

Exemple:
supposons que 4 clients font une demande de course de Créteil vers paris comme suit:

client destination
client 1 15 ème arrondissement.
client 2 19 ème arrondissement
client 3 20 ème arrondissement
client 4 12 ème arrondissement

Dans cette exemple mon application doit pouvoir grouper les demandes des clients 2,3 et 4 car les arrondissements 19, 20 et 20 sont très proche.
ensuite mettre la demande du client 1 dans un autre groupe car celle-ci est très distante des autres.

Je cherches un algorithme pouvant satisfaire à ce problème.

Merci par avance de votre aide.

[anapurna]

salut

cela ressemble a un cas typique de programmation par satisfaction de contraintes

[itachis]

Merci de ta reponse arnapurna, cependant as-tu un exemple concret? sinon c'est pas grave!

[phryte]

Bonjour,

J'utiliserais la méthode du voyageur de commerce.

[dourouc05]

J'utiliserais la méthode du voyageur de commerce.

C'est plutôt du type VRP (une variante du TSP, c'est vrai) : organiser une tournée de véhicules pour prendre des personnes ou des choses ; de ce que je comprends, la différence, c'est que tu peux déterminer le nombre de véhicules qui doivent prendre la route. Le VRP a déjà été pas mal étudié, mais reste difficile à résoudre, je ne sais pas exactement pour ta version.
https://en.wikipedia.org/wiki/Vehicle_routing_problem

[phryte]

Bonjour,
Je ferais comme dans cette discussion :

http://www.developpez.net/forums/d15...s-d-ouverture/

[dourouc05]

La difficulté est autre, ici, il me semble : il s'agit de grouper des demandes par proximité (selon des chemins à choisir) plutôt que de "simplement" les ordonner (sur un seul chemin).

[gpcbitnik38]

moi j'aurais fait ça différemment mais c'est peut etre impossible dans le contexte.

je dispose d'une carte de la France (par exemple) au format image.
a chaque ajout de trajet je donne une valeur particulière au pixel de départ et d'arrivé (la clef permetant de retrouvé le trajet en BDD par exemple, je stocke egalement en BDD les coordonnée pixélique histoire de pas reparcourir mon image)
j'ai donc une map a jour avec divers pixel allumé.

lorsque je souhaite groupé des trajets , je selectionne le trajet "initiale" et je fais une recherche autour du pixel (avec la résolution de la carte on fait une conversion km/pixel et on détermine le rayon de recherche) (on va donc parcourir qque centaine de pixel, peut-etre des milliers mais c'est très rapide au final), pour chaque pixel qui contient la valeur d'une clef je pourrais groupé le trajet.

après le principale soucis c'est la map qu'il faut actualiser et surtout avoir assez de mémoire pour ne pas la chargé tout le temps.
après tu peux imaginer travailler a différente résolution et avec des maps morcelées.

[dourouc05]

@gpcbitnik38 : tu sembles plutôt résoudre un TSP "de base". Ensuite, tu ne seras jamais sûr d'avoir une si bonne solution à ton problème, tu feras peut-être des centaines, des milliers de kilomètres de trop. Mieux vaut regarder du côté de Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html) ou Mathematica (la fonction FindShortestTour, https://www.wolfram.com/mathematica/...-salesman.html). OR-Tools (de Google) peut aussi servir (https://developers.google.com/optimization/routing/tsp).