Skip to content

Algunos datos de vrptools

Jump to bottom
etorrano edited this page Oct 6, 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.

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 << "Nodo dentro del path, está a la derecha:" << i << "StreetID: " << unassigned[i].streetId() << " x: " << unassigned[i].x() << " y: " << unassigned[i].y();`
          `DLOG(INFO) << strs.str();`
        `#endif`
        `seg.push_back( p );`
    `}`
    `else`
    `{`
      `#ifdef OSRMCLIENT`
        `std::ostringstream strs;`
        `strs << "Nodo fuera del path, está a la izquierda:" << i << "StreetID: " << unassigned[i].streetId() << " x: " << unassigned[i].x() << " y: " << unassigned[i].y();`
        `DLOG(INFO) << strs.str();`
      `#endif`
    `}`

  `}`
`}`
Clone this wiki locally