Algorithme de branche et de prix

Question

La branche et le prix peuvent-ils être une bonne solution pour un problème de routage avec une fonction objectif min-max? Par exemple, minimiser la longueur maximale de tout itinéraire de véhicule dans un VRP.

Dans la littérature, je n'ai jamais vu que cette approche de solution permettait de résoudre un tel problème. Autant que je sache, cette approche est utilisée pour résoudre les VRP en minimisant le coût total.

Answer 1

Être une bonne ou une mauvaise approche dépendra de plusieurs facteurs, par exemple:

• la taille des instances
• le temps disponible pour trouver une solution (cela a tendance à être une question importante dans les applications de routage de véhicules)
• Puissance de calcul
• quel niveau de qualité de la solution est qualifié d'assez bon

Voir ce travail de Yu, Nagarajan et Shen sur le VRP makespan minimum avec des contraintes de compatibilité, car c'est un problème similaire qui a été étudié avant d'utiliser la branche et le prix comme approche pour résoudre une variante de makespan VRP. Cela a très bien fonctionné. Notez que dans leur cas, ils ont conçu un algorithme d'approximation pour accélérer le temps d'exécution de B&P.

Je propose l'expérience suivante:

Première étape: Suite à la réponse de @ RobPratt à votre question précédente concernant la minimisation du makespan dans VRP :

Laisser $d_i$ être la demande du client $i\in N$, laisser $V=\{1,\dots,K\}$ être l'ensemble des véhicules, et laissez $P$ être l'ensemble des colonnes, où chaque colonne correspond à un sous-parcours réalisable à partir du dépôt, avec des variables d'arc $x_{i,j}$ et variables de nœud $y_i$. Laisser$z$être le makespan. Le problème principal sur$z$ et $\lambda$est comme suit, avec deux variables entre parenthèses: \ begin {align} & \ text {minimiser} & z \\ & \ text {sujet à} & z - \ sum_ {p \ in P} \ left (\ sum_ {i, j } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {pour$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {pour $i\in N$} &&(\texte{$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {pour $v\in V$} &&(\texte{$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {pour $v\in V$ et $p\in P$} \ end {align}

Le sous-problème de génération de colonne sur $x$ et $y$ pour chaque $v\in V$ est alors de minimiser le coût réduit de $\lambda^p_v$. Autrement dit, minimiser$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ sujet à $(x,y)$ formant un sous-parcours réalisable à partir du dépôt, avec $\sum_i d_i y_i \le L$, où $L$ est la capacité de chaque véhicule.

Comme indiqué ici, le sous-problème peut être reformulé en tant que chemin le plus court élémentaire: divisez le dépôt en une source et un puits, et déplacez les poids des nœuds vers les arcs: $\pi_v c_{i,j}−\alpha_i$ pour le poids de l'arc $(i,j)$ dans le sous-problème élémentaire du chemin le plus court.

Deuxièmement: implémentez la méthode ci-dessus. Je recommande d'essayer d'utiliser VRPy, comme suggéré par Kuifje ici . De cette façon, vous n'aurez pas à implémenter toutes les opérations de succursale et de prix à partir de zéro. Etapes détaillées:

1. Jetez un œil à la documentation du projet.
2. Jetez un œil au code dans GitHub.
3. Créez un fork ou téléchargez le projet au format .zip, de sorte que vous puissiez apporter des modifications localement.
4. Modifiez le code concernant le sous-problème , de sorte que le dépôt soit divisé comme expliqué ci-dessus.
5. Exécutez les expériences, vous pouvez suivre les exemples d'instances de la documentation comme ici et ici .
6. Faites-nous savoir comment cela a fonctionné. Et n'oubliez pas de remercier VRPy et ses développeurs dans votre travail (qu'il s'agisse d'un rapport de projet, de thèse, de publication, etc.), ainsi que de respecter les termes de la licence de la bibliothèque en ce qui concerne les modifications.

Answer 2

VRPy ( v0.3.0 ) prend désormais en charge cette option: il ne vous reste plus qu'à définir l' minimize_global_spanoption sur Truelors de l'instanciation de l' VehicleRoutingProblemobjet:

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

Bien sûr, votre graphique $G$ doit être bien défini en premier lieu.

La formulation proposée par @RobPratt est implémentée. Si vous jouez avec certains problèmes de jouets, vous verrez que la formulation est faible par rapport à la formulation classique (sans le makespan). Il est facile de voir que la contrainte$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ dans V$} $$ en est responsable.

Vous pouvez également essayer l'approche alternative suivante:

1. Résolvez le problème sans l'option min_max

2. Interroger la plus grande étendue

3. Résolvez à nouveau sans min_max, mais limitez le problème de telle sorte que chaque route ait une portée plus petite que la plus grande interrogée en 2.

4. Si impossible, arrêtez, sinon, passez à l'étape 2.

Tout cela est simple avec l'écosystème VRPy. S'amuser.