Einstein said " as far as models represent reality the are in-precise and as far as they are precise they do not represent reality" (source unknown)
“Real World”
RUTE -
“Model”
OPTIMUM : Panjang Turn/arah
Barrier Stop
Lebar Kecepatan Kapasitas
v c
Modeling Our World, Michael Zeiler, 1999
A
D
B
C
Tanya : Mana Route terbaik dari A ke C ? Jawab : A
D
C
http://www.yell.com/maps/
The economic foundation of the modern world is its infrastructure; the collection of highways, waterways, rails, cables, and pipelines that enable the movement of people, energy, commodities, and ideas. This infrastructure is modeled as networks, and the form, capacity, and efficiency of these networks have a substantial impact on our standard of living and our perception of the world around us.
Networks are conceptually simple. They are comprised of two fundamental components, edges and junctions. Streets, transmission lines, pipe, and stream reaches are examples of edges. Street intersections, fuses, switches, service taps, and the confluence of stream reaches are examples of junctions. Edges connect together at junctions, and the flow from one edge automobiles, electrons, water can be transferred to another edge.
WORK FLOW Efficient, Effective & Valuable Distribution ?
Survei Lapangan (lokasi), Time study, Market research
Plotting Outlet Data Primer & Sekunder
Digital Road Map
Pengolahan & Analisis Data
Competitive advantage, Increase prod.
Execution & Monitor - Customer Mapping System - Sales Territory Planning - Distribution Routing
Software Dist. Tools
Indobizmaps.com
CSS in CCA - Korea North Region
Daily Dispatching mampu mengurangi waktu, jarak dan biaya pengiriman Rute Sebelum
-81 ribu rupiah
-55 Menit
-11.6 Km 8/19/02
Rute Sesudah 26
” Networks are systems of connected linear features that form a framework trough which resource flow ” “Networks adalah sistem yang berkaitan dengan kenampakan linear yang membentuk kerangka kerja pada aliran sumberdaya” (Manual User’s PC Network Installation Guide, 1989). Seperangkat garis hubung yang memiliki atribut tertentu yang menunjukkan adanya arus (flow) obyek dari satu tempat ke tempat lain. (DeMers, 1997:1998)
• Apa itu jaringan? • Mengapa menggunakan jaringan? • Bagaimana struktur data jaringan ? • Bagaimana model data jaringan ? • Bagaimana kemampuan analisis jaringan ?
• Banyak aktivitas ekonomi dan sosial dunia diatur dalam jaringan • Bentuk, kapasitas, dan efisiensi jaringan mempunyai pengaruh yang kuat pada standart hidup dan persepsi kita tentang alam sekitarnya • Jaringan juga dijumpai dalam bentuk fisik contoh : jaringan sungai
Any system of interconnected linear features
• Solving problems involving networks • Goal is efficiency – Saving time and money
• Network data (connectivity is needed)
• Network analysis software – A GIS!
• Jaringan rel kereta api (PT. KAI) • Jaringan jalan dan jalan raya bebas hambatan (Jasa Marga, dll.) • Jaringan listrik (PLN) • Jaringan telepon (Telkom, dll.) • Jaringan transportasi udara (Garuda, dll.) • Jaringan pengiriman barang (PT. POSINDO, DHL Courier, dll.) • Jaringan jalan (Pelayanan ambulan, Pemadam Kebakaran, Kepolisian, dll.) • Arus komoditas tertentu (Export/Import) • Pergerakan hewan-hewan (Taman Konservasi) • dll.
• Route terbaik mana dari suatu lokasi ke tempat tujuan tertentu? • Bagaimana akses suatu lokasi terhadap lokasi lainnya ?
• Berapa banyak lintasan/jalur yang dapat diturunkan dari titik awal ke titik tujuan ? • Dimana seharusnya letak pusat pelayanan?
• Pusat-pusat pelayanan mana yang utama di suatu lokasi ? • Bagaimana peta dapat memberi alamat-alamat ?
• Jalur perjalanan menemukan jalur terpendek (termurah atau tercepat) antar lokasi • Asesibilitas menetapkan jumlah cara bagaimana dari suatu lokasi ke lokasi yang lain dapat dicapai • Lokasi/distribusi penempatan lokasi objek yang optimal sehingga variabelnya akan mencapai nilai maksimum atau minimum • Address Matching menemukan lokasi berdasarkan deskripsi alamat
• Direct path: mencari jalur terpendek antara rumah dengan kampus • Optimum routing: membantu deliveryman pizza mengantar pesanan ke beberapa rumah dalam waktu singkat • Closest facility: mencari Rumah Sakit terdekat dari tempat kejadian kecelakaan
• Drive time analysis: membantu manager toko untuk menentukan berapa banyak customer yang dapat terlayani dalam waktu tempuh 10 menit • General driving directions: Mapquest!
http://www.mapquest.com/maps?country=ID
Sebuah jaringan dapat digambarkan nodes/ junctions dan links/edges
secara
digital
oleh
• Nodes menggambarkan titik-titik persimpangan dan pertemuan • Links menggambarkan garis fasilitas transportasi antar nodes.
Node/ junctions
Link/ edges
• Jaringan Planar ada perpotongan garis Ex. : Jaringan jalan (Perhatikan jalan bebas hambatan dan jalan Layang) • Jaringan Non-Planar Tidak Ada perpotongan garis Ex. : Jaringan pesawat terbang
= Node = Garis/Lintasan
Overpass and underpass
Over/under pass
Intersection PLANAR
• Garis lurus, seperti jalan raya (Gambar 1a) • Garis bercabang, seperti alur sungai (Gambar 1b) • Sirkuit (Gambar 1c), seperti jalan yang memiliki arah putar (Muehrcke dan Muehrcke, 1992 dalam DeMers, 1997:198).
(a)
(b)
(c)
Gambar 1. (a) network garis lurus, (b) network bercabang, dan (c) sirkuit. (Sumber: DeMers , 1997:1998).
•Directed network hanya memiliki satu jalur arus (gambar 2a), misalnya, sungai akan mengalir ke satu jalur, atau jalan yang hanya memiliki satu jalur. •Undirected network. arus dapat berada dalam kedua jalur (gambar 2b), seperti jalan-duaarah (DeMers, 1997:1999).
Gambar 2. Directed network (a) hanya memiliki satu jalur, dan Undirected network (b) memiliki dua jalur. (Sumber: DeMers, 1997:1999).
ONEWAY
Text
10
Sesuai arah Rute FT = dari From ke To junction TF = dari To ke From junction B = jalan dua arah N = jalan tidak dapat diakses
Gambar network setelah dieksekusi. Network memperhitungkan Oneway
1. Tingkat kasar/jelek (coarse level) hanya menggambarkan jalan utama/arteri 2. Tingkat sedang (medium level) cocok untuk perencanaan transportasi
3. Tingkat halus/baik (fine level) hampir sama dengan jaringan jalan yang sebenarnya
(1)
(2)
(3)
Pergerakan aliran dikontrol oleh elemen-elemen network
ONEWAY
Text
10
Sesuai arah Rute FT = dari From ke To junction TF = dari To ke From junction B = jalan dua arah N = jalan tidak dapat diakses
TF_MINUTES Short Integer Default FT_MINUTES Short Integer Default
Sesuai tabel waktu tempuh
1. Arah lurus
8 6
Dari garis 6 ke 7 dapat lurus, dan dari garis 8 ke 9 juga lurus, tetapi jalan 6 ke 8 atau ke 9 tidak bisa belok
7
9
2. Tidak boleh belok 8 6
20
9
7
Dari garis 6 ke 9 tidak boleh belok kiri, tetapi dari garis 9 ke 7 bisa belok kiri. Waktu yang diperlukan untuk membelok juga harus diperhatikan dan dimasukkan antara pertemuan dua garis
3. Arah bebas, dengan waktu pemberhentian 8 6
20
7
STOP
9
Dari setiap garis bebas kearah mana saja belok kiri,lurus atau belok kanan, tetapi ada tenggang waktu untuk belokan misal dari garis 6 ke 7 diperlukan 15 detik, 6 ke 8 20 detik, dan 6 ke 9 10 detik
4. Belokan U 8 6
20
9
7
Untuk belokan U disamping waktu yang diperlukan untuk membelok juga diperhatikan sudut yang dibentuk oleh garis 6 dan garis 6 adalah 180o
Travel cost for turn • nodes.dbf 2
3
1
2
1
3 4
Record
Fjunction
Tjunction
1
2
3
2
3
1
3
3
4
• Turn table 1
2
X
5 3
Junction
F_edge
T_edge
Seconds
5
1
2
3
5
3
1
-1
Prohibited turn • Set the value of travel cost
Dijkstra's Algorithm is used to calculate the shortest path from a starting node to all other nodes of a graph (directed or undirected). To do this the direct path from the starting node to the separate nodes is noted as the shortest way. In the following steps the cheapest not yet visited node is chosen and it is checked if there is a node that can be reached from there with lower costs than before. In the end one has the cheapest path from the starting node to all other as long as all edges have a positive weight.
Dijkstra's algorithm Dijkstra's algorithm - is a solution to the single-source shortest path problem in graph theory.
Works on both directed and undirected graphs. However, all edges must have nonnegative weights. Approach: Greedy Input: Weighted graph G={E,V} and source vertex v∈V, such that all edge weights are nonnegative Output: Lengths of shortest paths (or the shortest paths themselves) from a given source vertex v∈V to all other vertices By Laksman Veeravagu and Luis Barrera
Dijkstra's algorithm - Pseudocode dist[s] ←0 (distance to source vertex is zero) for all v ∈ V–{s} do dist[v] ←∞ (set all other distances to infinity) S←∅ (S, the set of visited vertices is initially empty) Q←V (Q, the queue initially contains all vertices) while Q ≠∅ (while the queue is not empty) do u ← mindistance(Q,dist) (select the element of Q with the min. distance) S←S∪{u} (add u to list of visited vertices) for all v ∈ neighbors[u] do if dist[v] > dist[u] + w(u, v) (if new shortest path found) then d[v] ←d[u] + w(u, v) (set new value of shortest path) (if desired, add traceback code) return dist
By Laksman Veeravagu and Luis Barrera
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
Dijkstra Animated Example
algoritma floyd warshall
contoh apabila kita berada dari suatu tempat di titik A akan menuju tempat yang berada di titik E di mana kita harus melewati minimal satu titik antara b,c,d dan f .
apabila kita memakai floyd warshall maka kita harus mengtotalkan jumlah jaraknya, spt: a-b-d-e = 10+15+10 =35 km a-d-e = 20+5=25 km a-c-e = 30+25=55km a-f-e = 20+25=45 km dll,,
Bellman-Ford merupakan salah satu algoritma yang menangani kasus pencarian lintasan dengan bobot terkecil.
Relaxing tahap 4
• simulasi dan modeling sistem pergerakan dan • sistem basis data jaringan, query data, penelusuran rute secara efektif dan interaktif.
a. Route Optimum
b. Service Area c. Closest Fasility
d. Origin-Destination Cost Matrix e. Vehicle Routing Problem f. Address Locator / Geocoding
• finding a simple route between two locations or one that visits several locations • The best route can be the quickest, shortest, or most scenic route, depending on the impedance chosen.
• Network Analyst relies on “impedances”
• Default impedance is line length • Can also be others, such as estimated traveltime • Values must be in attribute table and specified before analysis If you know line length and speed limit, a travel time can be estimated 5 mile street/30 miles per hour speed limit * 60 min/hr = 10 minutes
• One way streets-can be specified in attribute table (must specify allowed travel direction) • Prohibited turns-can be specified in turntable (very tedious procedure)
• Under/Overpasses-can be specified in attribute table (add elevation fields)
Data source: ArcGIS Online (ESRI, Inc., Redlands, California, USA)
directions with turn-by-turn maps
Finding service areas With Network Analyst, you can find service areas around any location on a network. A network service area is a region that encompasses all accessible streets—that is, streets that lie within a specified impedance. For instance, the 10-minute service area for a facility includes all the streets that can be reached within 10 minutes from that facility.
Accessibility refers to how easy it is to go to a site. In ArcGIS Network Analyst, accessibility can be measured in terms of travel time, distance, or any other impedance on the network. Evaluating accessibility helps answer basic questions such as, How many people live within a 10-minute drive from a movie theater? How many customers live within a half-kilometer walking distance from a convenience store? Examining accessibility can help you determine how suitable a site is for a new business. It can also help you identify what is near an existing business to help you make other marketing decisions.
When finding closest facilities, you can specify how many to find and whether the direction of travel is toward or away from them. examples : 1. Finding the hospital closest to an accident, 2. The police cars closest to a crime scene, 3. The store closest to a customer's address
create an origin–destination (OD) cost matrix from multiple origins to multiple destinations
Jarak Antar Minimarket di Yogyakarta
Jarak Antar Kota Terpilih di Jawa Barat
merupakan permasalahan optimasi penentuan rute dengan keterbatasan kapasitas kendaraan. Pada permasalahan ini, ada sebuah depot awal dan sejumlah n tempat untuk dikunjungi dengan demand yang dapat berbeda-beda. Sebuah kendaraan diharapkan untuk memenuhi permintaan setiap tempat tersebut dari depot.
KOMARUDIN – 2010/09/14
Karakteristik Dari Permasalahan VRP: • Perjalanan kendaraan berawal dan berakhir dari dan ke depot awal • Ada sejumlah tempat yang semuanya harus dikunjungi dan dipenuhi permintaannya tepat satu kali • Jika kapasitas kenderaan sudah terpakai dan tidak dapat melayani tempat berikutnya, kendaraan dapat kembali ke depot untuk memenuhi kapasitas kendaraan dan melayani tempat berikutnya. • Tujuan dari permasalahan ini adalah meminimumkan total jarak yang ditempuh kendaraan dengan mengatur urut-urutan tempat yang harus dikunjungi beserta kapan kembalinya kendaraan untuk mengisi kapasitasnya lagi.
KOMARUDIN – 2010/09/14
Vehicle Routing Problem (VRP) consists in designing the optimal set of routes for fleet of vehicles in order to serve a given set of customers.
Consider the situation shown below where we have a depot surrounded by a number of customers who are to be supplied from the depot.
The depot manager faces the task of designing routes (such as those shown below) for his delivery vehicles and this problem of route design is known as the vehicle routing or vehicle scheduling problem.
D = Depot X = customer
Prof. G. Srinivasan Departement of Management Studies Indian Institute of Technology Madras https://www.youtube.com/watch?v=A1wsIFDKqBk
Vehicle Routing Problem (VRP) Vehicles • Each vehicle has a limit (capacity - usually weight and/or volume) on the goods carried, e.g. tankers delivering to petrol (gasoline) stations are volume limited, buses have a limit on the number of people legally allowed on board, etc. • Each vehicle has a total working time from departure to arrival back at the depot, typically to comply with legal restrictions on driver working hours. • Each vehicle has a time period within which it must leave the depot, typically to ensure that space is available for incoming vehicles to resupply the depot. • Each vehicle has a number of time periods during which it does nothing (driver rest periods). • Each vehicle has a cost associated with its use for deliveries.
Customers • Each customer has a certain quantity which has to be delivered (and/or collected), typically we usually think of pure delivery operations (e.g. to resupply local shops) but there are operations involving collections only (e.g. domestic rubbish (garbage), emptying of post boxes) and operations involving a mix of collections and deliveries (e.g. the business level express delivery/collection operations of DHL/Federal Express/UPS). Sometimes this quantity is known exactly (the deterministic case) and sometimes known with a degree of uncertainty (the stochastic case).
• Each customer has a number of time periods during which delivery (and/or collection) can occur (time windows). For example a customer might be prepared only to accept delivery between 10.30 and 11.30 or between 14.00 and 16.15. These two periods of time are the time windows for the customer. Time windows are convenient to customers as they know when delivery is likely to occur and they can schedule deliveries to suit the work pattern of their staff (who may be needed to check incoming goods, sign for them, help unload them, etc). Time windows are inconvenient to delivery companies as they limit their flexibility (e.g. two customers right next door to each other might have very different time windows). • Each customer has an associated visit time (drop time). • Each customer has a set of vehicles which cannot be used for delivery (access restrictions). • Each customer has a priority for delivery (if the vehicles cannot deliver to all the customers). Typically this might happen due to driver/vehicle unavailability or due to poor weather conditions dramatically reducing vehicle speeds (it is well known that in the UK, particularly around London, the slightest snow causes traffic chaos!) • Each customer may accept split visits (a delivery/collection by more than one vehicle) or not.
Other factors • Multiple trips by the same vehicle on a single day, where the vehicle returns to the depot and then goes out again (e.g. post office vans) • Trips by the same vehicle longer than one day (i.e. with overnight stops).
• Compartmentalised vehicles with many different types of product to deliver. Petrol (gasoline) tankers are often compartmentalised (for leaded/unleaded/diesel/LPG), as are food delivery vehicles (frozen/nonfrozen). • More than one depot, where vehicles can start/visit/end at different depots.
Objective
• minimise the number of vehicles used (vehicles, and their associated drivers, are often a fixed cost) • minimise the total distance (or time) travelled (this typically corresponds to variable cost) • minimise some combination of number of vehicles used and total distance (or time) travelled
Styles
Typical reference dataset geometry
Typical reference dataset Address search parameters Examples representation
Applications
US Streets
Lines
Address range for both sides of street segment
All address elements in a single field
320 Madison St.
Finding a house on a specific side of the street
US Alphanumeric
Lines
Address with grid zone information
All address elements in a single field
N2W1700 County Rd.
Used in some regions of Illinois and Wisconsin
US Hyphenated
Lines
Cross street information in address
All address elements in a single field
105-30 Union St.
Used in locations such as Queens, New York
US One Range
Lines
One range for each street All address elements in a segment single field
2 Summit Rd.
Finding a house on a street where side is not needed
US One Address
Points or polygons
Each feature represents an address
71 Cherry Ln.
Finding parcels, buildings, or address points
Single Field
Points or polygons
Each feature represents a particular place, Single, user-specified landmark, or point of variable interest
Cabrillo College
Finding place names or landmarks that can be identified by names in a single filed
US Cities with State
Points or polygons
City within a state
City name and state name Rice, WA or abbreviation
Finding a specific city in the country
World Cities
Points or polygons
City within a country
City name and country name
Lima, Peru
Finding a specific city in the world
ZIP 5 Digit
Points or polygons
Zip Code region or centroid
Five-digit ZIP code
22066
Finding a specific ZIP code location
ZIP + 4
Points or polygons
Five-digit ZIP codes and ZIP + 4 region or centroid four-digit extension in separate field
96822, 2323
Finding a specific ZIP+4 location
ZIP + 4 Range
Points or polygons
Each feature represents a Five-digit ZIP codes and ZIP code and a low and four-digit extension in high plus 4 range separate field
63703, 0078
Finding a specific ZIP+4 location
All address elements in a single field
