3/7/2017
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.
1
3/7/2017
The Shortest Path Problem • In the shortest path problem, There are n nodes beginning with the start node 1 and ending with the terminal node n. • It differs from the traveling salesman problem in two ways: • In the shortest path problem, • (1) not every node need to be included on the selected path, and • (2) we do not return to the start node
The Shortest Path Problem • Example 1:
Fairway Van Lines Company is a nationwide household mover in U.S. One of its current jobs is to move goods from a house in Seattle (in Washington) to El Paso (in Texas).
2
3/7/2017
The Shortest Path Problem Node 1 2 1 3 1 4 2 7 2 8 3 4 3 5 4 7 5 6 5 10 6 7 7 8
Node City Seattle Seattle Seattle Butte Butte Portland Portland Boise Sacramento Sacramento Reno Salt Lake City
City Butte Portland Boise Salt Lake City Cheyenne Boise Sacramento Salt Lake City Reno Bakersfield Salt Lake City Cheyenne
Distance (km) 599 432 497 420 691 432 602 345 138 291 526 440
7 7 8 9
Salt Lake City Salt Lake City Cheyenne Denver
Las Vegas Albuquerque Denver Albuquerque
432 621
11 12 9 12
102 452
The Shortest Path Problem Node 10 11 10 13 11 14 11 15 11 16 12 15 12 19 13 14 13 16 13 17 14 15 16 18 16 19 17 18 18 19
Node City Bakersfield Bakersfield Las Vegas Las Vegas Las Vegas Albuquerque Albuquerque Los Angeles Los Angeles Los Angeles Barstow Phoenix Phoenix San Diego Tucson
City Las Vegas Los Angeles Barstow Kingman Phoenix Kingman El Paso Barstow Phoenix San Diego Kingman Tucson El Paso Tucson El Paso
Distance (km) 280 114 155 108 290 469 268 138 386 118 207 116 403 425 314
3
3/7/2017
The Shortest Path Problem
Example 2 : What is the shortest route from Point A to Point B ?
A•
•B
What if some roads are specified as 1-way only ?
4
3/7/2017
A Graph-model of the Shortest Route problem Given a directed, weighted graph, G(V, E), start node s, end node v, Find the minimum total weight path from s to v kt
hh
4
4 tko
1 2
6
tkw
3
3
2 4
ust 7
pe 3 ch
Legend: Edge direct road weight road length nodes road intersections ust = HKUST tko = Tseung Kwan O kt = Kowloon Tong ch = Choi Hung tkw = To Kwa Wan pe = Prince Edward hh = Hung Hom
Finding shortest paths: Dijkstra’s method Strategy: Find shortest path to one node; [all other nodes remain] Find shortest path to one of the remaining nodes; Repeat … until done How? Upper bound on distance from s to u: d[u] If Node k has the MIN upper bound d[k] is the shortest distance from s to k Select node k to update upper bounds on remaining nodes Key concept: Relaxation
5
3/7/2017
Relaxation.. Two cases of relaxation x 10
x
y
4
18
12
Relax( x, y) x 10
4
y
4 10
Relax( x, y) x
y 14
y
4
12
10
cyan edge => current immediate predecessor of y is x
Dijkstra’s method.. d[vi] = for each vertex; d[s] = 0; Make two lists: S = { }; Q = V Find the node, u, in Q with minimum d[u] Remove u from Q, and add u to S For each edge (u, v), Relax (u, v); update IP(v) no
Q={}
yes
DONE
6
3/7/2017
Dijkstra’s method, Example
kt 4
tko
4
hh
1 2
6
tkw
3
3
2 4
ust 0
pe
7 ch
3
Find shortest path from ust to hh
Kasus Shortes Route; solusi dengan Win Qsb Perusahaan “Q” akan menentukan rute terpendek perjalanan truk yang mengangkut barang dari kota A ke kota M, dengan gambaran jaringan yang menghubungkan antar kota dan jarak antar kota adalah sebagai berikut :
7
3/7/2017
Solusi dengan Software Win Qsb RUTE TERPENDEK 1) Eksekusi Software Win Qsb, kemudian klik : Network Modelling – File – New Problem, maka akan tampil form kemudian isi form sebagai berikut – ok :
2) Klik : Edit – Node Names, kemudian isi sbb . :
3) Isi matriks di bawah ini :
8
3/7/2017
4) Klik solve and Analyze – solve :
5) Klik Result : Graphics Solution
A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.
9
3/7/2017
The Minimal Spanning Tree Problem • A spanning tree connects all of the n nodes of a network to each other. • Minimal spanning tree is the one that connects all the nodes in minimal total distance. • A minimal spanning tree approach is typically suitable for problems for which redundancy is expensive.
The Minimal Spanning Tree Problem • For example, consider the Cable Television Connections. It is desired to reach all the houses in a minimal cost of wiring. • Or, consider the design of a mass transportation system. • We want the busses to visit all the locations, but we should connect the locations by employing the minimal traveling distance.
10
3/7/2017
Contoh MST; solusi dengan Win Qsb PDAM Kab. Bandung telah memutuskan untuk membangun jaringan pipa air minum yang menghubungkan 10 kecamatan yang terhubung satu sama lain dengan biaya minimum. Angka pada busur adalah biaya instalasi (dalam jutaan rupiah)
• In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum. • The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in the network, as stated in the max-flow min-cut theorem.
11
3/7/2017
• Maximum flow problems consist of a single starting node, that is the source, from which all flow emanates, and a terminal node, called the sink, into which the flow is deposited. • The flow travels on the arcs that are between the source and sink. • Each arc has a capacity that cannot be exceeded. • The arc capacities do not have to be the same in each direction.
• At each of these intermediate nodes, the flow entering into the node must equal the flow leaving out of the node. • The capacity of flow between nodes i and j is shown by two values: Cij and Cji. • Cij corresponds to the flow from node i to node j. • And, Cji corresponds to the flow from node j to node i. • The goal is to find the maximum total flow possible out of node 1 that can flow into node n without exceeding the capacities on any arc.
12
3/7/2017
• Example: The United Chemical Company is a small producer of pesticides and lawn care products. One production area contains a huge drum that holds up to 100,000 gallons of a poisonous chemical used in making various insecticides. The drum is routinely filled to a level somewhere between 80,000 and 90,000 gallons.
• The flow of the chemical is then regulated through a series of pipes to production areas, where the chemical is mixed with other ingredients. • There is a final section called disposal area, where the waste is deposited into a large “safe tub”. • It is then collected from the safe tub and disposed of in a manner consistent with federal regulations.
13
3/7/2017
• The following table gives the volume that can flow through each pipe. • Capacities of pipes (in 1000 gallons/minute):
The Maximum Flow Problem
14
3/7/2017
• The plan must determine which valves to open and shut, as well as provide an estimated time for total discharge of the poisonous chemicals into the secure waste area. • The flow is possible in either direction between nodes 2 and 3, 3 and 6, 4 and 6, and 5 and 6. But, Flow is restricted to one direction for all other arcs. • The problem can easily be formulated as a linear program.
• Xij represent the amount of flow between nodes i and j. (in 1000 gallons per minute). The Objective is: Maximize X12 + X13 • The Constraints are as follows: • The total flow out of source node 1 must equal the flow into terminal node 7: X12 + X13 = X47 + X57 + X67
15
3/7/2017
• For nodes 2,3,4,5, and 6, The total flow into the node must equal the total flow out of the node: • Node 2: X12 + X32 = X23 + X24 + X26 • Node 3: X13 + X23 + X63 =X32 + X35 + X36 • Node 4: X24 + X64 = X46 + X47 • Node 5: X35 + X65 = X56 + X57 • Node 6: X26 + X36 + X46 + X56=X63 + X64 + X65 + X67
• The flows cannot exceed the arc capacities: • X12 10; X13 10; X23 1; X24 8; X26 6; X32 1; • X35 12; X36 4; X46 3; X47 7; X56 2; X57 8; • X63 4; X64 3; X65 2; X67 2. • The flows can not be negative: • All Xij 0.
16
3/7/2017
• The problem was solved by using the Network Modeling option of WINQSB. • The result is as follows: From Node 1 to Node 2, The net flow is 7,000 gallons per minute. From Node 1 to Node 3, The net flow is 10,000 gallons per minute. From Node 2 to Node 4, The net flow is 7,000 gallons per minute. From Node 3 to Node 5, The net flow is 8,000 gallons per minute. From Node 3 to Node 6, The net flow is 2,000 gallons per minute. From Node 4 to Node 7, The net flow is 7,000 gallons per minute. From Node 5 to Node 7, The net flow is 8,000 gallons per minute. From Node 6 to Node 7, The net flow is 2,000 gallons per minute.
• The maximum total net flow From Node 1 to Node 7, is 17,000 gallons per minute. • If the drum is full with 100,000 gallons, it will take about 100,000 / 17,000 = 5.88 minutes to empty the entire contents into the safe tub in an emergency situation.
Bagaimana solusi dengan Win Qsb
17
3/7/2017
The TSP involves finding the minimum traveling cost for visiting a fixed set of customers. The vehicle must visit each customer exactly once and return to its point of origin also called depot. The objective function is the total cost of the tour.
Traveling Salesman Problem 3
2
3
4
2
2 3
2
1
4 4
1
5
3
5
The total number of solutions is (n-1)! /2 if the distances are symmetric. For example, if there are 50 customers to visit, the total number of solutions is 49!/2=3.04x1062.
18
3/7/2017
Traveling Salesman Problem Solution
3
2
3
4
2
2 3
2
4
1 4
1
5
3
5
If the depot is located at node 1, then the optimal tour is 1-5-2-3-4-1 with total cost equal to 11.
Traveling Salesman Problem Mathematical Programming Inputs:
n = number of customers including the depot cij = cost of traveling from customer i to j
Decision variables:
1 if the vehicle travels from customer i to j. xij 0 otherwise
19
3/7/2017
Traveling Salesman Problem n
n
min cij xij i 1 j 1 n
x
s.t.
i 1 n
x j 1
ij
1
for all j
(1) (2)
ij
1
for all i
xij 0,1
for all i, j
Constraints (1) and (2) ensure that each customer is visited exactly once.
Traveling Salesman Problem 3
2
3
4
2
2 3
2
1
4 4
1
5
3
5
minimize 2x12+3x13+2x14+3x15+3x23+4x24+...+5x45 s.t.
x12+x13+x14+x15 = 1 x21+x31+x41+x51 = 1 ... ...
for node 1 for node 1
20
3/7/2017
Traveling Salesman Problem 2
3
4
1 5
Is this solution feasible to our formulation? We need additional constraints, so-called subtour elimination constraints.
Traveling Salesman Problem x iS jS
x iS jS
ij
ij
1 for every subset S
S 1 for every subset S 2
3
4
1 5
21
3/7/2017
Traveling Salesman Problem Subtour elimination constraints for the example:
2
3
S 1,2,3, S 4,5
x13 x14 x23 x24 x53 x54 1
4
1 5
S 1,4, S 2,3,5
2
3
x12 x13 x15 x42 x43 x45 1 4
1 5
Traveling Salesman Problem Heuristics for the TSP 1. Construction Heuristics build a feasible solution by adding a node to the partial tour one at a time and stopping when a feasible solution is found. Many construction heuristics are also called greedy heuristics because they seek to maximize the improvement at each step.
22
3/7/2017
Traveling Salesman Problem Nearest Neighbor Step 1. Start with any node as the beginning of the path. Step 2. Find the node closest to the last node added to the path. Step 3. Repeat Step 2 until all nodes are contained in the path. Then, join the first and last nodes.
Traveling Salesman Problem 3
2 Start with node 2.
2 3
Nodes added 2 5 1 4 3
Tour
3
4
2
2
1
4 4
1
5
3
2 2-5 2-5-1 2-5-1-4 2-5-1-4-3 2-5-1-4-3-2
5 2
3
3
2
1 2
1
4
3
5
23
3/7/2017
Traveling Salesman Problem Nearest Insertion Step 1. Start with a node i only.
Step 2. Find node k such that cik is minimal and form subtour i–k–i. Step 3. Selection step. Given a subtour, find node k not in the subtour closest to any node in the subtour.
Step 4. Insertion step. Find the arc (i,j) in the subtour which minimizes cik+ckj-cij. Insert k between i and j. Step 5. Go to step 3 unless we have a Hamiltonian cycle.
Traveling Salesman Problem Farthest Insertion Step 1. Start with a node i only. Step 2. Find node k such that cik is maximal and form subtour i–k–i.
Step 3. Selection step. Given a subtour, find node k not in the subtour farthest from any node in the subtour. Step 4. Insertion step. Find the arc (i,j) in the subtour which minimizes cik+ckj-cij. Insert k between i and j.
Step 5. Go to step 3 unless we have a Hamiltonian cycle.
24
3/7/2017
Traveling Salesman Problem Arbitrary Insertion Step 1. Start with a node i only.
Step 2. Find node k such that cik is minimal and form subtour i–k–i. Step 3. Selection step. Arbitrarily select node k not in the subtour to enter the subtour.
Step 4. Insertion step. Find the arc (i,j) in the subtour which minimizes cik+ckj-cij. Insert k between i and j. Step 5. Go to step 3 unless we have a Hamiltonian cycle.
Traveling Salesman Problem Cheapest Insertion Step 1. Start with a node i only. Step 2. Find node k such that cik is minimal and form subtour i–k–i.
Step 3. Insertion step. Find arc (i,j) in the subtour and node k not, such that cik+ckj-cij is minimal and, then, insert k between i and j. Step 4. Go to step 3 unless we have a Hamiltonian cycle.
25
3/7/2017
Traveling Salesman Problem Clarke and Wright Savings Heuristic 1. Select any node as the central depot which is denoted as node 0. Form subtours i-0-i for i=1,2,...,n. (Each customer is visited by a separate vehicle) 2. Compute savings sij=c0i + c0j - cij for all i,j 3. Identify the node pair (i,j) that gives the highest saving sij 4. Form a new subtour by connecting (i,j) and deleting arcs (i,0) and (0, j) if the following conditions are satisfied a) both node i and node j have to be directly accessible from node 0 b) node i and node j are not in the same tour.
Traveling Salesman Problem Clarke and Wright Savings Heuristic
5. Set sij=-, which means that this node pair is processed.
Go to Step 3, unless we have a tour.
26
3/7/2017
Traveling Salesman Problem Heuristics for the TSP 2. Improvement Heuristics begin with a feasible solution and successively improve it by a sequence of exchanges while maintaining a feasible solution throughout the process.
Traveling Salesman Problem Heuristics for the TSP
1
2
3
4
1
2
3
4
27
3/7/2017
Traveling Salesman Problem Two exchange heuristics (2-opt) Starting with any tour, we consider the effect of removing any two arcs in the tour and replacing them with the unique set of two arcs that form a different tour.
If we find a tour with a lower cost than the current tour, the we use it as the new tour. When no possible exchange can produce a tour that is better than the current tour, we stop.
Traveling Salesman Problem 3
3
2
4
2 3
2
3
2
1
2
2
4
1
3 2
4
4
1
5
3
5
5
3
5
Suppose the initial tour is given as 1-2-3-4-5 with cost 15.
28
3/7/2017
Traveling Salesman Problem 3
2
3
3
2
2
2
2
4
1
4 5
3
Remove 1-2 and 3-4
5
2
1
5
3
3
5
3
2
3 4
3
Add 1-3 and 2-4
4
1
cost=18
5
3
5
Traveling Salesman Problem 3
2
3
3
2
2
3
2
2
4
1 5
3
5
3
Remove 1-2 and 4-5
5
4
1 5
3
2
3 2
1
1
2
4
Add 1-4 and 2-5 cost=11
3
5
29
3/7/2017
Traveling Salesman Problem There are n (n-1)/2 - n possible ways of removing and adding arcs. In this case, n=5, and we have 5 combinations. The best tour obtained from the process at the first iteration is 2-3-4-1-5-2 with cost 11. We use this solution as the starting tour and apply the process again.
Contoh TSP; solusi dengan Win Qsb Perusahaan “Q” akan menentukan rute terpendek perjalanan truk yang mengangkut teh botol pusat distribusi di CMH mengunjungi seluruh ritel dalam jaringan di bawah ini dan kembali lagi pusat distribusi di CMH.
30
3/7/2017
Solusi dengan Software Win Qsb Travelling Salesman Problem (TSP) 1) Eksekusi Software Win Qsb, kemudian klik : Network Modelling – File – New 2) Klik : Edit – Node Names, kemudian isi Problem, maka akan tampil form sbb . : kemudian isi form sebagai berikut – ok :
3) Isi matriks di bawah ini :
31
3/7/2017
4) Klik solve and Analyze – solve :
5) Klik Result : Graphics Solution
32
3/7/2017
Model penugasan berguna untuk mengalokasikan pekerja-pekerja dengan skill tertentu pada mesin-mesin yang akan di-maintenance
Langkah – Langkah Penyelesaian (1) 1.
2. 3.
Membuat suatu tabel biaya Opportuniti ( opportunity cost table ) yakni dengan membuat reduksi baris dan kolom Buat tabel Reduksi baris : dengan cara mengurangkan semua biaya dalam tiap baris dengan biaya terkecil yang ada pada tiap baris tersebut. Buat tabel reduksi kolom : dengan cara mengurangkan semua biaya yang ada pada semua kolom dari tabel reduksi baris dengan biaya terkecil yang ada pada tiap kolomnya
33
3/7/2017
Langkah – Langkah Penyelesaian (2) 4.
5.
Buat tabel biaya pengujian : yakni tambahkan garis pada tabel yang sudah direduksi baik secara vertikal maupun secara horisontal dimana terdapat minimal dua angka nol. Untuk mencapai tabel yang optimal, maka jumlah minimal garis = jumlah baris atau kolom, jika belum maka buat tabel pengulangan model penugasan dengan cara kurangkan semua biaya yang tidak dilalui garis dengan biaya yang terkecil yang juga tidak dilalui garis dan untuk semua angka nol pada perpotongan garis harus ditambahkan dengan biaya yane terkecil. Kemudian tarik garis secara vertikal dan horisontal seperti langkah sebelumnya.
Langkah – Langkah Penyelesaian (3) 6.
Apabila jumlah minimal garis = jumalah baris atau kolom, maka tabel tersebut sudah opitmal. Maka tentukanlah penugasan berdasarkan sel di mana terdapat angka nol.
34
3/7/2017
penggambaran umum: mesin
pekerjaan
1 2 . . . m
1
2
...
n
c11 c12 . . . cm1
c12 c22 . . . cm2
... ...
...
c1n c2n . . . cmn
1
1
...
1
1 1 . . . 1
model matematis: 0, jk pekerjaan ke-i tidak ditugaskanpd mesin ke-j
xij = 1, jk pekerjaan ke-i ditugaskan pada mesin ke-j
35
3/7/2017
model persoalan penugasan: n
minimumkan:
n
z = cij xij i=1 j=1
berdasar pembatas: n
xij = 1, i = 1,2,…,n j=1 n
xij = 1, j = 1,2,…,n i=1
xij = 0 atau 1
jika pi dan qj merupakan konstanta pengurang thd baris i dan kolom j, maka jika dilakukan operasi pengurangan pi dan qj thd matriks ongkos, akan diperoleh “zero entries”, yaitu elemenelemen biaya dalam matriks yg berharga nol variabelvariabel yang menghasilkan solusi optimum. contoh: mesin 2
1 1 Pekerja
2 3 1
3
5
7
9
14
10
12
15
13
16
1
1 1 1
1
36
3/7/2017
solusi awal mesin 2
1 1 pekerjaan
3
5
7
9
14
10
12
1
2
1 15
3
13
16 1
1
1
1 1 1
1
Elemen-elemen nol dibuat dgn mengurangkan elemen terkecil masing-masing baris (kolom) dr baris (kolom) yang bersangkutan. Dengan demikian, matriks cij’ yg baru: 1 2 3
1
2
3
0 4 2
2 0 0
4 2 3
p1 = 5 p2 = 10 p3 = 13
Matriks terakhir dpt dibuat untuk memperbanyak elemen matriks yg berharga nol dengan cara mengurangkan q3 = 2 dr kolom ke-3. Hasilnya:
1 2 3
1
2
3
0 4 2
2 0 0
2 0 1
penugasan feasible dan optimum : (1,1), (2,3), dan (3,2) biaya penugasan
: 5 + 12 + 13 = 30
sama dengan p1 + p2 + p3 + q3 = 5 +10 + 13 + 2 = 30
37
3/7/2017
Seorang supervisor maintenance PTBA akan merencanakan penugasan 4 orang teknisi ke 8 mesin yang akan di-maintenance. Data nama teknisi, nama mesin dan estimasi waktu pengerjaan (jam) di masing-masing mesin adalah sebagai berikut : Keterangan: Data kosong = waktu untuk seorang teknisi yg. tidak memiliki skill untuk memaintenance mesin tersebut. AM1= jenis pekerjaan A untuk memaintenance Mesin1 (M1), dst…. Roni1=Roni2 = adalah orang yg. sama, hal ini dilakukan kr. software hanya mengalokasikan setiap inisial orang tepat kesatu jenis pekerjaan.
Buatlah rencana penugasannya, sehingga diperoleh total waktu pengerjaan paling minimum!
Eksekusi Win QSB, pilih Network Modelling – pilih Assigment Problem. Isi sebagai berikut :
Pilih Menu Edit - Node Names, kemudian edit nama pekerja dan nama mesin
38
3/7/2017
Entri, data waktu penyelesaian pekerjaan di masing-masing mesin sebagai berikut :
Klik menu Solve & Analyze – Solve Problem, maka akan tampil sbb. :
Untuk menampilkan gambar penugasan, klik Results – Graphics Solution
39
3/7/2017
40
3/7/2017
The Linear Programming Formulation
41
3/7/2017
42
3/7/2017
Transshipment or Transhipment is the shipment of goods or containers to an intermediate destination, and then from there to yet another destination. One possible reason is to change the means of transport during the journey (for example from ship transport to road transport), known as transloading. Another reason is to combine small shipments into a large shipment, dividing the large shipment at the other end. Transshipment usually takes place in transport hubs. Much international transshipment also takes place in designated customs areas, thus avoiding the need for customs checks or duties, otherwise a major hindrance for efficient transport.
Contoh : Terdapat 2 buah pabrik dengan kapasitas supply masing-masing S1 = 600 dan S2 = 800. Untuk mendistribusdikan produk ke konsumen digunakan pusat distribusi (T), T1 membutuhkan 200 dan T4 membutuhkan 100 sedangkan T2 memiliki supply 350 dan T3 = 200. Retail di daerah pemasaran (D), membutuhkan D1 = 500, D2 = 350, D3 = 900. Biaya transportasi tertera di setiap busur.
43
3/7/2017
Matrix Transhipmentnya adalah sebagai berikut :
Bagaimana mendistribusikan barang dari pabrik melalui pusat distribusi untuk memenuhi kebutuhan pelanggan dengan total biaya transportasi minimum ? Gunakan Win Qsb untuk mecari solusinya.
44
