Çoklu Çinli Postacı Problemi (k-Chinese Postman Problem-kCPP): k tane gezginin
olduğu ve gezginler için kapasite sınırının olmadığı durumdur. Bu problem tıpkı çoklu gezgin satıcı problemi gibidir. Serimde k tane gezgin vardı ve her ayrıtın mutlaka bir gezgin tarafından ziyaret edilmesi gerekir. Amaç, toplamda en az mesafenin kat edilmesini sağlayacak şekilde gezginlerin rotalarını belirlemektir. Gezginlerin turları birbirleriyle kesişebilir. Aslında bu problem için Çinli postacı probleminin genel hâli de denebilir. Bir mahalledeki postaların çok sayıda postacı tarafından dağıtılması buna iyi bir örnek olur.