Logistik do-it-yourself yang mudah

Saya ingin berbagi dengan Anda pengalaman menciptakan sistem logistik di satu perusahaan perdagangan.

Suatu hari, di dekat 2012, kepala mengatur tugas: untuk memikirkan masalah mengoptimalkan biaya transportasi logistik organisasi.
Bidang utama kegiatan perusahaan adalah grosir dan pengiriman produk, di mana biaya transportasi menempati porsi biaya yang signifikan.

Manajemen mempertimbangkan bahwa waktunya telah tiba untuk mengatur pengeluaran uang untuk bahan bakar, dan ada juga kecurigaan bahwa pengemudi juga terlibat dalam pengiriman "kiri" antar penerbangan. Dalam perusahaan kecil dan menengah, banyak yang dibangun di atas kepercayaan, karena menjaga individu untuk kontrol tidak menguntungkan dan tidak selalu disarankan. Ketika biaya naik dan efisiensi turun, Anda hanya perlu melakukan sesuatu.

Untuk mulai dengan, kami mencoba untuk memecahkan masalah dengan metode manajemen: pengukuran tingkat bahan bakar terus menerus, pembacaan takometer, pengukuran waktu pengiriman dengan pendampingan pribadi dari kargo. Efeknya tidak lain adalah negativitas, kecurigaan dan gerakan yang tidak perlu (mengukur ini juga pekerjaan untuk seseorang). Jika masih mungkin untuk menentukan ruang lingkup perkiraan dengan satu rute, maka dengan penerbangan 25-35 fasilitas ritel semuanya berubah sangat banyak, penyebarannya sangat besar, baik dalam waktu maupun bahan bakar.

Tujuan: untuk mengirim kendaraan yang sibuk ke perusahaan dagang, mengurangi jarak tempuh, dan karenanya biaya. Jika memungkinkan, hindari penyimpangan dari rute. Tujuannya adalah untuk mengurangi biaya dengan investasi minimal dalam keuangan dan waktu implementasi, sehingga untuk berbicara kemarin. Selama diskusi, mereka menyepakati beberapa alternatif:

1. menggunakan salah satu layanan untuk menghitung rute dan menghitung bahan bakar dan pelumas;
2. memakai modul pelacakan / pelacakan armada;
3. merancang sesuatu sendiri;

Kami memutuskan untuk mencoba ketiga solusi dan memilih yang terbaik:

1. Pada saat itu, kami tidak menemukan solusi turnkey yang baik. Entah desain turnkey, tapi mahal, atau mengambil apa adanya dan lebih lanjut dengan persetujuan. Sudah mencoba beberapa layanan online. Secara keseluruhan, ini tidak buruk, tetapi pada dasarnya kesulitannya adalah menggandakan informasi dari sistem akuntansi, jumlah tindakan untuk mendapatkan hasilnya (klik di sini, buka di sini, perbarui direktori), semuanya online (pada waktu itu sangat penting). Namun kelemahan terbesarnya adalah kesulitan dalam menciptakan rute dengan banyak titik dan memilih rute terbaik. Biasanya, semuanya harus dipilih secara manual, menyesuaikan nilainya, yang lama dan tidak selalu berhasil.

Setelah beberapa bulan bekerja, mereka menolak keputusan ini.

2. Sebagai percobaan, mereka memasang modul pelacakan GSM pada selusin mobil.
Hasilnya lebih sukses. Anda selalu tahu di mana mobil itu berada. Tetapi biayanya lebih mahal daripada opsi pertama. Namun, setelah mengidentifikasi beberapa kasus penyimpangan dari rute (satu pengemudi shabbat, yang kedua mengunjungi nyonya jantung, selama jam kerja), staf mulai secara intensif menyingkirkan perangkat tersebut. Meskipun mereka tidak antusias menerima inovasi ini sebelumnya. Entah terminal daya berkedip secara tidak sengaja, atau ketika mesin sedang diperbaiki, perangkat gagal, atau elektronik "terlalu panas" di bawah sinar matahari. Jadi selama tiga tahun kami kehilangan 9 perangkat. Secara umum, keputusan itu ternyata positif, tetapi dari minus - saya harus melihat rute perjalanan untuk waktu yang lama untuk mengidentifikasi kegiatan yang mencurigakan, yang sangat tidak nyaman. Nilai tambah dalam sistem pelacakan adalah item pada mengekspor trek, yang memungkinkan untuk mengakumulasi statistik tertentu pada rute.

Kemudian, kami menggunakan sistem lain dari salah satu operator seluler utama untuk komunikasi korporat dan melacak aktivitas agen penjualan, hasilnya serupa: kartu SIM rusak, telepon hilang, mereka lupa di rumah, baterai habis, orang akan selalu menemukan jalan keluar.

3. Sejalan dengan dua pendekatan pertama, kami memutuskan untuk menciptakan sepeda , untuk menyadari dalam sistem akuntansi kami kemampuan untuk membangun rute sendiri.

Pertama, kami membawa semua tempat kunjungan dan memasukkan koordinat geografis mereka ke dalam basis data. Kami mendapatkan koordinat sesuai dengan pelacak GPS ketika mengunjungi, serta secara visual dari peta OSM , menemukan tempat yang tepat dengan mouse dan menyalin koordinat.

Pada tahap kedua, perlu untuk mendapatkan peta vektor wilayah dalam format yang mudah.
Pilihan jatuh pada OSM yang sama, karena kartu memiliki format terbuka. Kami tidak menguasai dump planet ini, jadi kami awalnya mengunggah data dalam bentuk XML, melalui ekspor dari OSM itu sendiri, dan kemudian menghubungkan wilayah. Kemudian datang di proyek GIS-LAB . Orang-orang yang layak ini selama bertahun-tahun melakukan pembuangan harian atas wilayah - wilayah, dibagi berdasarkan wilayah. Tetapi semua orang ingin makan, proyek baru-baru ini terhenti, dan orang-orang telah pindah , dan mereka melakukan pekerjaan yang sama dengan harga yang wajar.

Setelah menerima peta dalam format XML, kami mengekstraksi layer yang bertanggung jawab untuk jalan sesuai dengan spesifikasi . Karena volume kartu dari beberapa daerah tetangga menempati sepuluh gigabyte, parser SAX ditulis dalam RUBY, ia hanya memilih tag yang diperlukan dan menggabungkan daerah tetangga di mana kegiatan tersebut dilakukan dalam satu struktur.

Proyek itu sendiri ditulis sebagai DLL eksternal ke sistem akuntansi yang ditulis dalam Pascal. Armada perangkat tempat sistem seharusnya bekerja adalah, dengan kata lain, usang, sehingga ada batas 1 GB RAM (Ya, ada juga perusahaan yang menggunakan teknik ini, telah bekerja selama 10 tahun, dan akan bekerja dalam jumlah yang sama). Awalnya, ada keinginan untuk memecah kartu menjadi beberapa bagian dan memuatnya ke dalam RAM sesuai kebutuhan (seperti pada navigator), tetapi itu sangat lambat. Akibatnya, kami berhasil menyusun hingga lima puluh MB yang wajar.

Dalam OSM, peta jalan direpresentasikan sebagai bagian vektor jalan dengan atribut tambahan. Dalam keputusan kami, kami menggunakan daftar kedekatan . Di mana puncaknya adalah titik pada peta, dan ujung-ujungnya adalah jalur ke titik tetangga. Untuk optimisasi, kami percaya bahwa ada maksimum empat jalur (persimpangan) dari satu titik. Jika ada lebih dari 4 jalur, maka Anda perlu membagi tepi menjadi dua jalur tambahan, jadi kami selalu memiliki jumlah tepi tetap = 4 untuk setiap titik peta. Pendekatan ini memungkinkan kami untuk menyelaraskan data dalam memori, meskipun agak berlebihan.

Perlu dicatat bahwa Bumi bukanlah bola (secara tidak terduga), tetapi geoid , tetapi untuk tujuan kartografi, ia disederhanakan menjadi spheroid atau ellipsoid .

Untuk tujuan kami, saya menemukan formula untuk menghitung jarak antara dua titik di permukaan ellipsoid, yang saya tidak bisa mengerti arti yang paling dalam, tetapi ini tidak menghalangi kami untuk menggunakannya.


Setelah membuat dasar jalan, lapisan visual diperlukan untuk menampilkan area sekitarnya. Proyek maperitive membantu di sini , memungkinkan kami untuk mem - parsing peta OSM daerah menjadi bagian ubin dengan lapisan perkiraan, seperti 10 ^ 100 atau Yandex. Ada upaya untuk bekerja dengan peta raksasa online, merender peta vektor di atas lapisan browser, tetapi karena pembatasan lisensi, mereka memutuskan untuk menolak. Sebagai hasilnya, kami membuat disk virtual dan mengunggah tumpukan ubin ke beberapa puluh gigabyte di sana, tetapi semuanya sudah dekat dan tidak melambat. Benar, setiap enam bulan sekali Anda harus menyegarkan, biasanya ini bertepatan dengan kelebihan kartu.



Untuk menggabungkan gambar ubin dan peta vektor, Anda perlu tahu bahwa ubin, Google, OpenStreetMap, Bing, Yahoo diwakili dalam proyeksi Mercator (lebih tepatnya WEB MERCATOR , yang merupakan proyeksi ke bola), di mana setiap lapisan yang lebih dalam dua kali lebih detail daripada yang sebelumnya.



Yandex.Maps menggunakan proyeksi ellipsoid Mercator.

Tidak masalah jika Anda dapat menghitung ulang koordinat geografis pada bidang proyeksi dan sebaliknya.

Kami memilih level 17 detail sebagai maksimum. Closer tidak masuk akal karena peningkatan dalam penyimpanan jumlah ubin (setiap tingkat 4 kali lebih besar dari yang sebelumnya), serta konten informasinya yang rendah.

2 ^ 17 * 256 = 33554432 (256 adalah ukuran tepi ubin dalam piksel).


Sekarang kita memiliki alat dasar, kita dapat melanjutkan langsung ke tugas menciptakan rute yang optimal. Kami menghubungkan fasilitas belanja dengan tepi terdekat di grafik jalan, dan kemudian mulai mencari jalur terpendek. Untuk melakukan ini, kami menggunakan variasi algoritma Dijkstra untuk variasi yang habis secara berurutan untuk setiap titik kunjungan. Pada output, kita mendapatkan matriks adjacency ukuran (N + 1) * (N + 1) dengan tak terbatas pada diagonal utama (ring ring), di mana N adalah jumlah titik kunjungan tanpa memperhitungkan titik keluar.

Matriks yang dihasilkan menyimpan jarak minimum di sepanjang jalan di antara semua fasilitas perbelanjaan, yang merupakan masalah salesman keliling yang klasik. Karena kompleksitas algoritmik masalah seperti itu di atas, kami menggunakan metode branch and bound untuk menyelesaikannya. Untuk n <15, ini lengkap, jika tidak, perkiraan kasar terhubung secara mendalam. Pilihannya tentu tidak ideal, tetapi cukup bekerja.

Hasilnya, kami mendapat rute yang dekat dengan jarak optimal dengan perkiraan dalam km. Jika perlu, operator dapat secara manual mengubah rute demi prioritas poin individu.

Solusinya telah bekerja di organisasi selama sekitar 7 tahun, cukup berhasil, meskipun bukan tanpa cacat, baik dalam akurasi maupun dalam kenyamanan. Hasilnya konsisten dengan data pelacakan kendaraan GPS. Menurut perkiraan saya, pengenalan logistik memungkinkan untuk menghemat 10-12% dari dana yang dialokasikan untuk bahan bakar. Program ini dirancang, diluncurkan dan ditemani oleh hanya satu orang - hamba Anda yang rendah hati.

Kepemimpinan konservatif saya tidak ingin “bersinar,” jadi saya menyarankan contoh fiktif tentang rute perhatian.



Tanpa visualisasi, perhitungannya jauh lebih cepat, dan di dalam satu penyelesaian, hampir secara instan.

Setelah bertahun-tahun, kadang-kadang tangan gatal untuk masuk ke dalam kode dan menyalinnya dengan pengalaman baru ke platform baru yang lebih modern, tetapi sejauh ini tidak ada kelayakan ekonomi.

Itu saja yang ingin saya sampaikan kepada Anda, semoga menarik.
Saya minta maaf jika saya tidak akurat di suatu tempat.