Splitting capacity across trucks

[DanHouston]

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

[RobPratt]

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]

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

[RobPratt · Accepted solution]

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]

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.