These

2009_Crevier_Benoit

Informations

• Publié par: Bavem
• Nombre de lectures: 67
• Langue: Français

Extrait

´ ´UNIVERSITE DE MONTREAL
´ ´INTEGRATION DE LA PLANIFICATION DES OPERATIONS ET DE LA GESTION
DU REVENU POUR LE TRANSPORT FERROVIAIRE DE MARCHANDISES
BENOIT CREVIER
´ ´ ´DEPARTEMENT DE MATHEMATIQUES ET DE GENIE INDUSTRIEL
´ ´ECOLE POLYTECHNIQUE DE MONTREAL
` ´ ´THESE PRESENTEE EN VUE DE L’OBTENTION
ˆDU DIPLOME DE PHILOSOPHIAE DOCTOR (Ph.D.)
´ ´(MATHEMATIQUES DE L’INGENIEUR)
´DECEMBRE 2009
cBenoit Crevier, 2009.´ ´UNIVERSITE DE MONTREAL
´ ´ECOLE POLYTECHNIQUE DE MONTREAL
Cette th`ese intitul´ee :
´ ´INTEGRATION DE LA PLANIFICATION DES OPERATIONS ET DE LA GESTION
DU REVENU POUR LE TRANSPORT FERROVIAIRE DE MARCHANDISES
pr´esent´ee par : CREVIER Benoit
en vue de l’obtention du diploˆme de : Philosophiæ Doctor
a ´et´e duˆment accept´ee par le jury d’examen constitu´e de :
M. GENDREAU Michel, Ph.D., pr´esident
M. SAVARD Gilles, Ph.D., membre et directeur de recherche
, Ph.D., membre et codirecteur de rechercheM. CORDEAU Jean-Franc¸ois
M. MARCOTTE Patrice, Ph.D., membre
M. DE ALMEIDA David, Docteur, membre externeiii
REMERCIEMENTS
Je tiens tout d’abord a` remercier M. Gilles Savard, directeur, et M. Jean-Franc¸ois
Cordeau, codirecteur, pour m’avoir propos´e le sujet de la pr´esente th`ese et m’avoir ac-
compagn´e dans mon travail durant toutes ces ann´ees. Votre patience, votre disponibilit´e
demˆemequevotreconstantsupportm’ontpermisdemenera`bienceprojet.Larigueuret
la clart´e de vos id´ees dans vos domaines d’expertises respectifs ont enrichi mes r´eflexions
et, de ce fait, le contenu de cette th`ese.
Je remercie M. Michel Gendreau, M.Patrice Marcotte ainsique M.David De Almeida
pour avoir particip´e au jury d’examen.
Je tiens `a exprimer ma reconnaissance a` M. Gilbert Laporte. Votre ´ecoute fut d’une
tr`es grande importance.
Je voudrais aussi remercier le personnel du Centre interuniversitaire de recherche sur
les r´eseaux d’entreprise, la logistique et le transport. Leur soutient fut une pr´ecieuse
ressource. Je remercie plus particuli`erement M. Serge Bisaillon, M. Franc¸ois Guertin, M.
Daniel Charbonneau et M. Luc Rocheleau.
Enfin j’aimerais exprimer ma sinc`ere gratitude envers ma famille et mes amis qui
`furent, tout au long de ce projet, source de motivation et d’encouragements. A ma m`ere
`et ma sœur Line, merci pour votre soutien ind´efectible. A Jean-Franc¸ois B´erub´e, Nadia
`Lahrichi, Julie Paquette, Marie-Eve Rancourt, Walter Rei et Endong Zhu, merci pour
votre amiti´e et d’avoir partag´e les al´eas de la recherche.iv
´ ´RESUME
Dans cette th`ese, nous nous int´eressons a` l’analyse de l’int´egration de processus d´eci-
sionnels issus de la gestion des revenus aux politiques de gestion des op´erations d’un
transporteur ferroviaire de marchandises. Les entreprises de services de ce secteur sont
tributaires de nombreuses op´erations logistiques complexes dont :
– l’´elaboration des politiques de blocage et de routage des wagons,
– la planification du routage, de l’habillage et des horaires des trains,
– la gestion des op´erations des cours de triage,
– l’affectation des locomotives,
– le repositionnement des wagons vides,
– la planification des horaires des ´equipages.
Les ´etudes traitant de transport ferroviaire de marchandises, bien que nombreuses, ne
consid`erent typiquement qu’un sous-ensemble des activit´es mentionn´ees. En effet, la taille
et la complexit´e des probl`emes r´esultant de la combinaison des op´erations identifi´ees
repr´esentent des obstacles au d´eveloppement d’approches m´ethodologiques int´egr´ees. De
plus,peudechercheurssesontpench´essurlamiseen placed’outilsdegestion desrevenus
dans le secteur du transport de marchandises par rail et ce malgr´e l’impact majeur de
ceux-ci en transport a´erien notamment.
Dansunpremiertemps,nousillustronsdoncl’´etatdelarecherchedanslesdeuxsph`eres
d’´etude pr´esent´ees afin d’´etablir de fac¸on claire la probl´ematique qui sera trait´ee. Pour
ce faire, nous recensons les principales contributions scientifiques et nous introduisons
les concepts qui seront fondamentaux au positionnement de cette th`ese par rapport aux
r´ecentes publications propos´ees dans la litt´erature.
Une fois l’axe de recherche identifi´e, nous pr´esentons quelques formulations d´ecrivant
l’int´egration propos´ee selon que le niveau de planification privil´egi´e soit op´erationnel ouv
tactique. Celles-ci permettent de mettre en lumi`ere la gestion combin´ee de d´ecisions li´ees
a` l’´elaboration du plan d’op´eration et celles d´ecoulant des politiques tarifaires dict´ees
par l’entreprise. Par le biais de la programmation math´ematique a` deux niveaux, nous
´etudions le comportement des usagers en r´eaction `a diff´erentes strat´egies tarifaires, tout
en consid´erant la capacit´e du r´eseau qui r´esulte des politiques op´erationnelles du trans-
porteur.
Nous proposons par la suite une analyse des principales caract´eristiques et propri´et´es
de la mod´elisation combinant la tarification et la gestion de la capacit´e au niveau op´era-
tionnel. Pour ce faire, deux politiques tarifaires sont trait´ees. Nous pr´esentons en outre
une famille d’in´egalit´es valides qui renforcent de fac¸on significative la formulation. Les
propri´et´es et in´egalit´es identifi´ees sont subs´equemment exploit´ees lors de la r´esolution de
la mod´elisation avec le logiciel d’optimisation Cplex. La validation de la m´ethodologie
d´evelopp´ee s’effectue sur une classe d’instances g´en´er´ees de mani`ere a` d´epeindre avec
r´ealisme le contexte ´etudi´e.
Finalement, nous abordons le d´eveloppement d’approches heuristiques pour le pro-
bl`eme pos´e en proposant deux familles d’algorithmes. La premi`ere tire parti de la relation
entrelesdeuxpolitiquestarifaires´evoqu´ees etsebasesurlarelaxation decontraintes liant
les tarifs entre eux. Celles-ci sont par la suite r´eintroduites graduellement. La proc´edure
vise par ce principe l’identification de la structure d’une solution optimale au probl`eme
initial. Enfin, nous pr´esentons une heuristique de type primal-dual ou` sont r´esolus, en al-
ternance, des sous-probl`emes ne consid´erant, respectivement, que les contraintes primales
ou duales du probl`eme de second niveau. Les heuristiques sont compar´ees entre elles de
mˆeme qu’avec les r´esultats obtenus par l’approche exacte.vi
ABSTRACT
This thesis studiesthe integration of decision processes based on revenue management
with operations planning policies of a rail freight carrier. Services companies in this field
must face complex logistic operations such as :
– block planning and car routing,
– train routing, makeup and scheduling,
– yard management,
– locomotive assignment,
– empty car repositioning,
– crew scheduling.
Even if freight rail transportation problems have been thoroughly analyzed in the past,
they typically consider only a subset of the operations mentioned. The size and the com-
plexityofcombiningtheidentifiedproblemshave preventedthedevelopment ofintegrated
methodological approaches. Moreover, few researchers have tackled the challenge of pro-
posing revenue management tools for freight rail applications despite their major impact
in air transportation for instance.
First of all, we describe the current state of research for the two fields presented in
order to clearly establish the problem that will be addressed. We therefore review the
main scientific contributions and introduce the fundamental concepts that will enable us
to position ourselves in relation to recent publications.
Once the research perspectives are identified, we present some formulations describing
the proposed integration according to the chosen planning level, which could be either
operational or tactical. These help to highlight the combined management decisions rela-
ted tothedevelopment oftheoperatingplanandthosearisingfromtariffpoliciesdictated
by the company. Through bilevel programming we study user behavior in response to dif-vii
ferent pricing strategies while considering network capacity resultingfromthe operational
policies of the carrier.
We then suggest an analysis of the main characteristics and properties of the model
combining pricing and capacity management at the operational level. To do this, two pri-
cing policies are discussed. We also present valid inequalities that strengthen significantly
the formulation. The identified properties and inequalities are subsequently exploited for
solving the model with the Cplex optimization software. The validation of the developed
methodology is carried on a class of instances generated in order to realistically portray
the context studied.
Finally, we discuss the development of heuristic approaches for the problem by propo-