Skip to content

Algunos datos de vrptools

etorrano edited this page Oct 7, 2015 · 27 revisions

Documentacion de vrptools

Comentarios generales

osrmclient.h, osrmclient.cpp (clase OsrmClient)

Se define enlace estático con la biblioteca OSRM, su inicialización y métodos/funciones de consulta y retorno de información -originalmente viaroute- y luego locate y nearest.

node.h, node.cpp (clase Node)

Se definen elementos principales de los nodos nid (interno), id, x, y, hint, valid. Se definen funciones básicas distancia a segmentos, distancias entre nodos, si un nodo esta a la derecha de un segmento.

twnode.h, twnode.cpp (clase Twnode)

Hereda de Node. Define los tipos de nodos: kStart, kPickup, kEnd y varios otros. Métodos para establecer y saber que tipo de nodo es. Demanda, apertura, cierre y calle en la que esta el nodo.

tweval.h, tweval.cpp (clase Tweval)

Hereda de Twnode. Se agregan elementos y datos relacionados con el path del vehiculo, nodos anteriores, tiempos, etc. Aparece evaluateOsrm que es el primero en referencias a OSRM.

tripVehicle.cpp

Trip::getNodesInOrder()

Ésta función le da un orden a los nodos en cada path a evaluar. Para ésto llama a las siguientes funciones:

getNodesOnPath(path, dumpSite, nodes, nodesInOrder)
Trip::bestInsertion(UINT n_ins, POS &ins_pos, double &i_delta)

Primero llama a geNodesOnPath para encontrar los nodos que se encuentran a menos de una tolerancia(en nuestro caso también los que están a la derecha). Luego obtiene los que quedaron excluidos haciendo nodesOutPath = nodes - nodesOnPath y llama a bestInsertion para insertar los que quedaron fuera.

twc.h (clase TWC -Time Windows Compatibility-)

No hereda. Las ideas vienen de paper.

Las llamadas a getOsrmViaroute (osrmclient) están todas aquí, por lo cual cambiando el código de este archivo cambiaría el funcionamiento de todo el programa. En particular esa función aparece cuatros veces en esa clase.

Aparecen tablas de tiempos y consultas

void fill_times(const TwBucket<knode> nodesOnPath) const {
bool setTravelingTimesInsertingOneNode(
   const TwBucket<knode> &truck,
   const knode &dumpSite,
   const knode &node) const {

Usan osrmi->getOsrmTimes(times) y por lo tanto agregar nodos fantasmas no es un problema.

void getNodesOnPath(
   const TwBucket<knode> &truck,
   const knode &dumpSite,
   const TwBucket<knode> &unassigned,
   TwBucket<knode> &orderedStreetNodes) const { 
bool setTravelingTimesOfRoute(
   const TwBucket<knode> &truck,
   const knode &dumpSite) const {

Si se afectan y requieren mas trabajo.

trashnode

#define Trashnode Tweval

Eso es todo.

prob_trash.h, prob_trash.cpp (clase Prob_Trash)

Carga los datos de entrada (excepto la matriz de tiempo) desde archivos de tiempo.

Luego pueden ser usados en la solución.

trashprob.h, trashprob.cpp (clase TrashProb)

Carga los datos de entrada desde estructura de datos, inclusive la matriz de tiempo.

solution.h, solution.cpp (clase Solution)

Hereda de Prob_Trash.

Encuentra la solución del problema.

Borrador de Pseudocódigo según debug de ejecutable trash

  • Pide una única instancia de OSRM
  • Si no hay ninguna la crea con servicio "viaroute"
  • invariant() -basicOerations.cpp- realiza cálculos para comprobar que los tamaños de la subdivisión de nodos al combinarlos se siguen manteniendo:
 		 void Basicoperations::invariant() { 
 		 #if 0 
 		     if ((unassigned.size() + assigned.size()) != 109) { 
 		     DLOG(INFO) << "assigned:" << assigned.size(); 
		     assigned.dumpid(); 
		     DLOG(INFO) << "unassigned" << unassigned.size(); 
		     unassigned.dumpid(); 
		     assert ((unassigned.size() + assigned.size()) == 109); 
		     } 
		 #endif 
 		     assert(pickups.size() == (unassigned.size() + problematic.size() + assigned.size())); 
 		     assert(pickups == (unassigned + problematic + assigned)); 
 		     assert(!(unassigned * problematic).size()); 
 		     assert(!(unassigned * assigned).size()); 
 		     assert(!(problematic * assigned).size()); 
 		 } 
  • Comienza a asignar viajes hasta que estén todos asignados
  • Pide un camión para comenzar
  • En fleetOpt.cpp hace la optimización de la secuencia Llama a Fleetopt::optimize() y ese a Fleetopt::extract_trips() En esta funcion llama varias veces a intraTripOptimizationNoOsrm(); quien llama a Trip::getNodesOnPath y este llama a twc->getNodesOnPath(path, dumpSite, nodes, nodesInOrder);

Intento de cambio según recomendado por Stephen

Para mí en la línea 970 del archivo twc.h es donde hay que ver si está por la derecha. Ahí es donde entiendo maneja la geometría del segmento con los iteradores geometry.begin() y geometry.end(). Intenté utilizar la función para ver si el nodo está a la derecha pero no sé de donde sacar bien el nodo comienzo y nodo fin de la geometría del segmento. Entiendo que en esta parte es donde se calcula si cada nodo pertenece(está cerca) del segmento.

   // tolerance to determine if a container is "on" the segment 
   // Node::positionAlongSegment() is doing Euclidean calcuations 
   // so this needs to be set in degrees or meters depending on the 
   // underlying projection that the node x,y values are in. 

   // Approximate meters in degrees longitude at equator 
   // 0.00009 degrees === 10 meters 
   // 0.00027 degrees === 30 meters 
   const double tol = 0.00014; 

   std::deque< Node >::iterator git = geometry.begin(); 
   git++;    // we need pairs segment( (git-1), git ) 
   while ( git != geometry.end() ) { 

     // container to hold nodes for this segment 
     std::deque< std::pair< double, unsigned int > > seg; 

     // loop through the nodes and see which are on this segment 
     for ( unsigned int i=0; i<streetNodes.size(); i++ ) { 
       double pos = streetNodes[i].positionAlongSegment( *(git-1), *git, tol ); 
       double distToDump = streetNodes[i].distanceToSquared( dumpSite ); 
       if ( pos > 0 ) { 
         // found one on the segment so save it so we can order them 
         std::pair< double, unsigned int > p( pos, i ); 
         //  Node::isRightToSegment(const Node &lineBegin, const Node &lineEnd) 
         const Node lineBegin = *geometry.begin(); 
         const Node lineEnd = *geometry.end(); 
         /*#ifdef OSRMCLIENT 
           std::ostringstream strs; 
           strs << "Segmento: " << i << "Inicio: " << &lineBegin.x() << " Fin: " << lineEnd.y(); 
           DLOG(INFO) << strs.str(); 
         #endif*/ 
         if(streetNodes[i].isRightToSegment(lineBegin, lineEnd)) 
         { 

             #ifdef OSRMCLIENT 
               std::ostringstream strs; 
               strs << "Nod