Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
4 replies Latest Post - ‏2013-01-22T10:49:05Z by SystemAdmin
SystemAdmin
SystemAdmin
623 Posts
ACCEPTED ANSWER

Pinned topic VRPTW with CP

‏2009-07-07T00:36:17Z |

[cmsoc said:]

Hi I'm Solving the VRPTW. I'm using ILOG CP Optimizer 2.0.1 and OPL 6.0.1.
I need some help

dvar interval Task[c in master_c] size 1;// task associated to the service required by customer c.
dvar interval vehiculos[set_CLI][set_VEH] optional;
dvar sequence Ruta[v in set_VEH]in all(c in set_CLI)vehiculos[c][v];
dvar boolean var_Y[c in set_CLI][k in set_KLI];//  1 if node c is before node k, 0 otherwise
par_TVIA[c,k] parameter for travel time between c and k
par_DIST[<c,k>] distance between customers c and k
INFI means infinity

forall(c in set_CLI) cons_ASIV[c]:
      alternative(Task[c], all(v in set_VEH) vehiculos[c][v]); 
   
forall(v in set_VEH) cons_OVERL[v]:
    noOverlap(Ruta [v]); 


This constraint calculate the the start time for each task if node c and node k are served with the same vehicle v (presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]))

forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DISE[c][k][v]:
  if(k not in set_PRE[c]&& k not in set_SUC[c] && k not in set_CNAS[c]&& c!=k)
{
startOf(Task[k])>=(endOf(Task[c])+ par_TVIA[c,k]-INFI*(1-var_Y[c][k]))*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);

startOf(Task[c])>=(endOf(Task[k])+ par_TVIA[k,c]-INFI*var_Y[c][k])*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
}

This Constraint calculate the traveled distance when a vehicle arrives to the location of each remaining customer.
forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DDRE[c][k][v]:
  if( k not in set_PRE[c]&& k not in set_SUC[c] && k not in set_CNAS[c]&& c!=k)
{
dist[k]>=(dist[c]+par_DIST[<c,k>]-INFI*(1-var_Y[c][k]))*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
dist[c]>=(dist[k]+par_DIST[<k,c>]-INFI*var_Y[c][k])*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);

}

using presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]) the model generate a huge number of constraints, for this reason the run time is large. Any suggestion for model this constraints?
Thanks
Carlos S
Updated on 2013-01-22T10:49:05Z at 2013-01-22T10:49:05Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    623 Posts
    ACCEPTED ANSWER

    Re: VRPTW with CP

    ‏2009-07-07T05:21:53Z  in response to SystemAdmin

    [shaw said:]

    Hello,

    Is it possible for you to post the whole model?  Helping you would be much easier.


    Paul
    • SystemAdmin
      SystemAdmin
      623 Posts
      ACCEPTED ANSWER

      Re: VRPTW with CP

      ‏2009-07-08T05:27:13Z  in response to SystemAdmin

      [cmsoc said:]

      using CP;

      // Conjuntos Maestros
      {string} master_v = ...; // Vehículo ///////indices////////////////////
      {string} master_c = ...; // Destino (c)
      {string} master_k = ...; // Destino (k)
      {string} master_z = ...; // Zonas
      int INFI=...;// 10000

      // c -> NOR() - Nodo Urbano Origen
      tuple Iset_NOR {  string c; } ;
      {Iset_NOR} IIset_NOR = ...;
      {string} set_NOR = { c | <c> in IIset_NOR } ;

      // v -> VEH() - Vehículos
      tuple Iset_VEH {  string v; } ;
      {Iset_VEH} IIset_VEH = ...;
      {string} set_VEH = { v | <v> in IIset_VEH } ;

      // c -> CLI() - Nodos Clientes
      tuple Iset_CLI {  string c; } ;
      {Iset_CLI} IIset_CLI = ...;
      {string} set_CLI = { c | <c> in IIset_CLI } ;

      // k -> KLI() - Clientes (k)
      tuple Iset_KLI {  string k; } ;
      {Iset_KLI} IIset_KLI = ...;
      {string} set_KLI = { k | <k> in IIset_KLI } ;

      // Parametros Leidos,Tabla,Tipo

      //  Parametro: CUVE(v) - Costo Uso Vehiculo Tabla: (VEHICULO-R)
      tuple Ipar_CUVE {  string v; }
      tuple Tpar_CUVE {  string v; float val_CUVE ;}
      {Ipar_CUVE} IIpar_CUVE = ...;
      {Tpar_CUVE} Dpar_CUVE = ...;
      float par_CUVE[IIpar_CUVE] = [<v>:val_CUVE | <v,val_CUVE> in Dpar_CUVE] ;

      //  Parametro: DIST(c,k) - Distancia Clientes Tabla: (CLI_CLI-R)
      tuple Ipar_DIST {  string c; string k; }
      tuple Tpar_DIST {  string c; string k; float val_DIST ;}
      {Ipar_DIST} IIpar_DIST = ...;
      {Tpar_DIST} Dpar_DIST = ...;
      float par_DIST[IIpar_DIST] = [<c,k>:val_DIST | <c,k,val_DIST> in Dpar_DIST] ;

      ///////PARAMETROS CP////////////////
      /
      //Parametro: TVIAJES(c,k) -Tiempo de Viaje entre Clientes
      /**tuple Ipar_TVIAJE {  string c; string k; }
      tuple Tpar_TVIAJE {  string c; string k; float val_TVIAJE ;}
      {Ipar_TVIAJE} IIpar_TVIAJE = ...;
      {Tpar_TVIAJE} Dpar_TVIAJE = ...;
      float par_TVIAJE[IIpar_TVIAJE] = [<c,k>:val_TVIAJE | <c,k,val_TVIAJE> in Dpar_TVIAJE] ;*/

      // Parametros Calculados

      //  Parametro: VELO() - Velocidad Promedio
      float par_VELO =  1 * 28.6 ;

      //  Parametro: TVIA(c,k) - Tiempo de Viaje
      float par_TVIA[c in master_c][k in master_k] =  par_DIST[<c,k>] /par_VELO ;

      //  Parametro: TESP(c) - Tiempo de espera en el destino c Tabla: (CLIENTE-R)
      tuple Ipar_TESP {  string c; }
      tuple Tpar_TESP {  string c; float val_TESP ;}
      {Ipar_TESP} IIpar_TESP = ...;
      {Tpar_TESP} Dpar_TESP = ...;
      float par_TESP[IIpar_TESP] = [<c>:val_TESP | <c,val_TESP> in Dpar_TESP] ;

      //  Parametro: COVA(v) - Costo Variable Uso Vehiculo  Tabla: (VEHICULO-R)
      tuple Ipar_COVA {  string v; }
      tuple Tpar_COVA {  string v; float val_COVA ;}
      {Ipar_COVA} IIpar_COVA = ...;
      {Tpar_COVA} Dpar_COVA = ...;
      float par_COVA[IIpar_COVA] = [<v>:val_COVA | <v,val_COVA> in Dpar_COVA] ;

      ///// Parametro: Dpar_HOIN Hora de inicio ventana de tiempo del cliente
      tuple Ipar_HOIN {  string c; }
      tuple Tpar_HOIN {  string c; float val_HOIN ;}
      {Ipar_HOIN} IIpar_HOIN = ...;
      {Tpar_HOIN} Dpar_HOIN = ...;
      float par_HOIN[IIpar_HOIN] = [<c>:val_HOIN | <c,val_HOIN> in Dpar_HOIN] ;

      ///// Parametro: Dpar_HOFI Hora de fin ventana de tiempo del cliente
      tuple Ipar_HOFI {  string c; }
      tuple Tpar_HOFI {  string c; float val_HOFI ;}
      {Ipar_HOFI} IIpar_HOFI = ...;
      {Tpar_HOFI} Dpar_HOFI = ...;
      float par_HOFI[IIpar_HOFI] = [<c>:val_HOFI | <c,val_HOFI> in Dpar_HOFI] ;

      //Conjunto de Trabajos predecesores
      {string} set_PRE[c in set_CLI] = { k |k in  set_KLI:par_HOIN[<k>]+par_TESP[<k>]+par_TVIA[k,c]<=par_HOFI[<c>]&& par_HOIN[<c>]+par_TESP[<c>]+par_TVIA[c,k]>par_HOFI[<k>]&& c!=k};
      //Conjunto de Trabajos Sucesores
      {string} set_SUC[c in set_CLI] = { k |k in  set_KLI:par_HOIN[<c>]+par_TESP[<c>]+par_TVIA[c,k]<=par_HOFI[<k>]&& par_HOIN[<k>]+par_TESP[<k>]+par_TVIA[k,c]>par_HOFI[<c>]&& c!=k};
      //Conjunto de clientes que no pueden ser asignados al mismo vehiculo que el cliente c es asignado.
      {string} set_CNAS[c in set_CLI] = { k |k in set_KLI:par_HOIN[<c>]+par_TESP[<c>]+par_TVIA[c,k]>par_HOFI[<k>]&& par_HOIN[<k>]+par_TESP[<k>]par_TVIA[k,c]>par_HOFI[<c>]&& c!=k};

      ///////////Variables CP///////////////////////////
      ////////////////////////////////////////////////
      dvar interval Task[c in master_c] size 1;//par_TESP[c]
      dvar interval vehiculos[set_CLI][set_VEH] optional;
      dvar sequence Ruta[v in set_VEH]in all(c in set_CLI)vehiculos[c][v];
      dvar int
      dist[set_CLI];
      dvar int+ tdist[set_VEH];

      // Variable FO = Funcion Objetivo
      dvar int FO ; // Ecuacion Funcion Objetivo

      // BINARY Variables
      dvar boolean var_AVL[v in master_v];   // AVL(v) - Asignación Vehículo
      dvar boolean var_Y[c in set_CLI][k in set_KLI]; // Deteremina si se visita al cliente c antes que el cliente k (Determinar Teimpo de Viaje)
      ;
       
      constraint cons_VETI[c in master_c] ;  // Ventana de Tiempo inferior
      constraint cons_VETS[c in master_c] ;  // Ventana de Tiempo Superior
      constraint cons_PRSE[c in set_CLI][o in set_NOR];  // El primer servicio del tour, Salida Nodo Origen
      constraint cons_ASIV[c in master_c] ;  // Cada cliente debe ser asignado a un vehiculo
      constraint cons_OVERL[V in master_v]; //Las tareas asignadas a un vehiculo no se pueden traslapar
      constraint cons_CAUV[v in master_v][c in master_c] ;  // Asignacion de un vehiculo a cada cliente
      constraint cons_UTVE[v in master_v] ;  // UTVE(v) - Utilizacion Vehiculo
      constraint cons_VCLI[c in set_CLI] ;  // VCLI(c) - Visita de destinos
      constraint cons_CADV[c in set_CLI][k in set_KLI][v in master_v] ;  //Clietes asignados a diferente vehiculo
      constraint cons_DISE[c in set_CLI][k in set_KLI][v in master_v] ;  //Determinacion inicio servicio
      constraint cons_DISS[c in set_CLI][k in set_KLI][v in master_v] ;//Determinacion inicio servicio sucesores
      constraint cons_DISP[c in set_CLI][k in set_KLI][v in master_v] ;//Determinacion inicio servicio predecesores
      constraint cons_DIPC[c in set_CLI][o in set_NOR];  // Distancia recorrida hacia el primer cliente
      constraint cons_DDRE[c in set_CLI][k in set_KLI][v in master_v] ;  //Determinacion distancia recorrida 
      constraint cons_DDRS[c in set_CLI][k in set_KLI][v in master_v] ;//Determinacion distancia recorrida sucesores
      constraint cons_DDRP[c in set_CLI][k in set_KLI][v in master_v] ;//Determinacion distancia recorrida predecesores
      constraint cons_DTOT[v in master_v] [c in set_CLI][o in set_NOR];//Distancia total recorrida

      // FO_MCOP; // Funcion Objetivo

      execute {
        //cp.param.FailLimit = 10000;
        cp.param.TimeLimit = 1200;
      }
      minimize FO ;  subject to {

      // Restriccion Limite inferior de la ventanas de tiempo
      forall(c in master_c)cons_VETI[c]:
      startOf(Task[c])>=par_HOIN[<c>];

      // Restriccion Limite superior de la ventanas de tiempo
      forall(c in master_c)cons_VETS[c]:
      startOf(Task[c])<=par_HOFI[<c>];

      /**El primer servicio del tour no puede empezar hasta que el vehiculo llegue al cliente
      desde el deposito**/

      forall(k in set_KLI, o in set_NOR)cons_PRSE[k][o]:
      startOf(Task[k])>=par_TVIA[o,k];

      //Restricciones que definen que cada cliente debe ser asignado a un vehiculo
      forall(c in set_CLI) cons_ASIV[c]:
            alternative(Task[c], all(v in set_VEH) vehiculos[c][v]); 
         
      forall(v in set_VEH) cons_OVERL[v]:
          noOverlap(Ruta [v]); 
       
      ///Clientes que no pueden ser asignados al mismo vehiculo debido a la ventana de tiempo
      forall(c in set_CLI,k in set_KLI,v in set_VEH)cons_CADV[c][k][v]:
      if(k in set_CNAS[c]){
      presenceOf(vehiculos[c][v])+presenceOf(vehiculos[k][v])<=1;   <br /> }

      ////Determinacion del tiempo de inicio del servicio en cada cliente
      forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DISE[c][k][v]:
      if(k not in set_PRE[c]&& k not in set_SUC[c] && k not in set_CNAS[c]&& c!=k)
      {

      startOf(Task[k])>=(endOf(Task[c])+ par_TVIA[c,k]-INFI*(1-var_Y[c][k]))*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
      startOf(Task[c])>=(endOf(Task[k])+ par_TVIA[k,c]-INFI*var_Y[c][k])*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);

      }
      //Restriccion de Sucesores (Para el Tiempo de Viaje)
      forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DISS[c][k][v]:
      if(k in set_SUC[c] && c!=k) //
      {
      startOf(Task[k])>=(endOf(Task[c])+ par_TVIA[c,k])*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
      }
      //Restriccion de Precedencia (Para el Tiempo de Viaje)
      forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DISP[c][k][v]:
      if(k in set_PRE[c] && c!=k) // 
      {
      startOf(Task[c])>=(endOf(Task[k])+ par_TVIA[k,c])*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
      }

      //////Determinacion de la distancia recorrida cuando un vehiculo llega al primer cliente de cada tour
      forall(c in set_CLI,o in set_NOR)cons_DIPC[c][o]:
      dist[c]>=par_DIST[<o,c>];

      forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DDRE[c][k][v]:
      if( k not in set_PRE[c]&& k not in set_SUC[c] && k not in set_CNAS[c]&& c!=k)
      {
      dist[k]>=(dist[c]+par_DIST[<c,k>]-INFI*(1-var_Y[c][k]))*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
      dist[c]>=(dist[k]+par_DIST[<k,c>]-INFI*var_Y[c][k])*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);

      }
      //Restriccion de Sucesores (Para la distancia recorrida)
      forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DDRS[c][k][v]:
      if( k in set_SUC[c]&& c!=k)
      {
      dist[k]>=dist[c]+par_DIST[<c,k>]*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
      }
      //Restriccion de Precedencia (Para la distancia recorrida)
      forall(c in set_CLI, k in set_KLI,v in set_VEH) cons_DDRP[c][k][v]:
      if(k in set_PRE[c]&& c!=k) // 
      {
      dist[c]>=dist[k]+par_DIST[<k,c>]*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
      }

      //Restriccion de Utilizacion del vehiculo
      forall(v in set_VEH)cons_UTVE[v]:
      sum(c in set_CLI) presenceOf(vehiculos[c][v])-100000*var_AVL[v]<=0;<br />
      //Determinacion de la distancia total recorrida por cada vehiculo
      forall(v in set_VEH,c in set_CLI,o in set_NOR)cons_DTOT[v][c][o]:
      tdist[v]>=(dist[c]par_DIST[<c,o>])*presenceOf(vehiculos[c][v]);

      //Funcion Objetivo CP

      //FO_MCOP:
      FO ==
      sum (v in set_VEH) tdist[v]*par_COVA[<v>]

      sum (v in set_VEH) par_CUVE[<v>] * var_AVL[v];

      // Fin Restricciones
      }

      using presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]) the model generate a huge number of constraints, for this reason the run time is large. Any suggestion for model this constraints?
      Thanks
      Carlos S
      Updated on 2009-07-08T05:27:13Z at 2009-07-08T05:27:13Z by SystemAdmin
      • SystemAdmin
        SystemAdmin
        623 Posts
        ACCEPTED ANSWER

        Re: VRPTW with CP

        ‏2009-07-16T22:39:15Z  in response to SystemAdmin

        [JR said:]

        Hi Paul

        You should use the scheduling constraint offered by CPO. That is :

        replace
        startOf(Task[k])>=(endOf(Task[c])+ par_TVIA[c,k]-INFI*(1-var_Y[c][k]))*presenceOf(vehiculos[c][v])*presenceOf(vehiculos[k][v]);
        by
        endBeforeStart(Task[c]), Task[k], par_TVIA[c,k]);

        The reason is it consider the optional status of the involved interval

        In general, with CPO, you have few cases that needs to use the presence constraint in temporal constraint and never to use big M. The CPO scheduling constraints semantic and expressions does this for you.



        In any case, I do think the extra constraint you add (the precedences and distances from origin) are useless. You have simply to add a distance matrix to the noOverlap constraint. Please refer to trolley2.mod and sched_sequence.mod samples delived with OPL


        Cheers
  • SystemAdmin
    SystemAdmin
    623 Posts
    ACCEPTED ANSWER

    Re: VRPTW with CP

    ‏2013-01-22T10:49:05Z  in response to SystemAdmin
    Is it possible for you to post the data file you are using with this model?