Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
Expand all | Collapse all

Modelling a time-space-network

Archive User

Archive UserMon July 08, 2019 07:29 AM

  • 1.  Modelling a time-space-network

    Posted Mon July 08, 2019 07:29 AM

    Originally posted by: Steps93


    Hello everybody,

     

    I would like to model a time-space network in context of a carsharing provider that is defined by S (stations) x (0,... t,..., Tmax) with different arcs that connect a node i at time t to a node j at time t' with t'>t. Each arc is associated with different values (for example profit).

    Do you have any ideas how to implementate these arcs? So far my idea was to define different tuples but i had problems integrating the time-component. Do you know if it's possible to solve such problem with tuples at all?

     

    Thanks a lot.


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 2.  Re: Modelling a time-space-network

    Posted Mon July 08, 2019 08:53 AM

    Hi,

    in documentation IDE and OPL > Optimization Programming Language (OPL) > Language Reference Manual > OPL, the modeling language > Data sources > Data consistency

    you may read

    
    
    
    {int} nodes = {1, 5, 7};
     
    tuple 
    arc  {
      int 
    origin
    ;
      int 
    
    
    destination
    
    ;
    }
     
    {
    arc} 
    
    
    arcs2 with 
    origin 
    in nodes, 
    
    
    destination 
    in nodes = 
      {<1,4>, <5,7>};
     
    execute {
      writeln(
    
    
    arcs2);
    };
    

    Plus have you had a look at the example in


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 3.  Re: Modelling a time-space-network

    Posted Mon July 08, 2019 09:39 AM

    Originally posted by: Steps93


    Hello Alex,

    many thanks for your quick response.

    I have read your stated code & the example you sent. But i'm still not sure how to implement the time-component within my different arcs.

    Let's say there is one arc, described by: 

     

    Ac: arcs a = (it, jt') -> customer travels from station i at time t to station j at time t'

     

    followed by a demand constraint (2, marked blue in attached image). 

     

    So far i have created tuples providing the information about start and end node, as given in your example code.

    But now i'm not quite sure, whether i have to implement the time dimension within the tuples or as an additional variable. 

     

    regards

    steps93


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 4.  Re: Modelling a time-space-network

    Posted Mon July 08, 2019 09:58 AM

    Hi,

    you may use nodes with time within a tuple.

    Let me adapt the previous example I mentioned:

    tuple nodetime
    {
      int n;
      int t;
    }

    {nodetime} nodes = {<1,1>, <5,2>, <7,3>};
     
    tuple arc  {
      nodetime origin;
      nodetime destination;
    }
     
    {arc} arcs2 with origin  in nodes, destination in nodes = {<<1,1>,<5,2>>, <<5,2>,<7,3>>};
     
    execute {
      writeln(arcs2);
    };

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 5.  Re: Modelling a time-space-network

    Posted Mon July 08, 2019 11:26 AM

    Originally posted by: Steps93


    Hey Alex,

     

    just for clarity a few questions.

     

    I modified your code a little bit (only the values):

    tuple nodetime
    {
      int n;
      int t;
    }
    
    {nodetime} nodes = {<0,1>, <1,3>};
     
    tuple arc  {
      nodetime origin;
      nodetime destination;
    }
     
    {arc} arcs2 with origin  in nodes, destination in nodes = {<<0,1>,<1,3>>};
     
    execute {
      writeln(arcs2);
    };
    

    If i were to interpret these code..

    {<<0,1>,<1,3>>} means nodetime 0 & origin 1 as well as nodetime 1 & destination 3 ?

    Regarding the carsharing-case: a car drives from origin to destination, this would generate some profit because the customer has to pay per minute; how could I assign these values to the single arcs?

     

    We have a distance matrix with distances between the stations, that we use to assign the profit to all customer arcs.

     

    regards

     

     


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 6.  Re: Modelling a time-space-network

    Posted Mon July 08, 2019 12:00 PM

    Hi,

    in order to add some income to arcs you could change

    tuple arc  {
      nodetime origin;
      nodetime destination;
    }

    into

    tuple arc  {
      nodetime origin;
      nodetime destination;

    float income;
    }

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 7.  Re: Modelling a time-space-network

    Posted Mon July 08, 2019 01:01 PM

    Originally posted by: Steps93


    Hi Alex,

     

    unfortunately i get an error when i insert "float income". I think i have to modify these line:

    {arc} arcs2 with origin  in nodes, destination in nodes = {<<0,1>,<1,3>>};

     

    In addition, maybe you can explain to me in a few sentences how this whole approach may help me on my problem?

     

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 8.  Re: Modelling a time-space-network

    Posted Tue July 09, 2019 02:02 AM

    Hi,

    tuple nodetime
        {
          int n;
          int t;
        }

        {nodetime} nodes = {<1,1>, <5,2>, <7,3>};
         
        tuple arc  {
          nodetime origin;
          nodetime destination;
          float income;
        }
         
        {arc} arcs2 with origin  in nodes, destination in nodes = {<<1,1>,<5,2>,1.1>, <<5,2>,<7,3>,2.2>};
         
        execute {
          writeln(arcs2);
        };

    works fine and gives

     

    {<<1 1> <5 2> 1.1> <<5 2> <7 3> 2.2>}

     

    Your question was how to model profit with arcs and time and that's an option.

    Then if you want to assign vehicles to arcs you could use a dvar boolean array that states whether a vehicle v visits a time arc.

    I think you could also have a look at the VRPTW model I shared with you.

    In https://www.linkedin.com/pulse/model-building-oplcplex-alex-fleischer/

    you could have a look at Milk collection

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 9.  Re: Modelling a time-space-network

    Posted Wed July 10, 2019 04:11 PM

    Originally posted by: Steps93


    Hey Alex,

     

    many thanks for your help. We are making progress!

     

    There is another question that came up.

     

    Suppose you want to do an 'union' on 2 tuples but not on every tuple component in it.

    Example:

    There is one arc Set A which is partitioned into several subsets of specific Arcs. Here are two them. Partly they are associated with different values (e.g. they differ in demand).

      

      tuple arcCustomer
        {
          int startTime;
          int endTime;
          string origin;
          string destination;    
          int profit;
          float batteryChange;
          int demand;
        }

        {arcCustomer} arcCustomers = ...;
        
        
      tuple arcWait
        {
          int startTime;
          int endTime;
          string origin;
          string destination;    
          int profit;
          float batteryChange;
          int demand;
        }

     

    Now we want to do an 'union' on both tuples but only on time (startTime & endTime) and nodes (origin & destination), because the other values can be different from each other.

     

    Is that possible?

     


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 10.  Re: Modelling a time-space-network

    Posted Thu July 11, 2019 01:18 AM

    Hi,

    of course that s possible.

    Let me share a tiny example:

    tuple t1
    {
    int o;
    int d;
    int v;
    };

    tuple t2
    {
    int o;
    int d;
    int w;
    }

    {t1} s1={<1,2,4>,<2,3,9>};

    {t2} s2={<1,2,9>,<2,5,10>};

    tuple t
    {
    int o;
    int d;
    }

    {t} s={<i.o,i.d> | i in s1} union {<i.o,i.d> | i in s2};

    execute
    {
    writeln(s);
    }

    which gives

     

    {<1 2> <2 3> <2 5>}

    regards

     

    PS:

     

    1) Do not hesitate to start new threads for new questions

    2) Many how to with OPL at https://www.linkedin.com/pulse/how-opl-alex-fleischer/


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 11.  Re: Modelling a time-space-network

    Posted Thu July 11, 2019 02:11 AM

    Originally posted by: Steps93


    Hey Alex,

     

    next time i will start a new thread.

     

    There is a problem with your solution. I still need the other values as demand, batteryCharge etc in the arcs after the union.

    Union only on time & nodes but still keep the other values.

    Sorry if i was not clear enough.

     

    I'm not sure if that is possible at all.

     

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 12.  Re: Modelling a time-space-network

    Posted Thu July 11, 2019 03:07 AM

    Yes, you can do that. Here is an example for the demand. You can add more fields as you please, I just restricted myself to demand to keep things short:

    tuple arcCustomer {
      int startTime;
      int waitTime;
      string origin;
      string destination;
      int demand;
    }
    tuple arcWait {
      int startTime;
      int waitTime;
      string origin;
      string destination;
      int demand;
    }
    tuple unionKey {
      int startTime;
      int waitTime;
      string origin;
      string destination;
    }
    // Tuple to hold the union elements in case we want to distinguish the demands
    // from the two original sets.
    tuple arcUnionBoth {
      int startTime;
      int waitTime;
      string origin;
      string destination;
      int demandCustomer;
      int demandWait;
    }
    // Tuple to hold the union elements in case we want to sum the demands from
    // the two original sets.
    tuple arcUnionSum {
      int startTime;
      int waitTime;
      string origin;
      string destination;
      int demandSum;
    }

    {arcCustomer} customer = { <1, 1, "a", "b", 1>,
                               <1, 2, "a", "b", 2> };
    {arcWait}     wait     = { <1, 1, "a", "b", 3>,
                               <1, 3, "a", "b", 4> };

    // Create a set that contains the <startTime,waitTime,origin,destination>
    // tuples that will appear in the union.
    {unionKey} unionKeys = { <t.startTime, t.waitTime, t.origin, t.destination> | t in customer }
                           union
                           { <t.startTime, t.waitTime, t.origin, t.destination> | t in wait };

    // Construct the elements in unionBoth. The first 4 elements are just the
    // keys from unionKeys. The next two elements are the matching demands from
    // the customer and wait set, respectively.
    {arcUnionBoth} unionBoth = { <k.startTime,k.waitTime,k.origin,k.destination,
                                  sum (t in customer : t.startTime == k.startTime &&
                                                       t.waitTime == k.waitTime &&
                                                       t.origin == k.origin &&
                                                       t.destination == k.destination) t.demand
                                  ,
                                  sum (t in wait     : t.startTime == k.startTime &&
                                                       t.waitTime == k.waitTime &&
                                                       t.origin == k.origin &&
                                                       t.destination == k.destination) t.demand>
                                 | k in unionKeys };

    // Construct the elements in unionBoth. The first 4 elements are just the
    // keys from unionKeys. The next element is the sum of the demands of all
    // matching elements.
    {arcUnionSum} unionSum   = { <k.startTime,k.waitTime,k.origin,k.destination,
                                  sum (t in customer : t.startTime == k.startTime &&
                                                       t.waitTime == k.waitTime &&
                                                       t.origin == k.origin &&
                                                       t.destination == k.destination) t.demand
                                  + // this differs from unionBoth
                                  sum (t in wait     : t.startTime == k.startTime &&
                                                       t.waitTime == k.waitTime &&
                                                       t.origin == k.origin &&
                                                       t.destination == k.destination) t.demand>
                                 | k in unionKeys };

    execute {
      writeln("unionBoth:");
      writeln(unionBoth);
      writeln("unionSum:");
      writeln(unionSum);
    }


    Note: I think in each of your sets the combination of <startTime, endTime, origin, destination> is unique, i.e., you don't have two tuples in the same set that have the same value in all of the four fields. In that case you can improve performance a little by marking these four fields as "key" (see here):

    tuple arcCustomer {
      key int startTime;
      key int waitTime;
      key string origin;
      key string destination;
          int demand;
    }
    tuple arcWait {
      key int startTime;
      key int waitTime;
      key string origin;
      key string destination;
          int demand;
    }
    tuple unionKey {
      key int startTime;
      key int waitTime;
      key string origin;
      key string destination;
    }

     


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 13.  Re: Modelling a time-space-network

    Posted Thu July 11, 2019 04:47 AM

    Originally posted by: Steps93


    Hey DanielJunglas,

     

    thank you very much for your answer!

    I still have one problem:

     

     tuple arcUnionBoth {
      int startTime;
      int waitTime;
      string origin;
      string destination;
      int demandCustomer;
      int demandWait;
     }

     

    arcUnionBoth contains now demandCustomer & demandWait. So if the model can't find a demand in Customer or in Wait, then the model sets the respective value equal 0. I'm not interested in the 0-values though.

    Is there a way to keep the initial tuple structure? 

     

    Desired tuple structure:

     

     tuple arcUnionBoth {
      int startTime;
      int waitTime;
      string origin;
      string destination;
      int demand;
     }

     

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 14.  Re: Modelling a time-space-network

    Posted Thu July 11, 2019 08:27 AM

    Yes, that is possible. But you to specify what the demand field should be set to in the union tuple. Should it be the demand from the customer tuple? The demand from the wait tuple? The sum of both? The max of both?

    In case it is the sum of both (where non-existing tuples contribute a 0) you already have the arcUnionSum tuple and unionSum in my example that achieve that. If that is not what you want, then please specify how field demand should be defined in the union tuple.


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 15.  Re: Modelling a time-space-network

    Posted Thu July 11, 2019 08:38 AM

    Hi,

    so instead of

    unionBoth:
     {<1 1 "a" "b" 1 3> <1 2 "a" "b" 2 0>
         <1 3 "a" "b" 0 4>}

    you need

    unionBoth:
     {<1 1 "a" "b" 4> <1 2 "a" "b" 2 >
         <1 3 "a" "b" 4>}

    or

     

    unionBoth:
     {<1 1 "a" "b" 1 > <1 1 "a" "b" 3> <1 2 "a" "b" 2 >
         <1 3 "a" "b" 4>}

    ?

     

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer