Dalam artikel sebelumnya, saya menggambarkan sebuah algoritma yang memungkinkan Anda untuk membangun rute berjalan yang lebih menarik (bukan yang lebih pendek, seperti yang dilakukan Yandex-Google) antara dua titik. Algoritma memuat pemandangan, taman, dan objek menyenangkan dan menarik lainnya untuk pejalan kaki dari Open Street Map dan meletakkan rute melalui mereka. Hasilnya, jalan bisa 10-20% lebih lama, tetapi jauh lebih indah dan menarik.
Foto City - Alex 'Florstein' Fedorov
Dalam komentar, banyak yang menulis bahwa selain rute antara dua titik, mereka akan tertarik untuk membangun rute melingkar yang akan mulai dan berakhir pada titik yang sama dan sesuai dengan batas waktu yang diberikan. Misalnya, jika Anda memiliki dua jam ke kereta atau bertemu teman, Anda tidak akan punya waktu untuk pergi ke tempat yang jauh selama waktu ini, tetapi sangat mungkin untuk berjalan-jalan dan melihat keindahan di dekatnya.
Setelah beberapa percobaan, saya menyusun algoritma genetika yang membangun rute (untuk saya) yang cukup bagus dalam situasi ini. Di bawah penjelasan kucing tentang prinsip operasi dan beberapa contoh.
Jadi, pengguna ingin dapat melakukan tur singkat di daerah sekitarnya dan kembali ke titik awal dalam waktu yang ditentukan (biasanya 1-2 jam). Ternyata, jenis jalan ini cukup laris. Sebagai contoh, artikel "Pola pergerakan wisatawan dalam suatu tujuan" menggambarkan studi tentang jejak 250 turis di Hong Kong, sementara 40% wisatawan mulai menjelajahi kota dari rute melingkar dalam radius 500 meter dari hotel. Namun, seringkali orang hanya berkeliaran, tidak tahu apa yang menarik dapat dilihat di dekatnya.
Tugasnya rumit jika bukan di pusat wisata (ke mana pun Anda pergi - Anda akan menemukan sesuatu yang menarik di mana-mana), tetapi di suatu tempat di pinggiran di mana Anda perlu mencari pemandangan.
Radius dan pemilihan objek wisata
Untuk membangun rute, pertama-tama kita harus memilih objek wisata yang ingin kita kunjungi. Dan untuk ini, Anda perlu menentukan area pencarian mereka di sekitar titik awal. Jika pengguna menentukan waktu berjalan maksimum dalam M menit, maka titik paling jauh yang dapat Anda capai dan memiliki waktu untuk kembali adalah titik pada jarak (V * M / 2), di mana V adalah kecepatan pejalan kaki.
Kecepatan rata-rata yang disukai pejalan kaki dapat dianggap 1,4 meter per detik. Namun, ketika jalan-jalan seseorang berjalan sedikit lebih lambat, karena ia menghabiskan waktu ekstra untuk tur. Saya membangun beberapa rute di sekitar kota dan berjalan di sepanjang mereka, membandingkan waktu berjalan dengan apa yang diprediksi aplikasi. Hasilnya, ternyata kecepatan berjalan rata-rata saya sekitar 20% lebih sedikit, mis. sekitar 1,1 m / s. Karena saya secara berkala berhenti untuk mengambil gambar, memeriksa peta, kadang-kadang saya menyeberang jalan sekali lagi untuk memilih sudut terbaik atau membeli es krim.
Saya melakukan eksperimen di daerah yang tidak dikenal di kota ini, menggunakan algoritme saya di sana, Anda dapat menemukan segala macam hal menarik yang belum pernah saya dengar sebelumnya. Misalnya, sebuah monumen untuk selebaran pertama.
Memilih tempat menarik pada jarak maksimum akan mengarah pada pembangunan rute melingkar yang merosot. Karena pejalan kaki tidak lagi memiliki waktu untuk keluar dari jalur terpendek dalam garis lurus, ia hanya dapat mengunjungi objek wisata ini, pergi ke sana dan kembali ke jalan yang sama, seperti yang ditunjukkan oleh panah merah.
Di sini kita bisa pergi ke taman lebih jauh, atau mengunjungi beberapa titik sekaligus lebih dekat
Tetapi situasi ini bertentangan dengan ide rute melingkar yang menarik, karena pada kenyataannya kita hanya melihat satu jalan dan satu objek, tetapi saya paling ingin melihat. Oleh karena itu, menurut hasil percobaan, radius yang sama dengan sepertiga dari jarak maksimum dipilih. Dengan jari-jari pencarian ini, pejalan kaki akan memiliki cukup waktu untuk mencapai titik menarik paling jauh di sepanjang jari-jari, kemudian, jika perlu, berjalan pada jarak yang sama di sepanjang akord untuk mencari benda-benda menarik lainnya, dan kemudian kembali dalam waktu.
Masalah pendekatan frontal
Oke, kami telah mengumpulkan daftar objek wisata kandidat. Sekarang tinggal memilih mana dari mereka dan dalam urutan apa kita ingin memeriksanya. Kemungkinan besar, kita tidak akan punya waktu untuk mengunjungi mereka, jadi kita perlu memilih subset yang paling menarik dari mereka.
Pertama, saya mencoba merumuskan dan membangun algoritma sekuensial sederhana. Namun, saya dengan cepat menemukan sejumlah masalah.
Jika kita mempertimbangkan situasi dari gambar di atas, tidak jelas harus mulai dari mana membangun rute. Jika taman adalah yang paling penting, tetapi daya tarik paling jauh, maka mulai dengan itu kita akan mendapatkan versi yang lebih buruk, yang kita tulis sebelumnya.
Solusi jelas berikutnya adalah entah bagaimana mengelompokkan pemandangan dan mencoba mencari jalan menuju kluster yang paling menguntungkan, dan kemudian berjalan di dalamnya. Tapi di sini lagi, semuanya tidak jelas: dari mana cluster untuk memulai, ke mana harus pergi. Anda selalu dapat jatuh ke dalam perangkap dari jenis yang kami salah jalan dan lari ke "gurun" - daerah tanpa pemandangan yang kami tidak punya cukup waktu untuk pergi dan kembali ke titik awal.
Pada titik tertentu, menjadi jelas bagi saya bahwa saya praktis melakukan pekerjaan dari algoritma genetika: Saya menggambar rute yang berbeda pada peta dan mencoba menentukan seberapa besar saya secara pribadi akan menyukainya.
Algoritma genetika
Setelah menerima daftar objek wisata bernomor, algoritma harus memilih subset yang diurutkan, yang akan membentuk dasar dari rute melingkar. Rute terakhir dalam hal ini adalah salah satu lokasi dari banyak atraksi utama (kami tidak ingin pengulangan dan tidak diharuskan untuk menggunakan semua objek yang mungkin).
Mengetahui rumus untuk jumlah penempatan dari n hingga k, kita dapat memperkirakan jumlah opsi yang memungkinkan. Jika kita mempertimbangkan rute sepanjang satu jam di sekitar Palace Square di St. Petersburg, akan ada 54 kandidat untuk atraksi utama setelah penyaringan dan pengelompokan dalam radius 1320 meter (yang didefinisikan seperti dijelaskan di atas).
Bubur infernal dari tumpukan pemandangan di tengah, hasil debug dari area visibilitas yang dihitung sesuai dengan algoritma dari artikel sebelumnya
Prinsip seleksi dan penyortiran dijelaskan dalam artikel sebelumnya, ditambah kami juga menghapus objek dengan minat kurang dari 3 (demi objek kecil seperti itu, seseorang tidak mungkin siap untuk pergi jauh, kecuali tidak ada yang lain di dekatnya). Dengan demikian, kemungkinan jumlah rute dapat dihitung dengan rumus jumlah penempatan dari 54 menjadi 5, yaitu 379501200. Untuk rute 2 jam, dalam radius di mana 151 poin yang diminati sudah jatuh, jumlah ini akan sama dengan 73423236600. Nah, agak terlalu banyak untuk pencarian sederhana.
Kromosom dan operator genetik
Kromosom dalam hal ini adalah garis di mana setiap elemen adalah jumlah daya tarik utama yang sesuai. Untuk tugas-tugas seperti itu di mana kromosom adalah permutasi atau pengaturan, ada varian khusus yang dioptimalkan dari operator genetik. Operator tersebut mempertahankan properti kromosom untuk tetap menjadi permutasi atau penempatan set elemen awal.
- Crossover yang Dipetakan Sebagian (PMX) digunakan untuk persimpangan.
- Untuk mutasi, pertukaran tempat dari dua gen acak (Swap Mutator) digunakan.
Deskripsi operasi operator ini dengan contoh dapat ditemukan, misalnya, dalam pekerjaan "Algoritma genetika untuk masalah salesman keliling: Tinjauan representasi dan operator".
Fungsi kebugaran
Fungsi kebugaran harus mempertimbangkan faktor-faktor berikut untuk membangun rute melingkar yang menarik:
- Total minat semua objek wisata utama yang dikunjungi harus sebesar mungkin.
- Total waktu perjalanan harus sedekat mungkin dengan yang ditentukan pengguna, rute tidak boleh lebih lama atau lebih pendek. Rute pendek hanya diizinkan ketika tidak ada cukup atraksi di dekatnya.
- Rute tidak harus melintasi sendiri. Untuk setiap persimpangan sendiri, kami menambahkan persentase penalti ke nilai total fungsi.
- Bentuk rute harus dekat dengan lingkaran, itu harus menangkap area kota terbesar dan menghindari kasus merosot. Untuk melakukan ini, kami menempatkan fungsi rasio area gambar yang dijelaskan oleh rute ke area lingkaran di mana pemandangan itu dicari.
Ini adalah contoh perjalanan pulang pergi yang baik. Melewati dua taman dan tidak pernah mengunjungi tempat yang sama dua kali
Berikut adalah contoh rute yang jelas-jelas tidak berhasil. Ini berisi cabang jalan buntu, di mana pejalan kaki harus kembali ke jalan yang diperiksa, dan persimpangan diri. Di persimpangan, waktu biasanya terbuang sia-sia untuk memeriksa kembali bagian kota yang sudah terlihat.
Rute buruk sebenarnya diperoleh oleh genetika, di mana titik 3 dan 4 dinonaktifkan untuk fungsi kebugaran (denda untuk penyilangan diri dan untuk area kecil)
Nuansa
Selama pengujian, beberapa nuansa muncul.
Batas waktu terlampaui
Selama pekerjaan genetika, kami menghitung panjang rute sepanjang garis lurus antar titik. Dan setelah kami memilih objek untuk komunikasi menggunakan algoritma genetika, kami mencari jalur di antara mereka menggunakan algoritma dari artikel sebelumnya. Dalam hal ini, jalur mungkin menjadi lebih panjang dan merangkak keluar dari waktu. Lagi pula, di kota sering kali jalur terpendek di sepanjang jalan bisa berkali-kali lebih lama daripada garis lurus.
Rata-rata, perbedaannya biasanya sekitar 10-20% dan kami menempatkannya dalam fungsi kebugaran (mis., Genetika mencari rute dengan margin waktu, yang kemudian dimakan saat meletakkan rute yang rinci). Terkadang itu tidak cukup - Anda harus menghitung ulang rute itu lagi. Kami memiliki tempat-tempat seperti itu di kota-kota di mana perbedaan antara rute "seperti burung" dan "seperti pejalan kaki" adalah kilometer.
Antara titik 50 meter dalam garis lurus, tetapi satu setengah kilometer di sepanjang trotoar dan melewati jalan pintas.
Namun, semua sama, algoritma kadang-kadang melebihi waktu yang ditentukan oleh pengguna, tetapi di sini setiap orang dapat memutuskan untuk dirinya sendiri apakah dia memiliki 10-15 menit tambahan atau jika dia harus menyelesaikan perjalanan lebih awal.
Venesia
Ketika algoritma sudah siap, saya memutuskan untuk menambahkan kota-kota wisata terbaik di Eropa untuk bersenang-senang. Ternyata menarik: kota-kota berbeda di mana-mana, fitur pemetaan di OSM, juga, akibatnya, saya terus-menerus harus menyelesaikan sesuatu.
Secara khusus, pencarian rute sirkular mogok di Venesia. Karena ini adalah contoh unik dari kota dengan wilayah yang tidak terkait - pulau-pulau dipisahkan oleh Grand Canal, yang melaluinya tidak ada jembatan, penyeberangan hanya dimungkinkan dengan feri.
Alhasil, algoritma memilih bagian dari objek di satu sisi selat, sebagian di sisi lain, kemudian tidak bisa menemukan jalur darat di antara mereka dan jatuh. Saya harus menambahkan tanda centang pada pencapaian semua atraksi dari titik awal.
Terkadang Anda masih harus kembali dengan cara yang sama
Dalam contoh dengan taman di atas, ada sepotong rute di mana Anda harus kembali dengan cara yang sama - ini adalah semenanjung kecil di mana berdiri sebuah monumen dengan pesawat terbang. Satu-satunya jalan menuju semenanjung ini, dan akan diperlukan untuk kembali menyertainya. Jadi, pengembalian uang semacam itu tidak dapat sepenuhnya dilarang. Algoritma untuk ini meningkatkan bobot semua sisi yang telah dijelajahi, mengurangi kemungkinan pengembalian di sepanjang sisi, tetapi masih memungkinkan ini terjadi.
Meskipun kadang-kadang masih berfungsi buruk. Misalnya, mereka mengeluh tentang katedral utama di Kaliningrad. Itu terletak di sebuah pulau di tengah sungai yang dilalui jembatan. Dari jembatan ini ada satu turunan dan satu jalur ke katedral, tampaknya algoritme ini menambah bobot jalan satu-satunya ini terlalu banyak, yang membuat pengembaliannya tidak menguntungkan. Akibatnya, ia hampir tidak pernah mengarah ke katedral, meskipun ini adalah salah satu daya tarik utama kota. Itu masih membutuhkan semacam penyempurnaan.
Hasil
Algoritme genetik adalah hal yang sedikit tidak terduga, jadi kadang-kadang buggy dan menarik zig-zag aneh. Namun secara umum, saya puas dengan hasilnya. Apa yang sangat bagus, algoritma bekerja tidak hanya di pusat wisata (di mana tidak masalah untuk bersenang-senang), tetapi juga di pinggiran kota. Di mana, seringkali, tanpa petunjuk, menemukan sesuatu yang menarik sangat sulit.
Bahkan di kantong tidur di barat daya St. Petersburg, Anda dapat menemukan monumen yang cukup untuk berjalan dua jam
Anda dapat mencoba sendiri algoritme di salah satu dari 77 kota yang didukung di situs web Sight Safari kami atau di aplikasi Android kami (ya, kami akhirnya menyelesaikannya).
Sangat menarik bagaimana algoritma ini akan bekerja di kota-kota dengan medan dan ketinggian yang kompleks. Kami menambahkan dukungan untuk analisis ketinggian ke pustaka pathfinder Graphopper, tetapi kami tidak dapat memverifikasi bagaimana seharusnya - Peter adalah kota yang terlalu datar.
Secara umum, coba, tulis ulasan, apakah rute sedang dibangun dengan benar. Anda dapat langsung mengajukan penambahan kota baru.