Rüzgârlı Postacı Problemi (Windy Postman Problem-WPP): Aslında yönsüz bir
serim üzerinde tanımlanan bu problemde her bir (i-j) ayrıtı için 2 farklı maliyet değeri verilir. Fakat bu ayrıttan bir kere geçilmesi yeterli olur. 2 faklı maliyet değerinin olması şöyle açıklanır. Araç i’den j’ye giderken rüzgâra karşı, j’den i’ye doğru giderken de rüzgârı arkasına alarak hareket ediyorsa, ilkinde daha yüksek maliyetle diğerinde ise daha düşük maliyetle gitmesi söz konusudur. O zaman rotalama problemi şu hâle dönüşür. Toplamda en az seyahat maliyetinin verecek şekilde ve her ayrıttan en az bir kere geçilmesini sağlayacak şekilde araç rotaları nasıl olmalıdır? Problemin ismine bakılarak konunun sadece rüzgârlı havaları ilgilendirdiği  düşünülmemelidir. Örneğin A kenti ovada, B kenti tepede konumlanmışsa, aracın A’dan B’ye gitmesiyle, B’den A’ya gitmesi maliyetleri yine farklı olacaktır. Hatta ikisi de aynı yükseklikte olan 2 kent için birinden diğerine gitme maliyeti kentin popülerliği veya trafik yoğunluğunun olması gibi nedenlerle daha pahalı olabilir. Sonuçta 2 kent arasında sadece bir geçiş yapılması yeterliyken 2 farklı maliyet söz konusu olursa rüzgârlı postacı problemi ortaya çıkar