Comment ne pas endormir son auditoire en 30 secondes

Olivier Delangre

Description

Problème de tarification routière:génération de colonnesAurélie CasierPromoteur : Martine LabbéGOM – Département d’Informatique – Faculté des SciencesUniversité Libre de Bruxelles (ULB)12 ParcoursLicenciée en Sciences Mathématiques (ULB) « Problème d'impression avec coûts fixes » (M.Labbé)  reformulation, nouvelles IV,…DEA en Sciences (ULB) collaboration: M. Campêlo  bourse de recherche (UFC, Brésil) « Problème de coloration des sommets d'un graphe: étude d'une formulation utilisant des représentants de classes » (M.Labbé) Nouvelles IV (PORTA, lifting)Depuis 6 mois: thèse, tarification de produits (autoroutière)23 Tarification de produitsExemple: tarification autoroutière (NPP)arcs « tarifables » commodités K = {commodités}NPP : déterminer les taxes qui maximisent le revenu de la compagnie, sachant que les clients réagissent à ces taxes en choisissant le plus court chemin de o à d. (distances = coûts) Prix assez hauts pour générer du bénéfice3 assez bas pour attirer des clients4 Tarification de produitsExemple: tarification autoroutière (NPP)1 cout fixe par arc Exemple: (1 commodité allant de 1  5)1 taxe par arc tarifable+t23 +t4522= coût max de la commodité 1-3-56 = coût min de la commodité 1-2-3-4-5 avec taxes nulles⇒ 22-6=16=bs au revenu de la compagniebs pas toujours atteinte:t ≤5 car  2t 2≤923 23 ¿ ¿t =5, t =1023 45t ≤10 car 2 0t ≤1245 4545 Tarification de produitsExemple: tarification autoroutière ...

Informations

• Publié par: Nelaf
• Nombre de lectures: 122
• Langue: Romanian

Extrait

Problème de tarification routière: génération de colonnes

Aurélie Casier

Promoteur : Martine Labbé

GOM – Département d’Informatique – Faculté des

Sciences

Université Libre de Bruxelles (ULB)

1

aPrcours

Licenciée en Sciences Mathématiques (ULB)

 «  Problème d'impression avec coûts fixes   (M.Labbé)

 reformulation, nouvelles IV,…

DEA en Sciences (ULB)

 collaboration: M. Campêlo  bourse de recherche (UFC, Brésil)

 «  Problème de coloration des sommets d'un graphe: étude d'une formulation utilisant des représentants de classes    (M.Labbé)

 Nouvelles IV (PORTA, lifting)

Depuis 6 mois: thèse, tarification de produits (autoroutière)

2

K = {co

modités}

 

3

 Prix assez hauts pour générer du bénéfice  assez bas pour attirer des clients

NPP : déterminer les taxes qui maximisent le revenu de la compagnie, sachant que les clients réagissent à ces taxes en choisissant le plus court chemin de o à d. (distances = coûts)

turonoa rè euoit: tamplecatirifi orp ed n exE stiudarTioaticif éslbaf semmoctido PP(N rc ) a« s rita

Tarification de produits Exemple: tarification autoroutière (NPP)   1 1 E     t c x o e u m t fi p x l e   : p ( a 1 r   a c r o c mmodité allant de 1  5) axe par arc tarifable +t 23 +t 45 22 = coût max de la commodité  1-3-5  6 = coût min de la commodité  1-2-3-4-5 avec taxes nulles  ⇒ 22-6 = 16 = bs au revenu de la compagnie bs pas toujours atteinte: t t 23 ≤ ≤ 1 5 0  c   a c r a   r  2  t 23  2 ≤ 9 t  2 = 5, t  45 = 10 45 2  0  t 45 ≤ 12 3 4

Tarification de produits Exemple: tarification autoroutière (NPP)   Ens. des entrées et sorties o k  Graphe complet o k arcs en // d k d k Hyp:  1) Les arcs tarifables sont tous connectés et forment un  chemin ( autoroute ) = 2) en pratique taxes déterminées par rapport à une      entrée et une sortie donnée (taxes pas additives)       1 taxe par ss-chemin de l’autoroute 5

Tarification de produits Exemple: tarification autoroutière (NPP)

Notations:

o k

d k

6

a noitacituorotulempxe s Efirita:   nedtaoiudtip orificTar ère (NPP)

7

remplacé par • contraintes primales-duales • conditions d’optimalité

2 d niveau (commodités)

1 er niveau (compagnie)

formulation biniveau (Dewez, 2004)



Tarification de produits Exemple: tarification autoroutière (NPP)

 formulation mixte entière

linéarisation

8

Tarification de produits Cas général (PPP)

Références (résolution exacte):  Contribution mathématique pauvre pour PPP:



R. Shioda, L. Tunçel, and T.G.J. Myklebust, "Maximum utility product pricing models and algorithms based on reservation prices.", Optimization Online, 2007.

  même formulation mais contrainte du plus court chemin remplacée par contrainte de l’utilité maximale

Contribution riche pour NPP:

 M. Labbé, P. Marcotte, and G. Savard (1998)  Didi, Bouhtou, Brotcorne, Cirinei, Dewez, Heilporn, …

9

(A. Casier, B. Fortz, M. Labbé)

Dantzig- Wolfe

10

SP décomposable par arc

érénGennoloc ed noita rmul NL Fo r HPs su NP)L nH(taoi

néGénod aritolnn eocur Hes s robl PNL P

11

MP)re (Maitème