! Path or itinerary based approach for modeling the
origin/destination )OD) shipping model in LINGO.
We are given:
A network of nodes and legs(or arcs, links).
Each leg of the network has a capacity limit.
There is a set of origin>destination (OD)
pairs of nodes in the network with a
demand amount desired to be shipped for each OD pair.
A path is a set of legs starting at an origin node and
ending at a destination note. Each path has a profit
contribution per unit shipped over this path. There may
be several paths for a single OD pair.
We want to decide how much to ship over each path
so as to:
Maximize the total profit contribution,
subject to
not exceeding the desired demand for any OD pair,
and not exceeding the capacity of any leg.
The Path formulation allows you to take into account that
paths that are too long from a source to a destination
need not be generated;
! Keywords: OriginDestination, Routing, Shipping, Path formulation;
SETS:
NODE; ! Node set of the network ;
LEG(NODE, NODE): ! Leg/Link/Arc set of network;
CAP; ! CAP(j,k) = capacity of leg from node j to node k;
ODPAIR(NODE,NODE): ! Origin>destination pairs;
DEM; ! DEM(s,d) = amount our customers would like to ship
from origin/source s to destination d;
PATH; ! Paths in network that are feasible.
A path is a set of connected legs;
PXOD( PATH, ODPAIR) : ! Identify the origin and destination
associated with path p;
PC, ! PC(p,s,d) = Profit contribution per unit shipped
over path/itinerary p from source s to destination d;
VOL; ! VOL(p,s,d) = volume shipped via itinerary p;
! Important a unique origin and a unique destination. There may
be several paths p with the same s and d ;
PXL( PATH, LEG); ! The sets of (p,j,k) of the Legs (j,k) that
are part of path p;
ENDSETS
DATA:
NODE = H1 H2 N3 N4 N5 N6; ! Nodes in network;
! Describe the network connections;
! In this data set, H1 and H2 are hubs, all shipments
involving N3 and higher go through either H1 or H2
In general, this need not be the case.
In the solution, notice that because of capacity
constraints not every shipment can go by its
most profitable path;
LEG, CAP =
H1 H2 54 ! Legs involving node 2 and lower;
H2 H1 54
N3 H1 18 ! Legs involving node 3 and lower;
N3 H2 18
H1 N3 18
H2 N3 18
N4 H1 18 ! Legs involving node 4 and lower;
N4 H2 18
H1 N4 18
H2 N4 18
N5 H1 18 ! Legs involving node 5 and lower;
N5 H2 18
H1 N5 18
H2 N5 18
N6 H1 18 ! Legs involving node 6 and lower;
N6 H2 18
H1 N6 18
H2 N6 18
;
! List the (origin, destination, demand) triples;
ODPAIR, DEM =
H2 H1 5 ! Demands involving node 2 and lower;
N3 H2 7 ! Demands involving node 3 and lower;
N4 N3 9 ! Demands involving node 4 and lower;
N5 N4 9 ! Demands involving node 5 and lower;
N3 N5 7
N6 N4 9 ! Demands involving node 6 and lower;
N3 N6 8
N5 N6 6
;
PATH = P1..P17; ! Path ID's;
PXOD, PC= ! List of (p,s,d, profit) 4tuples;
P1 H2 H1 6 ! Paths involving nodes up to 2;
P2 N3 H2 7 ! Paths involving nodes up to 3;
P3 N3 H2 6
P4 N4 N3 7 ! Paths involving node 4 and lower;
P5 N4 N3 6
P6 N5 N4 5 ! Paths involving node 5 and lower;
P7 N5 N4 4
P8 N3 N5 4
P9 N3 N5 3
P10 N3 N5 2
P11 N6 N4 5 ! Paths involving node 6 and lower;
P12 N6 N4 4
P13 N3 N6 5
P14 N3 N6 4
P15 N5 N6 7
P16 N5 N6 6
P17 N5 N6 5
;
! Set PXL actually defines the paths;
PXL = ! Insert (i,j,k) triples of legs in each path;
P1 H2 H1 ! H2>H1;
P2 N3 H2 ! N3>H2;
P3 N3 H1 ! N3>H1>H2;
P3 H1 H2
P4 N4 H1 ! N4>H1>N3;
P4 H1 N3
P5 N4 H2 ! N4>H2>N3;
P5 H2 N3
P6 N5 H1 ! N5>H1>N4;
P6 H1 N4
P7 N5 H2 ! N5>H2>N4;
P7 H2 N4
P8 N3 H2 ! N3>H2>N5;
P8 H2 N5
P9 N3 H1 ! N3>H1N5;
P9 H1 N5
P10 N3 H2 ! N3>H2>H1>N5;
P10 H2 H1
P10 H1 N5
P11 N6 H1 ! N6>H1>N4;
P11 H1 N4
P12 N6 H2 ! H6>H2>N4;
P12 H2 N4
P13 N3 H2 ! N3>H2>N6;
P13 H2 N6
P14 N3 H1 ! N3>H1>N6;
P14 H1 N6
P15 N5 H2 ! N5>H2>N6;
P15 H2 N6
P16 N5 H1 ! N5>H2>N6;
P16 H1 N6
P17 N5 H2 ! N5>H2>H1>N6;
P17 H2 H1
P17 H1 N6
;
ENDDATA
! To see the explicit scalar model, click on:
LINGO  Generate  Display model;
! Objective. Maximize profit contribution of shipments;
MAX = @SUM( PXOD(p,s,d): PC(p,s,d)*VOL(p,s,d));
! Demand constraints. Total shipped by all paths/itineraris
with source/origin s and destination d <= demand;
@FOR( ODPAIR( s,d):
[DEMC] @SUM( PXOD( p,s,d): VOL(p,s,d)) <= DEM(s,d);
);
! Capacity constraints. Volume shipped by all paths that use
leg (j,k) cannot exceed capacity of leg. For Leg (j,k),
find all paths p using leg(j,k), then get the volume
on that path p;
@FOR( LEG(j,k):
[CAPC] @SUM( PXL(p,j,k): @SUM(PXOD(p,s,d): VOL(p,s,d))) <= CAP( j,k);
);
