MODEL:
! (Dial_a_Ride) The traveling salesperson problem with the additional
condition that certain pairs of stops must be visited in a given order.
Specifically, for i even, stop i must be visited before stop i+1.
The interpretation is that someone is to be picked up at i and later
dropped off at i+1. The vehicle has sufficient capacity so that it
can carry as many people as necessary.
Stop 1 is the home base where no one is picked up and no one is dropped off;
! Keywords: Dial-a-ride, TSP, Traveling sales person, Routing, Tour, Sequencing;
SETS:
CITY: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X; ! X( I, J) = 1 if link I, J is in tour;
ENDSETS
DATA: ! Distance matrix, it need not be symmetric;
CITY=
1..15;
DIST=
0 69 39 49 5 59 19 40 33 81 9 21 8 37 33
69 0 47 39 54 9 49 59 95 47 98 87 69 36 67
41 47 0 90 67 63 4 49 93 48 7 94 52 19 41
49 39 90 0 21 60 56 80 12 69 54 52 33 99 2
5 54 67 21 0 32 22 61 85 47 56 75 59 42 63
59 9 63 60 32 0 58 46 43 3 33 65 69 80 37
19 49 4 56 22 58 0 82 97 15 78 82 64 33 26
37 59 49 80 61 46 82 0 8 86 1 90 37 0 42
33 95 93 12 85 43 97 8 0 63 34 81 21 56 0
82 47 48 69 47 3 15 86 63 0 88 69 33 47 90
9 98 7 54 56 33 78 1 34 88 0 77 63 87 57
21 87 94 52 75 65 82 90 81 69 77 0 46 30 63
8 69 52 33 59 69 64 37 21 33 63 46 0 59 95
38 36 21 99 42 80 33 0 56 47 87 30 59 0 40
33 67 41 2 63 40 26 42 0 90 57 63 95 40 0;
ENDDATA
!-----------------------------------------------------------;
! Warning: May take long to solve cases with N >> 12;
! Variables:
X(i,j) = 1 if vehicle tour includes link from i to j, else 0,
U(i) = sequence number of stop i on the tour, or also
load on vehicle upon departing stop i. One unit of
load is picked up at each stop. Starts empty at stop 1;
N = @SIZE( CITY);
! Minimize total distance traveled;
MIN = @SUM( LINK(i,j): DIST(i,j) * X(i,j));
! Stop k must be entered exactly once;
! For k = 1, we return to 1 only from an odd numbered (drop off) stop;
@SUM( CITY(i) | @mod(i,2) #NE# 0 #and# i #NE# 1: x(i,1)) = 1;
@SUM( CITY(i) | @mod(i,2) #EQ# 0 : x(i,1)) = 0;
@FOR( CITY(k) | k #GT# 1:
@SUM( CITY( i)| i #NE# k: X( i, k)) = 1;
);
! Stop k must be departed exactly once;
! For k = 1, we go first to an even numbered (pick up) stop;
@SUM( CITY(j) | @mod(j,2) #EQ# 0 : x(1,j)) = 1;
@SUM( CITY(j) | @mod(j,2) #NE# 0 : x(1,j)) = 0;
@FOR( CITY(k) | k #GT# 1:
@SUM( CITY( j)| j #NE# k: X( k, j)) = 1;
X( k, k) = 0; ! Cannot go from k to k;
);
U(1) = 0; ! Start empty;
! A weak but simple form of the subtour breaking constraints,
see Desrochers & Laporte, OR Letters, Feb. 91.
Not very powerful for large(N>12) problems;
! Enforce:
If x(i,j) = 1 then U(j) - U(i) = 1,
If x(j,i) = 1 then U(j) - U(i) = -1,
If x(i,j) + x(j,i) = 0, and i,j > 1,
then U(j) - U(i) >= -(N - 2);
! The case either i or j = 1;
@FOR( CITY(i) | i #GT# 1:
U(i) >= 2 - X(1,i) + (N-3)*X(i,1);
U(i) <= (N-2) + X(i,1) - (N-3)*X(1,i);
);
! The case i,j > 1,
! This constraint, plus its "mirror", when i and j are switched,
forces U(j) - U(i) = 1 if X(i,j) = 1;
@FOR( LINK(i,j)| i #GT# 1 #AND# j #GT# 1 #AND# i #NE# j:
U( j) >= U( i) + X(i,j)
- X(j,i)
- (N-2)*(1 - X(i,j) - X(j,i));
);
! Make the X's 0/1;
@FOR( LINK(i,j): @BIN( X(i,j)););
! The dial-a-ride feature. Every pickup occurs before its dropoff;
@FOR(CITY(i) | @mod(i,2)#EQ#0 : U(i) <= U(i+1));
! Some cuts;
! We know the sum of the stop numbers;
@SUM( CITY( i): U( i)) = ( N-1)*N/2;
|
