:. Initialiser and . Gô, gain), --+s=0(compteur, p.0

. Choisir-un-noeud,

, Supprimerl'arc (i, i +1) si z < net(i, 0) si i : n

C. K. Tel, que gà: c1.,i+1, -c1z+r,r*) : cç,i,t+r) -MinpT;, c(i + l,k). sig;>o --introduire I'arc (i + l

, Si tous les noeuds ont été explorés --+ la procédure s'arrête: la dernière tournée est optimale

, Supprimer I'arc (k. -1, k*) si k* > 0 ou (n, 0) si, p.0

, Introduire l'arc (i,k -L)

C. Gi and . Gi,

, Inverser le sens de la succession d'arcs appartenant à la tournée initiale et qui joignent k* -! àz+1

, Recommencer la procédure de 3 à 8 en initialisant'i à k* -1

, 10 Renuméroter les sommets dans I'ordre de la nouvelle tournée obtenue. 11

, Dtsciipaion de I'algorithme2

, Remarque: le nom des variables sont entre les parenthèses. l. Le nombre de sites

, Le nombre de places de parking dans chaque site

, Le nombre de plots dans chaque site En fait, une place de parking peut être équipée d'un chargeur ou pas, Le nombre de plots dans un site est inférieur ou égal au nombre de places de parking

, Le nombre de voitures électriques qui constituent la flotte

, La répartition initiale des voitures dans les différents sites, autrement dit, le nombre de voitures présentes dans chaque site au début de la simulation

, Le nombre de périodes éiémentaires constituant un cycle. Prenons I'exemple d'une journée, celle-ci peut être segmentée en un nombre fini de périodes élémentaires

, La demande maximale possible dans chaque site à destination des autres sites du système pour chacune des périodes élémentaircs

, Les probabilités de demandes entre tout couple de sites pour chaque période élémentaire . Remarque : les deux sites peuvent être identiques, Ln SrrvtuLATEUR, vol.8

, Les durées minimales des déplacements, en nombre de périodes élémentaires, entre tout couple de sites en connaissant la période élémentaire du départ

I. L. , é,cart, en nombre de périodes élémentaires, entre les durées minimales et les durées maximales des déplacements entre tout couple de sites

, Le moment où la simulation comm ence

. La-durée-de-la-simulation, autrement dit la période sur laquelle on teste 1es différentes politiques. Cette durée peut représenter plusieurs heures, plusieurs journées, ou même plusieurs mois

, Le nombre de simulations

. Le, en nombre de périodes élémentaires, qu'un client tolère avant de quitter le système insatisfait. Lorsqu'un client se présente dans un site, il souhaite trouver une voifure disponible, mais il peut attendre un certain temps avant de s'en aller mécontent

, Le nombre de voitures de service (camions) chargées du rééquilibrage

, Lacapacité de chacun des camions

, Le temps moyen, en nombre de périodes élémentaires, nécessaire aux camions pour parcourir la distance qui sépare les sites

, Le seuil de disponibilité dans chacun des sites, c'est à dire le niveau de charge au delà duquel une voiture est disponible (Sezdls)

, Les paramètres concernant une voiture électrique sont: a. Laquantité de charge reçue, par période élémentaire, lorsque la voiture se trouve sur un plot

L. Quantité-de-charge and . Qu, une voiture électrique en cours de déplacement consomme par période élémentaire

, sachant que I'on a le choix entre : a. Priorité au site Ie plus proche d'un camion. b. Service groupés. c, Lapolitique de redistribution choisie

, 3 Evènements A chaque période élémentaire, des évènements suivants sont considérés: 1 L arrivée d'une demande dans un site

, Le départ d'un client mécontent à cause d'une trop longue attente

, Le départ d'une voiture d'un site

, L'arnvée d'une voiture dans un site

, Une voiture atteint la charge maximale

, Une voiture tombe en panne lors d'une course

, L'arrivée d'un camion dans un site

, Uanvée du personnel chargé des déplacements locaux

, mises à jour Ces différents évènements produisent plusieurs mises à jour, à savoir

, L'emplacement des différentes voitures ainsi que leur état (en cours d'utilisation, disponible , en panne, ou en cours de chargement)

, Le nombre de voitures dans chaque site ainsi que leur emplacement (une voiture peut se trouver sur un emplacement muni d'un plot ou pas)

, Le nombre de systèmes de recharge en service

. La-file-d, attente des demandes dans le site Au bout d'un certain temps d'attente, si un client n'a pas de voiture disponible, il s'en va mécontent

, nous listons les plus importantes structures des données que nous utilisons dans le simulateur Afin de limiter la place mémoire utilisée, nous avons recours a des structures des données dynamiques, autrement dit, les variables sont crées et détruites pendant I'exécution du programme

, 5 détaille une partie de la figure précédente

S. Origine and F. , 5: Détail du second écran Références |4t97al 14th International Electric Vehicle Symposium and Exposition. Evaluation of an Electric Vehicle Demonstration Projeu, Florida |4t97bl 14th Intemational Electric Vehicle Symposium and Exposition. Were, When, How Fast and How Much? Questions about Consumer Demand for Home, Away From Home, Time of Day, and Speed of Recharging for Electric Vehicles, 1997.

C. Allal, Commande d'un réseau de transport urbain, 1998.

]. A. Ass88 and . Assad, Vehicle Routing : Methods and Studies,chapter Modeling and Implementation Issues in Vehicle Routing, p.745, 1988.

R. Kenneth and . Baker, Introduction to Sequencing and Scheduling, J. Wiley and sons, 1974.

L. Bodin and B. Golden, Classification in vehicle routing and scheduling, Networks, vol.6, issue.2, pp.97-108, 1981.
DOI : 10.1002/j.1538-7305.1965.tb04146.x

[. Bradley, A. Hax, and T. Magnanti, Applied Mathematical P ro gramming Menlo P ark, 797 I . tBN96l C. Bleijs and O. Normand. A fully automatic station using inductive charging techniques, 1996.

L. Bodin, Twenty Years of Routing and Scheduling, Operations Research, vol.38, issue.4, pp.57-58, 1990.
DOI : 10.1287/opre.38.4.571

O. Canzler, Rapport interne praxitèle, 1996.

[. Chauvet, N. Hafez, and J. Proth, Gestion d'un système de véhicules électriques en libre-service, ModéIisation et simulation des systèmes de production et de logistique, pp.325-332, 1997.

F. Chauvet, N. Hafez, J. Proth, and N. Sauer, Management of a pool of self-service cars, Journal of Intelligent Manufacturing, p.459466, 1997.

, IDDSe2] lDFResl IDLSS88] lea97l [Ele96] lFou96l lGLPe4l lGLPeTl

, IHDDe0l

G. Dantzig, Applications et prolongements de Ia programmation linéaire, 1966.

, Handbookof Genetic Algorithms

M. Desrochers, J. Desrosiers, and M. Solomon, A new optimisation algorithm for the vehicle routing problem with time windows. Operations Re s e arch, pp.342-367, 1992.

M. Dror, D. Fortin, and C. Roucairol, Redistribution of self-service electric cars: A case of pickup and delivery, 1998.
URL : https://hal.archives-ouvertes.fr/inria-00073142

M. Desrochers, J. Lenstra, M. W. Savelsbergh, and F. Soumis, Vehicle Routing: Methods and Studies, chapter Vehicle Routing with Time Windows: Optimization, and Approximation, pp.65-85, 1988.

E. Aarts, Local Search in Combinatorial Optimization, chapter Simulated Annealing, pp.9-120, 1997.

T. Electricité-dans-les and . Urbains, Conduite en train pour véhicules élec' triques en libre-service,PaÀs, avril 1996' Fourth IEEE Mediterranean Symposium on New Directions in Control and Automationg . Platooning techniquefor empty vehicles distribution in the PRAXI' TELE projecf, 1996.

M. Gendrau, G. Laporte, and J. Potvin, Local search algorithms for the vehicle routing problem, 1994.

M. Gendreau, G. Laporte, and J. Potvin, Local Search in Combinatorial Optimization, chapter Vehicle Routing: Modern Heuristics, pp.3-336, 1997.

N. Hafez, Analyse fonctionnelle de I'optimisation de la recharge -rapport interne praxitèle, 1997.

M. Haouari, P. Dejax, and M. Desrochers, Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de I'art. MIRO, Recherche O pérationnelle, pp.217-244, 1990.

A. [. Haimovich, L. Kan, and . Stougie, Vehicle Routing : Methods and Studies, Analysis of Heuristics for Vehicle Routing Problems, pp.47-61, 1988.

A. Hertz, E. Taillard, D. , and V. Erra, Local Search in Combinatorial Optimization, chapter Tabu Search, pp.12-136, 1997.

[. Congress, Praxitele : A New Public Transportwith Self Service Electric Cars, 1996.

[. Jodouin, Les réseaux de neurones: principes et définitions, Hermes, 1994.

G. Kindervater and M. Savelsbergh, Local Search in Combinatorial Optimization, chapter Vehicle Routing: Handling Edge Exchanges

, John Wiley and Sons, 1997.

E. L. Lawler, The Travelling Salesman Problem: a Guided Tour of Combinatorial Optimisation, Series In Discrete Mathematics And Optimisation . J. Wiley and sons, 1987.

P. Loomba, Linear Programming: an Introductory Analysis, 1964.

T. Mautor, Contribution à la résolution des problèmes d'implantation algorithmes séquentiels et parallèIes pour I'affectation quadratique, 1993.

[. Murty, Linear and Combinatorial Programming, J. Wiley and sons, 1976.

, Vehicle Routing in the Presence of SiteUehicle Dependency Constraints, 1986.

[. Potvin and F. Guertin, Meta-heuristics: theory and applications , chapter The Clustered Traveling Salesman Problem: A Genetic Approach, pp.619-631, 1996.

[. Proth and H. P. Hillion, Mathematical Tools in Production Management , Competitive Methods in Operations Research and Data Analysis, 1990.

C. Peterson and B. Soderberg, Local Search in Combinatorial Optimilation, Artificial Neural Networks, pp.173-214, 1997.

[. Psaraftis, Vehicle Routing: Methods and Studies, chapter Dynamic Vehicle Routing Problems, pp.223-249, 1988.

S. Ross, A course in simulation, 1991.

C. Roucairol, Du séquentiel au Parallèle : la recherche arborescente et son application à la programmation quadratique en variable 0.1, 1987.

C. Rego and C. Roucairol, Le problème de tournées de véhicules: étyde et résolution approchée, 1994.

M. Sakarovitch, Graphes et programmation linéaire Optimisation Combinatoire , Méthodes mathématiques et algorithmiques, graphes et programmation linéaire, des sciences et des arts, 1984.

M. Sakarovitch, Programmation discrète. Optimisation Combinatoire, Méthodes mathématiques et algorithmiques, graphes et programmation linéaire . Hermann, Editeurs des sciences et des arts, tThi78] Robert Thierauf. An Introductory Approach to Operations Research, 1978.

L. J. Van-der-bruggen, J. K. Kenstra, and P. C. Schuur, Variable-Depth Search for the Single-Vehicle Pickup and Delivery Problem with Time Windows, Transportation Science, vol.27, issue.3, pp.298-301, 1993.
DOI : 10.1287/trsc.27.3.298