Model LINGO untuk mixed fleet VRP dengan time windows

Saya sedang ditugasi membuat model VRP dalam LINGO untuk suatu kasus. Model adalah VRP biasa dengan beberapa ketentuan:

  • Depot tunggal (single depot)
  • Kendaraan bervariasi (mixed fleet)
  • Time windows jenis hard

Berikut modelnya. Dicoba dengan LINGO versi 11. Model ini hanya untuk 6 customer. Jika lebih atau kurang, harus diubah pada kendala penghilangan subtour.

! referensi :
	[1] Dell'Amico et al. 2007. Heuristic Approaches for the FSMVRP with Time Windows. Transportation Science 41(4), pp. 516-526, © 2007 INFORMS.
	[2] Suthikarnnarunai. 2008. A Sweep Algorithm for the Mix Fleet Vehicle Routing Problem. Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol III MECS 2008, 19-21 March, 2008, Hong Kong.
;

! waktu running dengan data hipotetik ini : sekitar 10 detik ;
! contoh hasil rute dengan data ini :

      X( 1, 3, 2)        1.000000
      X( 1, 4, 1)        1.000000
      X( 2, 7, 2)        1.000000
      X( 3, 6, 2)        1.000000
      X( 4, 5, 1)        1.000000
      X( 5, 1, 1)        1.000000
      X( 6, 2, 2)        1.000000
      X( 7, 1, 2)        1.000000

! jadi rutenya: 
      kendaraan 2 : 1 - 3 - 6 - 2 - 7 - 1 
      kendaraan 1 : 1 - 4 - 5 - 1

;

DATA:
	JUMLAH_KENDARAAN = 3;
	JUMLAH_NODE = 7; ! 6 + depot ;
	M = 1000000000;
ENDDATA

SETS:
	KENDARAAN /1..JUMLAH_KENDARAAN/: Z, KAPASITAS, FIXED_COST, V, PHI;
	CUSTOMER /1..JUMLAH_NODE/: DEMAND, A, B, TAU, S;

	PELAYANAN(CUSTOMER, KENDARAAN) : Y;
	RUTE(CUSTOMER, CUSTOMER, KENDARAAN) : X;
	ARRIVAL(CUSTOMER, KENDARAAN) : T;

	BIAYA(CUSTOMER, CUSTOMER, KENDARAAN): COST;
	JARAK(CUSTOMER, CUSTOMER): D;
	DURASI(CUSTOMER, CUSTOMER, KENDARAAN): DUR;
ENDSETS

! parameter input :
	KAPASITAS(K)	= kapasitas maksimum kendaraan K		[2]
	FIXED_COST(K)	= fixed cost kendaraan K				[1]
	V(K)			= kecepatan kendaraan K
	DEMAND(I)		= demand customer I						[2]
	A(I)			= waktu buka customer I					[1]
	B(I)			= waktu tutup customer I				[1]
	S(I)			= waktu pelayanan di customer I			[1]
	D(I, J)			= jarak customer I ke customer J		[1]
	COST(I, J, K)	= cost dari customer I ke customer J dengan kendaraan K
	DUR(I, J, K)	= lama perjalanan dari customer I ke customer J dengan kendaraan K

! variabel yang dicari :
	X(I, J, K)	= 1 jika pelanggan J dikunjungi setelah I oleh K 	[2]
	Y(I, K)		= 1 jika pelanggan I dilayani oleh K 				[2]
	Z(K)		= 1 jika kendaraan K digunakan 					[1]
	T(I, K)		= waktu minimum kendaraan K untuk customer I 		[1]
	PHI(K)		= waktu berangkat kendaraan K						[1]
	TAU(I)		= waktu pelayanan customer I 						[1]
;

DATA:
	KAPASITAS  = 150 200 300;
	FIXED_COST = 400 250 500;
	V          =  60  60  50;

	D =   ! antara depot dengan depot (diagonal matriks) diberi nilai bilangan besar (misal 999) ;
		999	8.9	4.2	4.7	7.7	9.3	6.7
		8.9	999	5.9	2.9	2.6	2.3	4.7
		4.2	5.9	999	6.3	5.9	3.7	2.9
		4.7	2.9	6.3	999	2.3	3	5.6
		7.7	2.6	5.9	2.3	999	6.2	6.7
		9.3	2.3	3.7	3	6.2	999	5.4
		6.7	4.7	2.9	5.6	6.7	5.4	999;

	! depot diset 0 ;
	DEMAND =  0	 30 70 90 60 56 36;
	A      =  0	  8  8 10  8 12 10;
	B      =  0	 15 13 16 17 18 17;
	S      =  0	  1  2  2  1  2  3;

ENDDATA

! fungsi objektif ;

MIN = 
	@SUM(KENDARAAN(K) : FIXED_COST(K) * Z(K) + T(1, K) - PHI(K))
	+
	@SUM(CUSTOMER(I) :
		@SUM(CUSTOMER(J) :
			@SUM(KENDARAAN(K) : COST(I, J, K) * X(I, J, K));
		);
	);

! setiap customer dikunjungi sekali ;
! kendala (2) dalam [2] ;

@FOR(CUSTOMER(I) | I #NE# 1 :
	@SUM(KENDARAAN(K) : Y(I, K)) = 1;
);			

! jumlah keluar masuk depot harus sama ;
! kendala (3) dalam [2] ;

@SUM(KENDARAAN(K) : Y(1, K)) <= JUMLAH_KENDARAAN;

! kendaraan yang sama harus masuk dan keluar node kecuali depot ;
! kendala (4) dan (5) dalam [2] ;

@FOR(CUSTOMER(I) : 
	@FOR(KENDARAAN(K) :
		@SUM(CUSTOMER(J) | J #NE# I : X(I, J, K)) = Y(I, K);
		@SUM(CUSTOMER(J) | J #NE# I : X(J, I, K)) = Y(I, K);
	);
);

! demand tidak boleh melebihi kapasitas ;
! kendala (5) dalam [1] ;

@FOR(KENDARAAN(K) :
	@SUM(CUSTOMER(I) | I #NE# 1 : DEMAND(I) * Y(I, K)) <= KAPASITAS(K) * Z(K);
);	

! waktu pelayanan harus di antara jam buka dan jam tutup ;
! kendala (11) dalam [1] ;

@FOR(CUSTOMER(I) :
	TAU(I) >= A(I);
	TAU(I) <= B(I);
);

! pengaturan time windows ;
! kendala (7) sampai (10) dalam [1] ;

@FOR(KENDARAAN(K) :
	T(1, K) >= PHI(K);	
);

@FOR(KENDARAAN(K) :
	@FOR(CUSTOMER(I) | I #NE# 1 :
		TAU(I) >= T(I, K);
	);
);

@FOR(KENDARAAN(K) :
	@FOR(CUSTOMER(J) | J #NE# 1 :
		T(J, K) >= PHI(K) + DUR(1, J, K) - M*(1 - X(1,J,K));
	);
);

@FOR(KENDARAAN(K) :
	@FOR(CUSTOMER(I) | I #NE# 1 :
		@FOR(CUSTOMER(J) :
			T(J, K) >= TAU(I) + S(I) + DUR(I, J, K) - M*(1 - X(I, J, K));
		);	
	);
);

! hubungan antara jarak, kecepatan, dan biaya ;

@FOR(KENDARAAN(K) :
	@FOR(CUSTOMER(I) :
		@FOR(CUSTOMER(J) :
			V(K) * DUR(I, J, K) = D(I, J);
			COST(I, J, K) = DUR(I, J, K);
		);
	);
);


! subtour elimination, mengenumerasi seluruh subset ;
! {2, 3}  |  {2, 4}  |  {2, 5}  |  {2, 6}  |  {2, 7}  |  {3, 4}  |  {3, 5}  |  {3, 6}  |  {3, 7}  |  {4, 5}  |  {4, 6}  |  {4, 7}  |  {5, 6}  |  {5, 7}  |  {6, 7}  |  {2, 3, 4}  |  {2, 3, 5}  |  {2, 3, 6}  |  {2, 3, 7}  |  {2, 4, 5}  |  {2, 4, 6}  |  {2, 4, 7}  |  {2, 5, 6}  |  {2, 5, 7}  |  {2, 6, 7}  |  {3, 4, 5}  |  {3, 4, 6}  |  {3, 4, 7}  |  {3, 5, 6}  |  {3, 5, 7}  |  {3, 6, 7}  |  {4, 5, 6}  |  {4, 5, 7}  |  {4, 6, 7}  |  {5, 6, 7}  |  {2, 3, 4, 5}  |  {2, 3, 4, 6}  |  {2, 3, 4, 7}  |  {2, 3, 5, 6}  |  {2, 3, 5, 7}  |  {2, 3, 6, 7}  |  {2, 4, 5, 6}  |  {2, 4, 5, 7}  |  {2, 4, 6, 7}  |  {2, 5, 6, 7}  |  {3, 4, 5, 6}  |  {3, 4, 5, 7}  |  {3, 4, 6, 7}  |  {3, 5, 6, 7}  |  {4, 5, 6, 7}  |  {2, 3, 4, 5, 6}  |  {2, 3, 4, 5, 7}  |  {2, 3, 4, 6, 7}  |  {2, 3, 5, 6, 7}  |  {2, 4, 5, 6, 7}  |  {3, 4, 5, 6, 7}  |  {2, 3, 4, 5, 6, 7};
! kendala (7) dalam [2] ;

@FOR(KENDARAAN(K) :

	X(2, 3, K) + X(3, 2, K) <= 1;
	X(2, 4, K) + X(4, 2, K) <= 1;
	X(2, 5, K) + X(5, 2, K) <= 1;
	X(2, 6, K) + X(6, 2, K) <= 1;
	X(2, 7, K) + X(7, 2, K) <= 1;
	X(3, 4, K) + X(4, 3, K) <= 1;
	X(3, 5, K) + X(5, 3, K) <= 1;
	X(3, 6, K) + X(6, 3, K) <= 1;
	X(3, 7, K) + X(7, 3, K) <= 1;
	X(4, 5, K) + X(5, 4, K) <= 1;
	X(4, 6, K) + X(6, 4, K) <= 1;
	X(4, 7, K) + X(7, 4, K) <= 1;
	X(5, 6, K) + X(6, 5, K) <= 1;
	X(5, 7, K) + X(7, 5, K) <= 1;
	X(6, 7, K) + X(7, 6, K) <= 1;
	X(2, 3, K) + X(2, 4, K) + X(3, 2, K) + X(3, 4, K) + X(4, 2, K) + X(4, 3, K) <= 2;
	X(2, 3, K) + X(2, 5, K) + X(3, 2, K) + X(3, 5, K) + X(5, 2, K) + X(5, 3, K) <= 2;
	X(2, 3, K) + X(2, 6, K) + X(3, 2, K) + X(3, 6, K) + X(6, 2, K) + X(6, 3, K) <= 2;
	X(2, 3, K) + X(2, 7, K) + X(3, 2, K) + X(3, 7, K) + X(7, 2, K) + X(7, 3, K) <= 2;
	X(2, 4, K) + X(2, 5, K) + X(4, 2, K) + X(4, 5, K) + X(5, 2, K) + X(5, 4, K) <= 2;
	X(2, 4, K) + X(2, 6, K) + X(4, 2, K) + X(4, 6, K) + X(6, 2, K) + X(6, 4, K) <= 2;
	X(2, 4, K) + X(2, 7, K) + X(4, 2, K) + X(4, 7, K) + X(7, 2, K) + X(7, 4, K) <= 2;
	X(2, 5, K) + X(2, 6, K) + X(5, 2, K) + X(5, 6, K) + X(6, 2, K) + X(6, 5, K) <= 2;
	X(2, 5, K) + X(2, 7, K) + X(5, 2, K) + X(5, 7, K) + X(7, 2, K) + X(7, 5, K) <= 2;
	X(2, 6, K) + X(2, 7, K) + X(6, 2, K) + X(6, 7, K) + X(7, 2, K) + X(7, 6, K) <= 2;
	X(3, 4, K) + X(3, 5, K) + X(4, 3, K) + X(4, 5, K) + X(5, 3, K) + X(5, 4, K) <= 2;
	X(3, 4, K) + X(3, 6, K) + X(4, 3, K) + X(4, 6, K) + X(6, 3, K) + X(6, 4, K) <= 2;
	X(3, 4, K) + X(3, 7, K) + X(4, 3, K) + X(4, 7, K) + X(7, 3, K) + X(7, 4, K) <= 2;
	X(3, 5, K) + X(3, 6, K) + X(5, 3, K) + X(5, 6, K) + X(6, 3, K) + X(6, 5, K) <= 2;
	X(3, 5, K) + X(3, 7, K) + X(5, 3, K) + X(5, 7, K) + X(7, 3, K) + X(7, 5, K) <= 2;
	X(3, 6, K) + X(3, 7, K) + X(6, 3, K) + X(6, 7, K) + X(7, 3, K) + X(7, 6, K) <= 2;
	X(4, 5, K) + X(4, 6, K) + X(5, 4, K) + X(5, 6, K) + X(6, 4, K) + X(6, 5, K) <= 2;
	X(4, 5, K) + X(4, 7, K) + X(5, 4, K) + X(5, 7, K) + X(7, 4, K) + X(7, 5, K) <= 2;
	X(4, 6, K) + X(4, 7, K) + X(6, 4, K) + X(6, 7, K) + X(7, 4, K) + X(7, 6, K) <= 2;
	X(5, 6, K) + X(5, 7, K) + X(6, 5, K) + X(6, 7, K) + X(7, 5, K) + X(7, 6, K) <= 2;
	X(2, 3, K) + X(2, 4, K) + X(2, 5, K) + X(3, 2, K) + X(3, 4, K) + X(3, 5, K) + X(4, 2, K) + X(4, 3, K) + X(4, 5, K) + X(5, 2, K) + X(5, 3, K) + X(5, 4, K) <= 3;
	X(2, 3, K) + X(2, 4, K) + X(2, 6, K) + X(3, 2, K) + X(3, 4, K) + X(3, 6, K) + X(4, 2, K) + X(4, 3, K) + X(4, 6, K) + X(6, 2, K) + X(6, 3, K) + X(6, 4, K) <= 3;
	X(2, 3, K) + X(2, 4, K) + X(2, 7, K) + X(3, 2, K) + X(3, 4, K) + X(3, 7, K) + X(4, 2, K) + X(4, 3, K) + X(4, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 4, K) <= 3;
	X(2, 3, K) + X(2, 5, K) + X(2, 6, K) + X(3, 2, K) + X(3, 5, K) + X(3, 6, K) + X(5, 2, K) + X(5, 3, K) + X(5, 6, K) + X(6, 2, K) + X(6, 3, K) + X(6, 5, K) <= 3;
	X(2, 3, K) + X(2, 5, K) + X(2, 7, K) + X(3, 2, K) + X(3, 5, K) + X(3, 7, K) + X(5, 2, K) + X(5, 3, K) + X(5, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 5, K) <= 3;
	X(2, 3, K) + X(2, 6, K) + X(2, 7, K) + X(3, 2, K) + X(3, 6, K) + X(3, 7, K) + X(6, 2, K) + X(6, 3, K) + X(6, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 6, K) <= 3;
	X(2, 4, K) + X(2, 5, K) + X(2, 6, K) + X(4, 2, K) + X(4, 5, K) + X(4, 6, K) + X(5, 2, K) + X(5, 4, K) + X(5, 6, K) + X(6, 2, K) + X(6, 4, K) + X(6, 5, K) <= 3;
	X(2, 4, K) + X(2, 5, K) + X(2, 7, K) + X(4, 2, K) + X(4, 5, K) + X(4, 7, K) + X(5, 2, K) + X(5, 4, K) + X(5, 7, K) + X(7, 2, K) + X(7, 4, K) + X(7, 5, K) <= 3;
	X(2, 4, K) + X(2, 6, K) + X(2, 7, K) + X(4, 2, K) + X(4, 6, K) + X(4, 7, K) + X(6, 2, K) + X(6, 4, K) + X(6, 7, K) + X(7, 2, K) + X(7, 4, K) + X(7, 6, K) <= 3;
	X(2, 5, K) + X(2, 6, K) + X(2, 7, K) + X(5, 2, K) + X(5, 6, K) + X(5, 7, K) + X(6, 2, K) + X(6, 5, K) + X(6, 7, K) + X(7, 2, K) + X(7, 5, K) + X(7, 6, K) <= 3;
	X(3, 4, K) + X(3, 5, K) + X(3, 6, K) + X(4, 3, K) + X(4, 5, K) + X(4, 6, K) + X(5, 3, K) + X(5, 4, K) + X(5, 6, K) + X(6, 3, K) + X(6, 4, K) + X(6, 5, K) <= 3;
	X(3, 4, K) + X(3, 5, K) + X(3, 7, K) + X(4, 3, K) + X(4, 5, K) + X(4, 7, K) + X(5, 3, K) + X(5, 4, K) + X(5, 7, K) + X(7, 3, K) + X(7, 4, K) + X(7, 5, K) <= 3;
	X(3, 4, K) + X(3, 6, K) + X(3, 7, K) + X(4, 3, K) + X(4, 6, K) + X(4, 7, K) + X(6, 3, K) + X(6, 4, K) + X(6, 7, K) + X(7, 3, K) + X(7, 4, K) + X(7, 6, K) <= 3;
	X(3, 5, K) + X(3, 6, K) + X(3, 7, K) + X(5, 3, K) + X(5, 6, K) + X(5, 7, K) + X(6, 3, K) + X(6, 5, K) + X(6, 7, K) + X(7, 3, K) + X(7, 5, K) + X(7, 6, K) <= 3;
	X(4, 5, K) + X(4, 6, K) + X(4, 7, K) + X(5, 4, K) + X(5, 6, K) + X(5, 7, K) + X(6, 4, K) + X(6, 5, K) + X(6, 7, K) + X(7, 4, K) + X(7, 5, K) + X(7, 6, K) <= 3;
	X(2, 3, K) + X(2, 4, K) + X(2, 5, K) + X(2, 6, K) + X(3, 2, K) + X(3, 4, K) + X(3, 5, K) + X(3, 6, K) + X(4, 2, K) + X(4, 3, K) + X(4, 5, K) + X(4, 6, K) + X(5, 2, K) + X(5, 3, K) + X(5, 4, K) + X(5, 6, K) + X(6, 2, K) + X(6, 3, K) + X(6, 4, K) + X(6, 5, K) <= 4;
	X(2, 3, K) + X(2, 4, K) + X(2, 5, K) + X(2, 7, K) + X(3, 2, K) + X(3, 4, K) + X(3, 5, K) + X(3, 7, K) + X(4, 2, K) + X(4, 3, K) + X(4, 5, K) + X(4, 7, K) + X(5, 2, K) + X(5, 3, K) + X(5, 4, K) + X(5, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 4, K) + X(7, 5, K) <= 4;
	X(2, 3, K) + X(2, 4, K) + X(2, 6, K) + X(2, 7, K) + X(3, 2, K) + X(3, 4, K) + X(3, 6, K) + X(3, 7, K) + X(4, 2, K) + X(4, 3, K) + X(4, 6, K) + X(4, 7, K) + X(6, 2, K) + X(6, 3, K) + X(6, 4, K) + X(6, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 4, K) + X(7, 6, K) <= 4;
	X(2, 3, K) + X(2, 5, K) + X(2, 6, K) + X(2, 7, K) + X(3, 2, K) + X(3, 5, K) + X(3, 6, K) + X(3, 7, K) + X(5, 2, K) + X(5, 3, K) + X(5, 6, K) + X(5, 7, K) + X(6, 2, K) + X(6, 3, K) + X(6, 5, K) + X(6, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 5, K) + X(7, 6, K) <= 4;
	X(2, 4, K) + X(2, 5, K) + X(2, 6, K) + X(2, 7, K) + X(4, 2, K) + X(4, 5, K) + X(4, 6, K) + X(4, 7, K) + X(5, 2, K) + X(5, 4, K) + X(5, 6, K) + X(5, 7, K) + X(6, 2, K) + X(6, 4, K) + X(6, 5, K) + X(6, 7, K) + X(7, 2, K) + X(7, 4, K) + X(7, 5, K) + X(7, 6, K) <= 4;
	X(3, 4, K) + X(3, 5, K) + X(3, 6, K) + X(3, 7, K) + X(4, 3, K) + X(4, 5, K) + X(4, 6, K) + X(4, 7, K) + X(5, 3, K) + X(5, 4, K) + X(5, 6, K) + X(5, 7, K) + X(6, 3, K) + X(6, 4, K) + X(6, 5, K) + X(6, 7, K) + X(7, 3, K) + X(7, 4, K) + X(7, 5, K) + X(7, 6, K) <= 4;
	X(2, 3, K) + X(2, 4, K) + X(2, 5, K) + X(2, 6, K) + X(2, 7, K) + X(3, 2, K) + X(3, 4, K) + X(3, 5, K) + X(3, 6, K) + X(3, 7, K) + X(4, 2, K) + X(4, 3, K) + X(4, 5, K) + X(4, 6, K) + X(4, 7, K) + X(5, 2, K) + X(5, 3, K) + X(5, 4, K) + X(5, 6, K) + X(5, 7, K) + X(6, 2, K) + X(6, 3, K) + X(6, 4, K) + X(6, 5, K) + X(6, 7, K) + X(7, 2, K) + X(7, 3, K) + X(7, 4, K) + X(7, 5, K) + X(7, 6, K) <= 5;

);

! kendala biner untuk variabel ;

@FOR(KENDARAAN(K) : 
	@BIN(Z(K));
	@FOR(CUSTOMER(I) :
		@BIN(Y(I, K));
		@FOR(CUSTOMER(J) :
			@BIN(X(I, J, K));
		);
	);
);