[AMPL] algoritmo dijkstra

[JamesC++]

Salve a tutti,

sto lavorando con il linguaggio AMPL su un problema di programmazione lineare intera.

Ho N veicoli su un grafo e voglio semplicemente modificare l'algoritmo di dijkstra in maniera da trovare il cammino minimo per ciascuno senza che ci siano collisioni tra robot.

Ovviamente ogni robot conosce la posizione degli altri.

Avete idee?

Grazie

[ivandl]

Ciao,

come è definito l'evento collisione?
Significa che all'istante T1 non possono esserci due robot che percorrono uno stesso arco per andare da un nodo di partenza ad uno di destinazione?

[JamesC++]

esatto... fissato un orizzonte temporale T_max... l'evento collisione significa che ad ogni tempo discreto t non devono esserci 2 veicoli sullo stesso nodo e 2 veicoli non devono percorrere lo stesso arco.
Ipotizziamo che i veicoli possono essere N . Ogni veicolo conosce la posizione degli altri ad ogni istante temporale.

Più che ad una procedura iterativa, sarei interessato a trovare una funzione costo e una serie di vincoli che eseguiti da un solver di ottimizzazione lineare intera mi possa dare la soluzione (se il problema è fattibile)

grazie..