Network pricing problems : complexity, polyhedral study and solution approaches
Notice bibliographique
Résumé
Consider the problem of maximizing the revenue generated by tolls set on a subset <p>of arcs of a transportation network, where origin-destination flows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs. <p>This thesis is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path, as occurs on highways. Further, as toll levels are usually computed using the highway entry and exit points, a complete toll subgraph is considered, where each toll arc corresponds to a toll subpath. Two <p>variants of the problem are studied, with or without specific constraints linking together the tolls on the arcs. <p>The problem is modelled as a linear mixed integer program, and proved to be NP-hard. Next, several classes of valid inequalities are proposed, which strengthen important constraints of the initial model. Their efficiency is first shown theoretically, as these are facet defining for the restricted one and two commodity problems. <p>Also, we prove that some of the valid inequalities proposed, together with several <p>constraints of the linear program, provide a complete description of the convex hull <p>of feasible solutions for a single commodity problem. Numerical tests have also been conducted, and highlight the real efficiency of the valid inequalities for the multi-commodity case. Finally, we point out the links between the problem studied in the thesis and a more classical design and pricing problem in economics. /<p><p><p>Considérons le problème qui consiste à maximiser les profits issus de la tarification d’un sous-ensemble d’arcs d’un réseau de transport, où les flots origine-destination (produits) sont affectés aux plus courts chemins par rapport aux tarifs et aux coûts initiaux. Cette thèse porte sur une structure de réseau particulière du problème ci-dessus, dans laquelle tous les arcs tarifables sont connectés et forment un chemin, <p>comme c’est le cas sur une autoroute. Étant donné que les tarifs sont habituellement déterminés selon les points d’entrée et de sortie sur l’autoroute, nous considérons un sous-graphe tarifable complet, où chaque arc correspond en réalité à un sous-chemin. Deux variantes de ce problème sont étudiées, avec ou sans contraintes <p>spécifiques reliant les niveaux de tarifs sur les arcs. <p>Ce problème peut être modélisé comme un programme linéaire mixte entier. Nous prouvons qu’il est <p>NP-difficile. Plusieurs familles d’inégalités valides sont ensuite proposées, celles-ci renforçant certaines contraintes du modèle initial. Leur efficacité est d’abord démontrée de manière théorique, puisqu’il s’agit de facettes <p>des problèmes restreints à un ou deux produits. Certaines des inégalités valides proposées, ainsi que plusieurs contraintes du modèle initial, permettent aussi de donner une description complète de l’enveloppe convexe des solutions réalisables d’un problème restreint à un seul produit. Des tests numériques ont également <p>été menés, et mettent en évidence l’efficacité réelle des inégalités valides pour le problème général à plusieurs produits. Enfin, nous soulignons les liens entre le problème de tarification de réseau étudié dans cette thèse et un problème plus classique de tarification de produits en gestion. <p>
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,000 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,000 |
| Études des sciences et des technologies | 0,001 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule tête enseignante, pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».