BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
DanHouston
Obsidian | Level 7

I am using this example, and wondering what would have to change to use more than 1 truck to meet the demands of a node:

https://documentation.sas.com/doc/en/pgmsascdc/9.4_3.2/casmopt/casmopt_decomp_examples12.htm

 

I adjusted the capacity down so that it would have to split between two trucks, but it becomes infeasible. I'm not totally sure which constraint is causing that to happen. I think it is the FlowBalance constraint, but not sure how it should adjust. Any help would be great.

 

Thanks,

Dan

1 ACCEPTED SOLUTION

Accepted Solutions
RobPratt
SAS Super FREQ

A heuristic idea is to keep the optimization model the same but modify the input data to split demands across multiple copies of the existing nodes.  For example, the following DATA step splits nodes 8 and 17 in the input:

data vrpdata;
   input node x y demand;
   datalines;
1  145 215    0
2  151 264 1100
3  159 261  700
4  130 254  800
5  128 252 1400
6  163 247 2100
7  146 246  400
8.1  161 242  400
8.2  161 242  400
9  142 239  100
10 163 236  500
11 148 232  600
12 128 231 1200
13 156 217 1300
14 129 214 1300
15 146 208  300
16 164 208  900
17.1 141 206 500
17.2 141 206 500
17.3 141 206 500
17.4 141 206 500
17.5 141 206 100
18 147 193 1000
19 164 193  900
20 129 189 2500
21 155 185 1800
22 139 182  700
;

The resulting optimal solution has optimal objective value 585 instead of 603.

 

If you instead want the solver to determine the best way to split the demands, you can keep the original data and replace the FlowBalance constraints as follows:

*   con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:
       sum {<j,(i)> in ARCS} Flow[j,i,k] - sum {<(i),j> in ARCS} Flow[i,j,k]
       = demand[i] * UseNode[i,k];
   var DemandSatisfied {NODES diff {depot}, VEHICLES} >= 0 <= capacity;
   con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:
       sum {<j,(i)> in ARCS} Flow[j,i,k] - sum {<(i),j> in ARCS} Flow[i,j,k]
       = DemandSatisfied[i,k];
   con DemandSatisfaction {i in NODES diff {depot}}:
      sum {k in VEHICLES} DemandSatisfied[i,k] = demand[i];

 

View solution in original post

4 REPLIES 4
RobPratt
SAS Super FREQ

Do you want to allow splitting of each demand into two equal demands, or do you want to allow arbitrary splits into two or more not necessarily equal demands?

DanHouston
Obsidian | Level 7

Does not need to be equal, just needs to be able to split when demand is greater than capacity of a truck.

RobPratt
SAS Super FREQ

A heuristic idea is to keep the optimization model the same but modify the input data to split demands across multiple copies of the existing nodes.  For example, the following DATA step splits nodes 8 and 17 in the input:

data vrpdata;
   input node x y demand;
   datalines;
1  145 215    0
2  151 264 1100
3  159 261  700
4  130 254  800
5  128 252 1400
6  163 247 2100
7  146 246  400
8.1  161 242  400
8.2  161 242  400
9  142 239  100
10 163 236  500
11 148 232  600
12 128 231 1200
13 156 217 1300
14 129 214 1300
15 146 208  300
16 164 208  900
17.1 141 206 500
17.2 141 206 500
17.3 141 206 500
17.4 141 206 500
17.5 141 206 100
18 147 193 1000
19 164 193  900
20 129 189 2500
21 155 185 1800
22 139 182  700
;

The resulting optimal solution has optimal objective value 585 instead of 603.

 

If you instead want the solver to determine the best way to split the demands, you can keep the original data and replace the FlowBalance constraints as follows:

*   con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:
       sum {<j,(i)> in ARCS} Flow[j,i,k] - sum {<(i),j> in ARCS} Flow[i,j,k]
       = demand[i] * UseNode[i,k];
   var DemandSatisfied {NODES diff {depot}, VEHICLES} >= 0 <= capacity;
   con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:
       sum {<j,(i)> in ARCS} Flow[j,i,k] - sum {<(i),j> in ARCS} Flow[i,j,k]
       = DemandSatisfied[i,k];
   con DemandSatisfaction {i in NODES diff {depot}}:
      sum {k in VEHICLES} DemandSatisfied[i,k] = demand[i];

 

DanHouston
Obsidian | Level 7

Thanks Rob!

 

We actually were doing a data solution and not even asking the solver to solve it, which was a little inefficient in cases where it could better make choices on how to fill trucks. As we add more and more to this problem I suspect we'll have to let the optimizer solve the best way to split trucks out.

SAS Innovate 2025: Call for Content

Are you ready for the spotlight? We're accepting content ideas for SAS Innovate 2025 to be held May 6-9 in Orlando, FL. The call is open until September 25. Read more here about why you should contribute and what is in it for you!

Submit your idea!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.

Discussion stats
  • 4 replies
  • 872 views
  • 0 likes
  • 2 in conversation