Pada penelitian ini dirancang suatu metode solusi heuristik untuk menyelesaikan permasalahan Periodic Vehicle Routing Problem with Stochastic Demand pada kasus rural logistics. Tujuannya adalah memperoleh suatu set jadwal distribusi berupa tour apriori harian kendaraan ke sejumlah pengecer selama periode waktu yang memberikan ekspektasi total waktu distribusi paling minimum. Algoritma solusi yang dirancang terdiri atas dua tahapan proses yaitu tahap konstruksi solusi dan tahap perbaikan solusi. Tahap konstruksi solusi dilakukan dengan menggunakan prinsip cluster-first-route-second. Sedangkan tahap perbaikan solusi digunakan strategi eksploratif dan strategi eksploitatif yang berfungsi mencari tetangga-tetangga solusi yang mungkin lebih baik dari solusi-solusi sementara yang telah berhasil ditemukan pada tahap konstruksi atau tahap perbaikan solusi pada iterasi sebelumnya. Strategi eksploratif terdiri atas dua metode yaitu metode inter-tour circular exchange dan overtime cut-off, sedangkan strategi eksploitatif menggunakan metode intra-tour swap. Pengujian kinerja algoritma solusi hasil rancangan dilakukan menggunakan 27 blok eksperimen hasil kombinasi tiga faktor yang diduga merupakan parameter-parameter yang berpengaruh pada kinerja algoritma solusi. Dengan menggunakan pengaturan parameter pencarian yang tepat, algoritma yang dirancang mampu menunjukkan kinerja yang memuaskan yaitu menghasilkan solusi yang berkualitas baik dengan waktu komputasi yang wajar.