Topic
  • 4 replies
  • Latest Post - ‏2013-01-22T10:49:05Z by SystemAdmin
SystemAdmin
SystemAdmin
623 Posts

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

    Re: VRPTW with CP

    ‏2009-07-07T05:21:53Z  

    [shaw said:]

    Hello,

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


    Paul
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: VRPTW with CP

    ‏2009-07-08T05:27:13Z  

    [shaw said:]

    Hello,

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


    Paul

    [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

    Re: VRPTW with CP

    ‏2009-07-16T22:39:15Z  

    [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

    [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

    Re: VRPTW with CP

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