8
I PENDAHULUAN 1.1 Latar Belakang Pendistribusian suatu barang merupakan persoalan yang sering dijumpai baik oleh pemerintah maupun oleh produsen. Dalam pelaksanaannya sering kali dihadapkan pada berbagai masalah seperti efisiensi biaya, efisiensi waktu ataupun masalah efektifitas kendaraan. Contoh pendistribusian barang adalah pengangkutan sampah oleh Dinas Kebersihan, pendistribusian produk perusahaan kepada agen, pengambilan surat di kotak pos oleh PT Pos Indonesia dan mas ih banyak lagi. Contoh-contoh tersebut termasuk dalam masalah pengambilan dan pengiriman (pick up and delivery problem / PDP). Masalah pengambilan dan pengiriman dengan kendala waktu (pick up and delivery problem with time windows/PDPTW) merupakan pengembangan dari PDP. Kendala waktu dalam PDPTW diartikan sebagai selang waktu untuk menunggu pengambilan atau pengiriman di suatu tempat.
Masalah PDP dan PDPTW telah banyak dibahas dan dipelajari, di antaranya oleh Mitrofic-Minic (1998) yang membahas metode heuristik untuk menyelesaikan masalah PDPTW, Bruggen et al. (1993) membahas PDPTW dengan satu depot, Dumas et al. (1991) membahas penyelesaian PDPTW dengan menggunakan teknik pembangkitan kolom yang dipandang sebagai masalah path terpendek serta M. Sol & M.W.P. Savelsberg (1995) yang membahas PDP secara luas. Tulisan ini merupakan rekonstruksi dari tulisan M. Sol & M.W.P. Savelsberg (1994) yang berjudul “A Branch-and-Price Algorithm for the Pickup and Delivery Problem with Time Windows”. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah mempelajari penyelesaian masalah pengambilan dan pengiriman berkendala waktu dengan menggunakan teknik pembangkitan kolom .
II LANDASAN TEORI Beberapa konsep yang dibutuhkan dalam masalah pengambilan dan pengiriman dengan kendala waktu adalah sebagai berikut: 2.1 Graf Definisi 1 (Graf) Suatu graf adalah pasangan terurut (V,E) dengan V himpunan takkosong dan hingga dan E adalah himpunan pasangan takterurut yang menghubungkan elem en-elemen V dan dinotasikan dengan G = (V , E ) . Elemen V dinamakan simpul (node), dan elemen E dinamakan sisi (edge), dinotasikan sebagai {i, j } , yaitu sisi yang menghubungkan simpul i dengan simpul j, dengan i , j ∈V . (Foulds, 1992) Ilustrasi graf dapat dilihat pada Contoh 1 berikut: Contoh 1 v5 v6 v1 G:
v2
v3
v4
Gambar 1 Graf G = (V, E).
Pada Gambar 1, V = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } dan E = {{v1 , v 2 },{v1 , v 6 }, {v 2 , v 3 },{v 3 , v 6 },
{v3 , v4 }, {v5 , v6 },{v4 , v5 }}.
Definisi 2 (Walk) Suatu walk pada graf G = (V , E ) adalah suatu barisan simpul dan sisi dari G dengan bentuk: v1 , {v1 , v2 }, v2 , {v2 , v3 },..., {vn −1 , vn }, vn , atau dengan ringkas : v1 , v 2 ,..., v n atau v1 , v2 ,..., vn . Walk tersebut menghubungkan simpul v1 dengan v n . (Foulds, 1992) ditulis
Definisi 3 (Closed Walk, Cycle) Suatu walk v 1 , v 2 ,..., v n pada suatu graf G dikatakan tertutup (closed walk) jika v1 = vn . Suatu walk tertutup yang mengandung setidaknya tiga simpul dan semua simpulnya berbeda disebut cycle. (Foulds, 1992) Berikut ini diberikan ilustrasi dari walk tertutup dan cycle. Salah satu contoh walk
9
tertutup pada graf G dalam Contoh 1 adalah v1 ,v 6 , v1 , v 2 , v1 , sedangkan v1 , v2 , v3 , v6 , v1 adalah salah satu contoh cycle. Definisi 4 (Digraf) Digraf (directed graf/graf berarah) adalah pasangan terurut (V, A) dengan V adalah himpunan takkosong dan hingga, dan A adalah himpunan pasangan terurut dari elemenelemen di V dan dinotasikan sebagai D = (V , A) . Elemen dari A disebut sisi berarah (arc) dan dituliskan sebagai (i, j ) dengan i , j ∈V . (Foulds, 1992) Contoh berikut merupakan ilustrasi digraf. Contoh 2 D: v1
v6
v1-v2-v3-v6-v1, sedangkan cycle v 1, v 6, v 3,v 2,v 1 pada digraf D bukan merupakan cycle berarah. Definisi 7 (Graf Berbobot) Suatu graf G = (V , E ) atau digraf D = (V , A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau ϑ : A → ℜ (dengan ℜ adalah himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau elemen A. (Foulds, 1992) 2.2 Pemrograman Linear Pemrograman linear adalah kegiatan merencanakan untuk mendapatkan hasil yang optimal. Model pemrograman linear (P L) meliputi pengoptimuman suatu fungsi linear terhadap kendala linear . (Hillier & Lieberman, 1990)
v5 Pada tulisan ini, suatu P L mempunyai bentuk standar seperti yang didefinisikan sebagai berikut:
v2
v3
v4
Gambar 2 Digraf D = (V , A) . Pada Gambar 2, digraf D memiliki V = {v1 ,v2 , v3 , v4 , v5 , v6 } dan
A = {(v1 , v2 ), (v6 , v1 ),(v2 , v3 ), (v3 , v6 ), (v3 , v4 ) (v5 , v 6 ), (v 4 , v 5 )} .
Definisi 5 (Walk berarah) Suatu walk berarah pada digraf D = (V , A) adalah suatu barisan simpul dan sisi dari G dengan bentuk: (v1 − (v1 , v2 ) − v2 − (v2 , v3 ) − ... − (vn −1 ,vn ) − vn ) atau ditulis dengan ringkas: (v1 − v 2 − ... − v n ) atau v1-v 2-…-vn. Walk tersebut menghubungkan simpul v1 dengan v n . (Foulds, 1992) Definisi 6 (Cycle berarah) Suatu walk berarah
(v1 − v 2 − ... − v n )
dengan v1 = v n dan mempunyai setidaknya tiga simpul berbeda disebut sebagai cycle berarah. (Foulds, 1992) Berikut ini diberikan ilustrasi mengenai cycle berarah. Salah satu contoh cycle berarah pada digraf D dalam Contoh 2 adalah cycle
Defi nisi 8 (Bentuk Standar Suatu PL) Suatu pemrograman linear didefinisikan mempunyai bentuk standar: Minimumkan z = cT x Ax = b terhadap (1) x ≥0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga sebagai matriks kendala. (Nash & Sofer, 1996) 2.2.1 Solusi S uatu Pemrograman linear Untuk menyelesaikan suatu masalah pemrograman linear (PL), metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum. Metode ini mulai dikembangkan oleh Dantzig tahun 1947. Sejak perkembangannya, metode ini adalah metode yang paling umum digunakan untuk menyelesaikan PL, yaitu berupa metode iteratif untuk menyelesaikan masalah PL dalam bentuk standar. Pada Pemrograman Linear (1), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi P L (1). Misalkan matriks A dapat dinyatakan sebagai A = (B N), dengan B adalah matriks taksingular berukuran m × m yang merupakan matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa
10
koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk P L. Misalkan x dapat dinyatakan sebagai x vektor x = B , dengan x B adalah vektor xN variabel basis dan xN adalah vektor variabel nonbasis. Maka A x = b dapat dinyatakan sebagai x Ax = (B N ) B xN (2) = ? x B + Nx N = b . Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai: (3) x B = B−1 b − B−1N x N . Definisi 9 (Solusi Basis) Vektor x disebut solusi basis dari suatu pemrograman linear jika x memenuhi kendala dari PL dan kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari x adalah bebas linear. (Nash & Sofer, 1996) Definisi 10 (Solusi Basis Fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x ≥ 0. (4) (Nash & Sofer, 1996) Ilustrasi solusi basis dan solusi basis fisibel dapat dilihat dalam contoh berikut: Contoh 3 Misalkan diberikan pemrograman linear berikut: Minimumkan z = − x1 − 2x 2 terhadap −2 x1 + x 2 + x 3 = 2
− x1 + 2 x2 + x4 = 7
(5)
x1 + x 5 = 3
x1 , x2 , x3 , x4 , x5 ≥ 0 Dari pemrograman linear tersebut didapatkan: 1 0 0 − 2 1 2 A = −1 2 0 1 0 , b = 7 1 3 0 0 0 1 Misalkan dipilih
x B = (x3
x4
x5 )T dan x N = (x1
x2 )T
maka matriks basis
1 0 0 B = 0 1 0 0 0 1 Dengan menggunakan matriks basis tersebut, diperoleh x B = B −1b = (2 7 3)T , x N = (0 0 )T . (6) Solusi (6) merupakan solusi basis, karena solusi tersebut memenuhi kendala pada P L (5) dan kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari (6) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (6) juga merupakan solusi basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol._ PL (1) dapat dinyatakan dalam xB dan xN sebagai berikut: Minimumkan z = cBT x B + cN T x N terhadap B x B + Nx N = b x ≥0 dengan c B adalah koefisien variabel basis pada fungsi objektif, c N adalah koefisien variabel nonbasis pada fungsi objektif. Jika P ersamaan (3) disubstitusikan ke fungsi objektif z = cBT x B + c N T x N maka akan didapat:
(
)
z = c B T B − 1b − B − 1Nx N + c N T x N −1
(
)
z = cB B b + c N − c BT B − 1N x N . T
T
( ) z = yT b + (cN T − yT N )x N .
−1 T
Jika didefinisikan y = c B B = B −T c B maka z dapat dinyatakan dalam y: T
(7) Vektor y disebut vektor pengali simpleks (simplex multiplier). Untuk suatu solusi basis, x N = 0 dan
x B = bˆ = B −1b , maka zˆ = c B T B − 1b . Notasi zˆ adalah notasi untuk z optimal. Koefisien cˆ j disebut biaya tereduksi (reduced cost) dari x j dengan
(
cˆ j adalah
)
elemen dari vektor cˆ N T = cN T − cBT B − 1N . Biaya tereduksi adalah penambahan nilai fungsi objektif jika suatu variabel nonbasis dijadikan variabel basis (artinya menjadi solusi taknol) pada suatu pemrograman linear.
11
2.2.2 Penyelesaian Pemrograman Linear dengan Algoritme S impleks Solusi suatu pemrograman linear dapat diketahui optimal atau tidak untuk P L tersebut melalui algoritme sebagai berikut: • Tes Keoptimalan
Vektor y = c B T B − 1 dihitung, kemudian dapat dihitung pula nilai biaya tereduksi
(
)
cˆN T = cN T − yT b . Jika cˆ N T ≥ 0 maka solusi yang diperoleh adalah solusi optimal. Jika cˆ N T < 0 maka variabel xt yang memenuhi cˆt < 0 dipilih sebagai variabelmasuk, yaitu variabel xt yang akan masuk ke dalam basis. • Langkah tertentu (t) Kolom Aˆ t = B −1 At , yaitu kolom koefisien kendala yang berhubungan dengan variabel-masuk ke t dihitung kemudian ditentukan indeks s pada kolom kendala yang berhubungan dengan variabel-masuk yang memenuhi min bˆi bˆs = : a i ,t > 0 . (8) a s, t 1 ≤ i ≤ m a i, t Pemilihan indeks dengan cara tersebut disebut dengan uji nisbah minimum (minimum ratio test). Variabel yang menjadi variabel-keluar (variabel yang akan keluar dari basis, tergantikan oleh variabel -masuk) dan pivot entry adalah variabel yang berhubungan dengan aˆ s ,t . Jika aˆ i ,t ≤ 0 , (1 ≤ i ≤ m) untuk semua i, maka masalah P L disebut masalah takterbatas (unbounded). • Pivot Matriks basis B dan vektor basis x B diperbaharui dan kemudian kembali ke tes keoptimalan. Berikut ini diberikan contoh penggu naan algoritme simpleks: Contoh 4 Misalkan diberikan PL(5) dalam Contoh 3. Dengan menggunakan algoritme simpleks akan diperoleh solusi x1 = 3, x2 = 5, x3 = 3, x4 = x5 = 0 dengan z = - 13 (lihat Lampiran 1). _ 2.3 Masalah Dual Setiap masalah pemrograman linear memiliki padanan, yaitu masalah lain yang disebut pemrograman linear dual. Pemrograman linearnya sendiri disebut
sebagai masalah primal. Misalkan diberikan masalah primal: Minimumkan z = cT x terhadap Ax ≥ b (9) x≥0 Maka masalah dual dari (9) adalah Maksimumkan
w = bT y
AT y ≤ c y≥0 Jika masalah primal memiliki n variabel dan m kendala, maka masalah dual akan memiliki m variabel dan n kendala. Koefisien fungsi objektif masalah primal merupakan nilai sisi kanan pada masalah dual, begitu pula sebaliknya. Jika masalah primal adalah masalah minimisasi maka masalah dual merupakan masalah maksimisasi. Solusi optimal dari masalah dual merupakan pengali simpleks pada masalah primal. Pada kondisi optimal, solusi dari masalah dual dan masalah primal akan menghasilkan nilai fungsi objektif yang sama. Hal ini dibuktikan dalam teorema dualitas kuat. Akibat dari teorema dualitas lemah digunakan untuk membuktikan teorema dualitas kuat. terhadap
Teorema 1 (Teorema Dualitas Lemah) Misalkan diberikan pemrograman linear primal dan masalah dualnya. Misalkan x adalah solusi fisibel untuk masalah primal dalam bentuk standarnya dan misalkan y solusi fisibel untuk masalah dual, maka nilai fungsi objektif dari masalah primal selalu lebih besar atau sama dengan nilai fungsi objektif dari masalah dual. Bukti : lihat (Nash & Sofer, 1996). Akibat 1 Jika x adalah solusi fisibel untuk masalah primal, y adalah solusi fisibel untuk masalah dual, dan b T y = c T x , maka x dan y adalah solusi optimal berturut-turut untuk masalah primal dan dual. Teorema 2 (Teorema Dualitas Kuat) Misalkan diberikan pemrograman linear primal dan masalah dualnya. Jika salah satu dari masalah primal atau masalah dual tersebut memiliki solusi optimal, maka masalah lainnya juga memiliki solusi optimal dan nilai fungsi objektif optimalnya adalah sama.
12
Bukti : Misalkan diasumsikan bahwa masalah primal dalam bentuk standar dan mempunyai solusi x yang merupakan solusi basis fisibel optimal. Misalkan x dapat dinyatakan sebagai x vektor x = B , dengan xB adalah vektor xN variabel basis dan xN adalah vektor variabel nonbasis. Selain itu, seperti telah dijelaskan sebelumnya matriks A dapat dinyatakan sebagai A = (B N ) dan vektor koefisien pada fungsi objektif c dapat dinyatakan c sebagai c = B . Karena B adalah matriks cN taksingular, maka B memiliki invers sehingga
Bukti dari teorema dualitas kuat menghasilkan solusi optimal dual. Misalkan x c x = B , A = (B N ) , dan c = B x N cN maka nilai optimal dari variabel dual diberikan
xB dapat dinyatakan sebagai x B = B − 1b . Dari sebelumnya diketahui pula, jika x optimal maka biaya tereduksinya adalah
Contoh 5 Misalkan diberikan pemrograman linear primal sebagai berikut: Minimumkan z = 51x1 + 27 x2 + 93x3 + 74 x4 + 55 x 5 terhadap x1 + x2 ≥ 1
c TN − c TB B − 1N ≥ 0 atau (*) cTB B − 1N ≤ cTN Misalkan y adalah vektor dari pengali simpleks yang berhubungan dengan solusi basis fisibel, dengan y = B −T c B atau
yT = cTB B − 1 . Akan ditunjukkan bahwa: 1 Nilai dari fungsi objektif masalah primal 2
dan dual adalah sama, yaitu bT y = cT x . y adalah optimal untuk masalah dual.
Bukti: 1 Sebelumnya akan diperiksa dahulu kefisibelan dari y:
y T A = c TB B −1 (B N )
(
= cTB
) (
terlebih
)
cTB B −1 N ≤ cTB cTN dari (*)
= cT
Sehingga AT y ≤ c dan y fisibel untuk masalah dual, kemudian dihitung nilai objektif untuk masalah primal (z) dan dual (w):
z = c T x = c TB x B = c TB B − 1b
w = bT y = y T b = cTBB −1b = z. Jadi y adalah fisibel untuk masalah dual dan nilai fungsi objektif solusi optimal dari masalah primal dan dual mempunyai nilai yang sama. 2
Karena b T y = cT x maka y adalah solusi optimal untuk masalah dual (dari Akibat 1)._
oleh vektor pengali simpleks y = B −T c B . Dari bukti teorema dualitas kuat terlihat bahwa kondisi primal optimal
cTN − cTB B − 1N ≥ 0 adalah ekivalen dengan kondisi fisibel dual A T y ≤ c atau c − A T y ≥ 0 . Jadi vektor dari biaya tereduksi cˆ adalah vektor variabel slack dual cˆ = c − AT y.
x1 + x2 + x3 + x4 ≥ 1
x1 + x5 ≥ 1 x2 + x3 ≥ 1 x3 + x 4 + x5 ≥ 1 x4 ≥ 1
xi ≥ 0 , untuk i = {1, 2,3, 4,5} . Masalah dual dari masalah tersebut adalah sebagai berikut: Maksimumkan w = y1 + y 2 + y3 + y4 + y5 + y6 terhadap y1 + y 2 + y3 ≤ 51 y1 + y 2 + y 4 ≤ 27
y2 + y 4 + y 5 ≤ 93 y2 + y5 + y6 ≤ 74 y3 + y5 ≤ 55 y i ≥ 0 , untuk i = {1, 2,3, 4,5,6}. Dengan menggunakan LINDO 6.1, diperoleh solusi dari masalah primal sebagai berikut: x1 = x 2 = x 4 = 1, x 3 = x 5 = 0 dengan nilai fungsi objektifnya z = 152 (lihat Lampiran 2). Nilai pengali simpleks untuk masing-masing kendala adalah sebagai berikut: y1 = y2 = 0, y3 = 51, y 4 = 27 , y5 = 4 , y6 = 70 dengan yi adalah nilai pengali simpleks kendala ke-i.
13
Solusi dari masalah dual tersebut juga dapat dicari dengan menggunakan LINDO 6.1 yang menghasilkan solusi: y1 = y 2 = y 5 = 0 , y 3 = 51 , y 4 = 27 , y 6 = 74 dengan nilai fungsi objektif w = 152 (lihat Lampiran 2). Dari penghitungan tersebut, terlihat bahwa fungsi objektif dar i masalah primal dan dual mempunyai nilai yang sama seperti dinyatakan dalam Teorema 2. _ 2.4 Pemrograman Linear Bilangan Bulat Model pemrograman linear bilangan bulat (Integer Linear Programming/ILP) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa bilangan bulat, maka masalah tersebut disebut ILP-murni. Jika hanya sebagian yang harus bilangan bulat maka disebut ILP-campuran. ILP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 I LP.
Partisi dari I di antaranya adalah
karena untuk himpunan J = {3,5} memenuhi: Υ Pj = I dan j∈ J *
untuk j , k ∈ J * , j ≠ k ⇒ P j ∩ Pk =
Model yang digunakan pada tulisan ini yang berkaitan dengan masalah ILP adalah model masalah pemartisian himpunan. 2.5 Masalah Pemartisian Himpunan Definisi 12 (Partisi) Misalkan diberikan dua himpunan, yaitu I = {1,2,..., m} dan P = {P1 , P2 ,..., Pn } dengan P j adalah suatu himpunan bagian dari I, j ∈ J = {1,2,..., n} . Himpunan Pj , j ∈ J * ⊆ J adalah partisi dari I jika: Υ Pj = I dan j∈ J *
untuk j , k ∈ J * , j ≠ k ⇒ P j ∩ Pk = ø. (Garfinkel & Nemhauser, 1972) Ilustrasi dari suatu partisi dapat dilihat pada Contoh 6 berikut: Contoh 6 Misalkan diberikan himpunan I = {1,2,3,4,5,6} dan kelas-kelas himpunan P1 = {1, 6} , P2 = {3,4} , P3 = {1,4,6}, P4 = {2} ,
P5 = {2,3,5}.
ø. _
Masalah pemartisian himpunan (set partitioning problem/SPP) adalah masalah menentukan partisi dari himpunan I dengan biaya minimum. Untuk mendapatkan partisi tersebut, misalkan didefinisikan variabel 0-1 sebagai berikut: 1, jika Pj termasuk dalam partisi xj = 0, selainnya Bentuk umum SPP: n
Minimumkan Definisi 11 (Pemrograman Linear Relaksasi) PL-relaksasi dari suatu ILP merupakan pemrograman linear yang diperoleh dari ILP tersebut dengan menghilangkan kendala bilangan bulat atau kendala 0-1 pada variabelnya. (Winston, 1995)
{P3 , P4 } ,
*
∑ cjx j j =1
n
terhadap
∑ A( j )x j = 1 j =1
x j = 0 atau 1 dengan cj adalah biaya Pj, A(j) adalah matriks koefisien kendala, dan 1 adalah vektor dengan dimensi n dengan semua komponennya sama dengan 1. Model ini memiliki beberapa sifat penting, yaitu: Sifat 1 Masalah pada model memiliki kendala berupa persamaan. Sifat 2 Nilai sisi kanan semua kendala adalah 1. Sifat 3 Semua elemen matriks koefisien A(j) adalah 0 atau 1. Contoh 7 (Masalah pemartisian himpunan) Misalkan diberikan himpunan I beserta kelas -kelas P seperti pada Contoh 6. Misalkan diketahui biaya dari masing-masing kelas Pj , yaitu cj , dengan c1 = 15, c2 = 10 , c3 = 19 , c4 = 18, c5 = 17 . Diinginkan himpunan dari Pj yang dapat memartisi I dengan biaya minimum. Masalah tersebut dapat dimodelkan sebagai masalah pemartisian himpunan. Misalkan didefinisikan variabel 0-1 sebagai berikut: 1, jika Pj termasuk dalam partisi xj
= 0, selainnya
14
1, jika elemen ke-j di I merupakan elemen Pj , dengan j = 1,2 ,...,5 A(j) = 0, selainnya Masalah tersebut dapat dimodelkan sebagai SPP berikut: Minimumkan 15 x1 + 10 x 2 + 19 x3 + 18 x4 + 17 x5 terhadap x1 + x 3 = 1 (elemen 1)
x4 + x5 = 1
(elemen 2)
x2 + x5 = 1
(elemen 3)
x2 + x3 = 1 (elemen 4) (elemen 5) x5 = 1 (elemen 6) x1 + x3 = 1 x j = 0 atau 1, untuk j = {1, 2, 3, 4, 5} . Dengan mengunakan LINDO 6.1 diperoleh solusi untuk masalah SPP sebagai berikut: x1 = x2 = x4 = 0, x3 = x5 = 1 , dan nilai fungsi objektif sebesar 36. Jadi partisi dari I = {1, 2,3,4,5,6} dengan biaya minimum adalah P3 = {1,4,6} dan P5 = {2,3,5}.
III DESKRIPSI DAN FORMULASI MASALAH Dalam masalah pengambilan dan pengiriman (PDP) sejumlah rute harus dikonstruksi guna memenuhi semua permintaan transportasi (transportation request/TR). Permintaan transportasi dapat diartikan sebagai suatu permintaan pengiriman barang yang harus dibawa secara langsung dari lokasi pengambilan barang (tempat asal) ke lokasi pengiriman (tempat tujuan). Setiap permintaan transportasi memiliki kuantitas barang yang dibawa oleh suatu kendaraan. Kuantitas barang yang dibawa ke tempat tujuan belum tentu semuanya diturunkan pada tempat tujuan. Bisa jadi hanya sebagian barang yang diturunkan atau bahkan tidak diturunkan sama sekali. Barang yang tidak diturunkan kemudian dikirimkan ke tempat tujuan selanjutnya. Bisa jadi dalam pengiriman tersebut ditambah dengan barang yang diangkut pada tempat penurunan barang. Kuantitas barang dalam permintaan transportasi terkadang tidak selalu diketahui pada masalah pengambilan dan pengiriman. Kuantitas tersebut dapat dicari melalui kuantitas suatu barang yang harus diangkut atau diturunkan pada suatu tempat Armada kendaraan sangat dibutuhkan dalam PDP. Armada kendaraan dapat beroperasi dalam berbagai rute. Suatu armada dapat memiliki berbagai macam tipe kendaraan. Setiap tipe kendaraan memiliki depot dan kapasitas pengangkutan barang. Depot merupakan tempat di mana kendaraan tersebut diberangkatkan dan kembali setelah perjalanan usai. Masalah pengambilan dan pengiriman dengan kendala waktu (pick up and delivery problem with time windows/PDPTW) merupakan pengembangan dari PDP, dengan
kendala waktu diartikan sebagai selang waktu untuk menunggu pengambilan atau pengiriman di suatu tempat. Sebagai ilustrasi pada pengambilan surat oleh PT Pos Indonesia. Misalkan saja waktu pengambilan surat di suatu kotak pos adalah tepat pukul 9.00. Sering kali dalam pelaksanaannya dihadapkan pada berbagai masalah perjalanan, sehingga diperkirakan kendaraan tersebut akan tiba sekitar pukul 8.50 sampai pukul 9.10. Perkiraan waktu tersebut digunakan sebagai kendala waktu pada PDPTW. Dalam masalah pengambilan dan pengiriman dengan kendala waktu, setiap permintaan transportasi memiliki kendala waktu yang ada pada saat pengambilan maupun pengiriman. Hal ini berarti setiap kendaraan harus mengunjungi setiap tempat sesuai dengan kendala waktu yang ada. Di depot, s etiap tipe kendaraan dalam armada juga memiliki kendala waktu, sehingga kendaraan tersebut berangkat dan pulang ke depot sesuai dengan waktu yang tersedia. Jika rute-rute dalam PDPTW yang memenuhi permintaan transportasi telah dikonstruksi, maka harus dicari bagaimana cara memenuhi semua permintaan transportasi tersebut dengan biaya minimum. Beberapa asumsi digunakan dalam model PDPTW ini. Asumsi tersebut adalah: 1 Barang yang diambil dan dikirim merupakan barang yang homogen. 2 Barang tersebut dikirimkan oleh satu kendaraan dari lokasi pengambilan ke lokasi pengiriman tanpa adanya biaya pengangkutan di tengah lokasi. 3 Waktu yang diperlukan untuk bongkar muat barang pada lokasi pengambilan dan lokasi pengiriman dapat dengan mudah
