ปัญหาการกำหนดเส้นทางส่วนโค้ง ( ARP ) เป็นหมวดหมู่ของปัญหาการกำหนดเส้นทางทั่วไป (GRP) ซึ่งรวมถึงปัญหาการกำหนดเส้นทางโหนด (NRP) ด้วย วัตถุประสงค์ใน ARP และ NRP คือการเดินทางผ่านขอบและโหนดของกราฟตามลำดับ^{[ 1 ]}วัตถุประสงค์ของปัญหาการกำหนดเส้นทางส่วนโค้งเกี่ยวข้องกับการลดระยะทางและเวลาทั้งหมดให้เหลือน้อยที่สุด ซึ่งมักเกี่ยวข้องกับการลด เวลา เดินทางเปล่า ให้เหลือน้อยที่สุด ซึ่งเป็นเวลาที่ใช้ในการไปถึงปลายทาง ปัญหาการกำหนดเส้นทางส่วนโค้งสามารถนำไปใช้กับการเก็บขยะการ วางแผนเส้นทาง รถโรงเรียนการส่งพัสดุและหนังสือพิมพ์ การ ละลายน้ำแข็งและการกำจัดหิมะด้วยยานพาหนะบริการฤดูหนาวที่โรยเกลือบนถนน^{[ 2 ]}การส่งจดหมายการบำรุงรักษาเครือข่ายการกวาดถนนการลาดตระเวนของตำรวจและเจ้าหน้าที่รักษาความปลอดภัย^{[ 1 ]}และการไถหิมะ^{[ 3 ] [ 4 ]}ปัญหาการกำหนดเส้นทางส่วนโค้งเป็นปัญหาNP-hardซึ่งแตกต่างจากปัญหาการตรวจสอบเส้นทางที่สามารถแก้ไขได้ในเวลา พหุนาม

สำหรับตัวอย่างในโลกแห่งความเป็นจริงของการแก้ปัญหาการกำหนดเส้นทางส่วนโค้ง Cristina R. Delgado Serna และ Joaquín Pacheco Bonrostro ได้ใช้อัลกอริธึมการประมาณค่าเพื่อค้นหาเส้นทางรถบัสโรงเรียนที่ดีที่สุดในระบบโรงเรียนมัธยมศึกษาของจังหวัดBurgos ประเทศสเปน นักวิจัยได้ลดจำนวนเส้นทางที่ใช้เวลานานกว่า 60 นาทีในการเดินทางก่อน พวกเขายังลดระยะเวลาของเส้นทางที่ยาวที่สุดด้วยจำนวนยานพาหนะสูงสุดที่กำหนดไว้^{[ 5 ]}

มีการขยายความของปัญหาการกำหนดเส้นทางส่วนโค้งที่เกี่ยวข้องกับบุรุษไปรษณีย์หลายคน ตัวอย่างเช่น ปัญหาบุรุษไปรษณีย์ชาวจีน k คน (KCPP)

การจัดตารางเวลาและการกำหนดเส้นทางยานพาหนะอย่างมีประสิทธิภาพสามารถช่วยประหยัดเงินให้กับภาคอุตสาหกรรมและรัฐบาลได้หลายล้านดอลลาร์ในแต่ละปี^{[ 2 ] [ 6 ]}ปัญหาการกำหนดเส้นทางส่วนโค้งมีการประยุกต์ใช้ในการวางแผนรถบัสโรงเรียน การเก็บขยะและของเสียในเมือง การส่งจดหมายและพัสดุโดยบุรุษไปรษณีย์และบริการไปรษณีย์ การโรยเกลือในฤดูหนาวเพื่อรักษาความปลอดภัยบนท้องถนนในฤดูหนาว การไถและกำจัดหิมะ การอ่านมิเตอร์ รวมถึงเทคโนโลยีการอ่านมิเตอร์ด้วยคลื่นความถี่วิทยุระยะไกล การบำรุงรักษาและการกวาดถนน การวางแผนเส้นทางรถลาดตระเวนของตำรวจ และอื่นๆ

ปัญหาการกำหนดเส้นทางพื้นฐานคือ: เมื่อกำหนดชุดของโหนดและ/หรือส่วนโค้งที่จะให้บริการโดยกลุ่มยานพาหนะ ให้ค้นหาเส้นทางสำหรับยานพาหนะแต่ละคันโดยเริ่มต้นและสิ้นสุดที่คลังสินค้า เส้นทางยานพาหนะคือลำดับของจุดหรือโหนด ซึ่งยานพาหนะต้องเดินทางตามลำดับ โดยเริ่มต้นและสิ้นสุดที่คลังสินค้า^{[ 2 ]}

ปัญหาบุรุษไปรษณีย์จีน ( CPP) มีเป้าหมายเพื่อค้นหาวงจรที่มีความยาวน้อยที่สุดสำหรับบุรุษไปรษณีย์คนเดียว CPP กำหนดให้ต้องเดินทางผ่านขอบทั้งหมดหนึ่งครั้ง ในขณะที่ปัญหาบุรุษไปรษณีย์ชนบท (RPP) กำหนดให้ต้องเดินทางผ่านขอบย่อยบางส่วนด้วยวงจรที่มีความยาวน้อยที่สุด^{[ 1 ]}

ปัญหาการกำหนดเส้นทางส่วนโค้งส่งผลกระทบต่อการตัดสินใจวางแผนเชิงกลยุทธ์ ยุทธวิธี และการปฏิบัติงาน บทบาทเชิงกลยุทธ์ของตำแหน่งที่ตั้งคลังสินค้าขึ้นอยู่กับเส้นทางส่วนโค้งที่มีประสิทธิภาพมากที่สุด การตัดสินใจเกี่ยวกับขนาดของกองยานพาหนะและประเภทของยานพาหนะที่มีคุณสมบัติแตกต่างกันนั้นเกี่ยวข้องกับแง่มุมเชิงยุทธวิธีของปัญหาการกำหนดเส้นทางส่วนโค้งในการวิจัยการดำเนินงาน การตัดสินใจเกี่ยวกับการกำหนดเส้นทางและการจัดตารางเวลาเป็นการตัดสินใจวางแผนการปฏิบัติงานในปัญหาการกำหนดเส้นทางส่วนโค้ง การตัดสินใจวางแผนการปฏิบัติงานยังรวมถึงเวลาที่พนักงานใช้ยานพาหนะด้วยการตัดสินใจเกี่ยวกับพนักงาน^{[ 2 ]}การตัดสินใจเกี่ยวกับการกำหนดเส้นทางยานพาหนะสำหรับตำแหน่งที่ตั้งคลังสินค้าขึ้นอยู่กับต้นทุนในการขนส่งวัสดุในพื้นที่ทางภูมิศาสตร์ Bodin และคณะได้ประยุกต์ใช้การกำหนดเส้นทางยานพาหนะกับปัญหาการเรียกใช้บริการรถ^{[ 7 ]}

ในบางสถานการณ์ ชุดของขอบที่ต้องการจะแตกต่างจากขอบในกราฟ ปัญหานี้จำลองโดยปัญหาบุรุษไปรษณีย์ชนบท (RPP) ^{[ 1 ]}โดยที่ขอบที่ต้องการเป็นเซตย่อยของระบบขอบ

การค้นหาวิธีแก้ปัญหาที่มีประสิทธิภาพด้วยข้อมูลจำนวนมากสำหรับปัญหาบุรุษไปรษณีย์จีน (CPP), ปัญหาบุรุษไปรษณีย์ลมแรง (WPP), ปัญหาบุรุษไปรษณีย์ชนบท (RPP), ปัญหาบุรุษไปรษณีย์จีน kตัว (KCPP), ปัญหาบุรุษไปรษณีย์จีนแบบผสม (MCPP), ปัญหาบุรุษไปรษณีย์จีนแบบมีทิศทาง (DCPP), ^{[ 8 ]}ปัญหาการไถนาลงเนิน (DPP), ปัญหาการไถนาที่มีลำดับความสำคัญ (PPP), ปัญหาบุรุษไปรษณีย์ชนบทลมแรง (WRPP) และปัญหาการกำหนดเส้นทางทั่วไปลมแรง (WGRP) จำเป็นต้องใช้แนวคิดทางคณิตศาสตร์ที่รอบคอบ รวมถึงวิธีการเพิ่มประสิทธิภาพแบบฮิวริสติกวิธีการแตกกิ่งและขอบเขตการเขียนโปรแกรมเชิงเส้นจำนวนเต็มและการประยุกต์ใช้ อัลกอริทึม ปัญหาพนักงานขายเดินทางเช่นอัลกอริทึม Held–Karpทำให้เกิดการปรับปรุงจาก[ ^{9 ] นอกจาก}อัลกอริทึมเหล่านี้แล้ว ปัญหาเหล่านี้ยังสามารถแก้ไขได้ด้วยอัลกอริทึมระนาบตัดการเพิ่มประสิทธิภาพแบบนูนเปลือกนูน ตัวคูณลากรางจ์และวิธีการเขียนโปรแกรมแบบไดนามิก อื่น ๆ ในกรณีที่ไม่สามารถใช้อัลกอริธึม Held–Karp ได้เนื่องจากมีความซับซ้อนในการคำนวณสูง อัลกอริธึมเช่นนี้สามารถใช้เพื่อประมาณคำตอบได้ภายในระยะเวลาที่เหมาะสม^{[ 10 ]}${\displaystyle O(n!)}$${\displaystyle O(2^{n}n^{2})}$

เอกสารอ้างอิงที่เก่าแก่ที่สุดเกี่ยวกับปัญหาการกำหนดเส้นทางส่วนโค้งคือ ความท้าทาย สะพานคลาสสิกของเคอนิกส์เบิร์กซึ่งออยเลอร์พิสูจน์แล้วว่าเป็นไปไม่ได้^{[ 4 ]}ผู้อยู่อาศัยในเคอนิกส์เบิร์กซึ่งปัจจุบันเป็นส่วนหนึ่งของคาลินินกราดต้องการหาวิธีข้ามสะพานทั้งเจ็ดแห่งเหนือแม่น้ำเพรเกลโดยไม่ต้องย้อนกลับหรือย้อนรอย นั่นคือข้ามสะพานแต่ละแห่งเพียงครั้งเดียวเท่านั้น ในปี 1736 ออยเลอร์ลดปัญหาลงเหลือเพียงคำถามเกี่ยวกับจุดและขอบ และแสดงให้เห็นว่าปัญหานี้เป็นไปไม่ได้ ในปี 1873 ฮีร์โฮลเซอร์ได้ทำงานเพิ่มเติมเกี่ยวกับคำถามของวงจรปิด^{[ 4 ]}

งานเกี่ยวกับวงจรออยเลอร์ได้รับความนิยมจากScientific Americanเมื่อวันที่ 1 กรกฎาคม พ.ศ. 2496 ^{[ 11 ]}งานนี้ได้รับการต่อยอดโดย Meigu Guan หรือที่รู้จักกันในชื่อ Kwan Mei-Ko ที่วิทยาลัยครู Shangtun Meigu Guan สนใจในคำถามที่แตกต่างออกไปแทนที่จะหาวงจรปิด Guan ทำงานเพื่อหาเส้นทางเดินที่มีความยาวน้อยที่สุดที่ผ่านขอบทุกด้านของกราฟอย่างน้อยหนึ่งครั้ง Guan อธิบายเป้าหมายของเขาในปี พ.ศ. 2505 ว่า "บุรุษไปรษณีย์ต้องทำงานในส่วนที่ได้รับมอบหมายให้เสร็จก่อนที่จะกลับไปที่ทำการไปรษณีย์ ปัญหาคือการหาเส้นทางเดินที่สั้นที่สุดสำหรับบุรุษไปรษณีย์" ^{[ 4 ]}

ปัญหาการกำหนดเส้นทางส่วนโค้ง (ARPs) มีความแตกต่างกันในเป้าหมายและวิธีการแก้ปัญหา แต่ทั้งหมดเป็นที่ทราบกันดีว่าเป็นปัญหาNP- hard

ปัญหานี้มีชื่อมาจากบุรุษไปรษณีย์และความท้าทายของเขาในการส่งจดหมายตามลำดับใดก็ได้ที่เขาเลือก แต่ต้องลดต้นทุนให้น้อยที่สุด เช่น เวลาหรือระยะทางในการเดินทาง บางครั้งก็เรียกว่าปัญหาบุรุษไปรษณีย์จีนแบบไม่กำหนดทิศทางปัญหาบุรุษไปรษณีย์ชนบทแบบไม่กำหนดทิศทาง (URPP) มีเป้าหมายเพื่อลดต้นทุนรวมของเส้นทางที่ครอบคลุมเครือข่ายทั้งหมด หรือในกรณีที่เฉพาะเจาะจงมากขึ้น เส้นทางที่ครอบคลุมทุกขอบที่ต้องการบริการ หากต้องครอบคลุมเครือข่ายทั้งหมด เส้นทางที่ครอบคลุมเครือข่ายทั้งหมดเรียกว่าเส้นทางครอบคลุมในกรณีที่ต้องครอบคลุมเฉพาะขอบบางส่วนเท่านั้น ปัญหามีเป้าหมายเพื่อหาเส้นทางที่เหมาะสมที่สุดกับความต้องการ โดยข้ามไปยังเส้นทางที่ไม่จำเป็นให้น้อยที่สุด ^{[ 12 ]}

ปัญหาการกำหนดเส้นทางส่วนโค้งแบบไม่มีทิศทางที่มีความจุประกอบด้วยความต้องการที่วางไว้บนขอบ และแต่ละขอบต้องตอบสนองความต้องการนั้น ตัวอย่างเช่น การเก็บขยะ ซึ่งแต่ละเส้นทางอาจต้องการทั้งการเก็บขยะและการเก็บวัสดุรีไซเคิล ปัญหาในการใช้งานจริงอาจเกิดขึ้นได้หากมีปัญหาเรื่องเวลา เช่น กรณีที่บางเส้นทางไม่สามารถให้บริการได้เนื่องจากความขัดแย้งด้านเวลาหรือการจัดตารางเวลา หรือข้อจำกัด เช่น ระยะเวลาที่จำกัด ฮิวริสติกที่อธิบายไว้ในบทความนี้จะไม่สนใจปัญหาดังกล่าวที่เกิดขึ้นเนื่องจากข้อจำกัดของแอปพลิเคชัน ^{[ 12 ]}

ปัญหา URPP ถูกนำเสนอครั้งแรกในปี 1974 และได้รับการพิสูจน์ว่าเป็นปัญหา NP-hard โดยLenstraและKanปัญหา UCARP สามารถพัฒนามาจาก URPP ได้ ดังนั้นจึงเป็นปัญหา NP-hard เช่นกัน ในปี 1981 นักวิทยาศาสตร์คอมพิวเตอร์อีกคู่หนึ่งคือ Golden และ Wong สามารถพิสูจน์ได้ว่าแม้แต่การหาค่าประมาณ 0.5 ของ URPP ก็ยังเป็นปัญหา NP-hard ในปี 2000 Dror ได้ตีพิมพ์หนังสือที่อธิบายปัญหาการกำหนดเส้นทางส่วนโค้งต่างๆ

ปัญหาบุรุษไปรษณีย์ลมแรงที่เสนอโดย Minieka เป็นรูปแบบหนึ่งของปัญหาการตรวจสอบเส้นทางซึ่งอินพุตเป็นกราฟแบบไม่มีทิศทาง แต่ละขอบอาจมีต้นทุนที่แตกต่างกันสำหรับการเดินทางในทิศทางหนึ่งเมื่อเทียบกับการเดินทางในอีกทิศทางหนึ่ง^{[ 13 ]}ตรงกันข้ามกับวิธีแก้ปัญหาสำหรับกราฟแบบมีทิศทางและไม่มีทิศทาง ปัญหานี้เป็นปัญหาNP-complete [ ^{14 ] [ 15 ] ต้นทุน}ในการเดินทางในทิศทางหนึ่งจะมากกว่าเมื่อลมพัดเข้าหน้ามากกว่าเมื่อลมพัดอยู่ด้านหลัง และนี่คือที่มาของชื่อปัญหาบุรุษไปรษณีย์ลมแรง งานที่ใช้ในการเดินทางบนถนนในทิศทางหนึ่งจะแตกต่างจากงานที่ใช้ในการเดินทางบนถนนในอีกทิศทางหนึ่งในวันที่ลมแรง^{[ 8 ]}

ปัญหาบุรุษไปรษณีย์ลมแรงเป็นปัญหาการกำหนดเส้นทางส่วนโค้ง (ARP) ที่ประกอบด้วยปัญหาบุรุษไปรษณีย์จีนแบบผสม (MCPP) เป็นกรณีพิเศษ^{[ 16 ]}

ปัญหาสามารถกำหนดได้ดังนี้: "กำหนดให้กราฟ G=(V,E) ที่ไม่มีทิศทางและเชื่อมต่อกัน โดยมีค่าใช้จ่ายที่ไม่เป็นลบสองค่าและเกี่ยวข้องกับขอบแต่ละด้านที่สอดคล้องกับค่าใช้จ่ายในการเดินทางจาก i ไป j และจาก j ไป i ตามลำดับ ปัญหา WPP คือการค้นหาเส้นทางที่มีต้นทุนต่ำสุดบน G โดยเดินทางผ่านขอบแต่ละด้านอย่างน้อยหนึ่งครั้ง" ^{[ 16 ]}ปัญหานี้ได้รับการแนะนำโดย Minieka โดยทั่วไปแล้ว WPP เป็นปัญหา NP-complete และสามารถแก้ไขได้ในเวลาพหุนามหาก G เป็นกราฟออยเลอร์ หากค่าใช้จ่ายของทิศทางตรงข้ามสองทิศทางของทุกวงจรใน G เท่ากัน หรือหาก G เป็นกราฟแบบอนุกรม-ขนาน ปัญหา Windy Rural Postman Problem (WRPP) เป็นการขยายความของ WPP ซึ่งไม่จำเป็นต้องเดินทางผ่านขอบทั้งหมดในกราฟ แต่เฉพาะขอบที่อยู่ในเซตย่อยที่กำหนดของขอบที่จำเป็นเท่านั้น ตัวอย่างเช่น ถนนในชนบทบางสายไม่จำเป็นสำหรับบุรุษไปรษณีย์ที่จะต้องข้าม และถนนบางสายบนเนินเขาสูงชันใช้เวลานานกว่าในการขึ้นมากกว่าลง^{[ 10 ]}${\displaystyle c_{i,j}}$${\displaystyle c_{j,i}}$${\displaystyle \{i,j\}\in E}$

ปัญหาบุรุษไปรษณีย์ชนบทที่มีลมแรง (WRPP) เป็นการขยายความของ WPP ซึ่งไม่จำเป็นต้องเดินทางผ่านขอบทั้งหมดในกราฟ แต่เดินทางผ่านเฉพาะขอบในกลุ่มย่อยที่กำหนดเท่านั้น ตัวอย่างเช่น ถนนในชนบทบางเส้นไม่จำเป็นสำหรับบุรุษไปรษณีย์ที่จะต้องข้าม และถนนบางเส้นบนเนินเขาชันใช้เวลานานกว่าในการขึ้นมากกว่าลง^{[ 10 ]}พิจารณากราฟแบบไม่มีทิศทางที่มีค่าใช้จ่ายสองค่าและเกี่ยวข้องกับค่าใช้จ่ายในการเดินทางผ่านขอบที่เริ่มต้นจาก i และ j ตามลำดับ G คือกราฟที่มีลมแรง และเราสนใจกลุ่มย่อยของขอบ หรือในสัญลักษณ์ทางคณิตศาสตร์ ${\displaystyle G=\{E,V\}}$${\displaystyle c_{ij}}$${\displaystyle c_{ji}}$${\displaystyle (i,j)}$${\displaystyle E_{R}\subseteq E}$

หาก WRPP มีข้อจำกัดเพิ่มเติมว่าต้องเยี่ยมชมจุดยอดชุดหนึ่งปัญหาจะกลายเป็นปัญหาการกำหนดเส้นทางทั่วไปของลม (WGRP) Benavent เสนอสูตรการเขียนโปรแกรมเชิงเส้นจำนวนเต็มและฮิวริสติกส์และขอบเขตล่างที่แตกต่างกันสำหรับ WRPP ^{[ 9 ]}${\displaystyle V_{R}\subseteq V}$

Benavent และคณะได้ตีพิมพ์การประเมินวิธีการฮิวริสติกหลายวิธีที่ใช้ในการแก้ปัญหา WRPP ในเวลาไม่กี่วินาที โดยมีความคลาดเคลื่อนไม่เกิน 1% จากขอบเขตล่างบนกราฟขนาดกลาง พวกเขาปรับปรุงสิ่งนี้ด้วยอัลกอริทึมการค้นหา แบบกระจาย (Scatter Search ) ซึ่งลดความแตกต่างลงเหลือ 0.5% การค้นหาแบบกระจายพบวิธีแก้ปัญหาที่มีความคลาดเคลื่อนน้อยกว่า 2% เมื่อนำไปใช้กับเครือข่ายที่มีโหนดหลายร้อยโหนดและขอบหลายพันเส้น^{[ 9 ]}

ในแอปพลิเคชันในโลกแห่งความเป็นจริง มีรถหลายคันที่สามารถเคลื่อนที่ได้ ซึ่งนำไปสู่การสร้างแบบจำลองทั่วไปที่เรียกว่า ปัญหาคนส่งไปรษณีย์ชนบทที่มีลมแรงและจำนวนรถ K คันแบบหาค่าต่ำสุดและสูงสุด (Min-Max Windy Rural Postman Problem: MM K-WRPP) ปัญหาคนส่งไปรษณีย์ชนบทที่มีลมแรงและจำนวนรถ K คันแบบหาค่าต่ำสุดและสูงสุด (MM K-WRPP) ถูกกำหนดไว้ดังนี้: กำหนดให้กราฟที่มีลมแรงจุดยอดที่โดดเด่นซึ่งแทนสถานีขนส่ง ชุดย่อยของขอบที่จำเป็น และจำนวนรถ K คันที่กำหนดไว้ ปัญหา MM K-WRPP ประกอบด้วยการค้นหาชุดเส้นทาง K เส้นทางสำหรับรถแต่ละคัน โดยที่แต่ละเส้นทางเริ่มต้นและสิ้นสุดที่สถานีขนส่ง และแต่ละขอบที่จำเป็นมีรถเพียงคันเดียวให้บริการ เป้าหมายคือการลดความยาวของเส้นทางที่ยาวที่สุดให้เหลือน้อยที่สุด เพื่อค้นหาชุดเส้นทางที่สมดุลสำหรับรถแต่ละคัน การประยุกต์ใช้ในชีวิตจริงของปัญหาการกำหนดเส้นทางด้วยวัตถุประสงค์ขั้นต่ำ-สูงสุด ได้แก่ การกำหนดเส้นทางรถโรงเรียน (Delgado และ Pacheco 2001) การส่งหนังสือพิมพ์ให้ลูกค้า (Applegate et al. 2002) และการเก็บขยะ (Lacomme et al. 2004) ^{[ 10 ]}${\displaystyle G=\{V,E\}}$${\displaystyle 1\in V}$${\displaystyle E_{R}\subseteq E}$

อัลกอริทึม MM K_WRPP ที่ดีที่สุดนั้นใกล้เคียงกับค่าต่ำสุดมากเมื่อมีรถ 2 และ 3 คัน โดยมีความคลาดเคลื่อนเฉลี่ยน้อยกว่า 0.4% ส่วนความคลาดเคลื่อนจะเพิ่มขึ้นเป็นประมาณ 1.00% และ 1.60% เมื่อมีรถ 4 และ 5 คัน

ตามที่ Dussault และคณะ และ Benavent และคณะ กล่าวไว้ อัลกอริทึมการจำลองการอบอ่อนแบบหลายวัตถุประสงค์ของเมตาฮิวริสติกส์ (MOSA) สามารถแก้ปัญหาข้อจำกัดต่างๆ ที่กำหนดไว้ใน WRPP ได้ WRPP เป็นปัญหาการกำหนดเส้นทางส่วนโค้งที่สำคัญ ซึ่งเป็นการขยายปัญหาการกำหนดเส้นทางส่วนโค้งของยานพาหนะเดี่ยวหลายๆ ปัญหา ในการประยุกต์ใช้คณิตศาสตร์ในทางปฏิบัติ วิธีแก้ปัญหาที่ลดต้นทุนรวมของเส้นทางยานพาหนะทั้งหมดและความยาวของเส้นทางที่ยาวที่สุดให้เหลือน้อยที่สุดนั้นเป็นที่ต้องการมากกว่า การอยู่ในสถานที่ที่พัสดุของคุณล่าช้าเป็นเวลาหลายชั่วโมงนั้นเป็นเรื่องยาก^{[ 8 ]} เราควรเริ่มต้นด้วยสมมติฐานที่ว่ายานพาหนะหลายคันที่มีความจุที่วัดได้เฉพาะเพื่อให้บริการลูกค้านั้นสมจริงกว่ายานพาหนะคันเดียวที่มีความจุอนันต์ที่วัดไม่ได้ Rabbani และคณะ ได้วัดประสิทธิภาพของอัลกอริทึมและแบบจำลอง MOSA โดยใช้การพัฒนาแบบหลายวัตถุประสงค์ของการค้นหาแบบนกกาเหว่า ซึ่งพัฒนาโดย Yang และคณะ^{[ 17 ]}หรือที่เรียกว่าการค้นหาแบบนกกาเหว่าหลายวัตถุประสงค์และย่อว่า MOCS ^{[ 8 ]}พวกเขาสรุปว่าวิธีการ MOSA มีประสิทธิภาพมากกว่าวิธีการ MOCS ในอนาคตอาจมีการวิจัยเปรียบเทียบกับวิธีการเมตาฮิวริสติกอื่นๆ รวมถึง Non-dominated Sorting Genetic Algorithm (NSGA-), multi-objective particle swarm optimization algorithm (MOPSO) และ multi-objective Imperialist Competitive Algorithm

ในแบบจำลองปัญหาบุรุษไปรษณีย์ลมแรง (WPP) ต้นทุนในการเดินทางในทิศทางหนึ่งจะแตกต่างจากต้นทุนในการเดินทางในอีกทิศทางหนึ่ง ตัวอย่างเช่น หากลมพัดไปตามถนน การเดินทางทวนลมจะใช้เวลาและพลังงานมากกว่าการเดินทางตามลม อีกตัวอย่างหนึ่งของ WPP คือ ต้นทุนในการไถขึ้นเนินจะมากกว่าต้นทุนในการไถลงเนิน^{[ 3 ]}แบบจำลองนี้ใช้รูปแบบที่ศึกษาโดย Dussault et al ซึ่งก็คือปัญหาการไถลงเนิน (DPP) ^{[ 3 ]}

Angel Corberan ได้เผยแพร่อัลกอริทึม branch and cut สำหรับปัญหา windy postman อัลกอริทึมนี้ใช้พื้นฐานจากวิธีการเชิงฮิวริสติกและแม่นยำในการจัดการกับการละเมิดความไม่เท่าเทียมกันของการตัดคี่^{[ 16 ]}

ปัญหาเชิงการจัดเรียงต่างๆ ได้ถูกลดทอนให้เหลือเพียงปัญหาบุรุษไปรษณีย์จีน ซึ่งรวมถึงการหาการตัดสูงสุดในกราฟระนาบและวงจรความยาวเฉลี่ยต่ำสุดในกราฟที่ไม่มีทิศทาง^{[ 18 ]}

ในฤดูหนาว คำถามทั่วไปคือชุดเส้นทางใดที่มีความยาวเส้นทางสูงสุดน้อยที่สุด (ต่ำสุด) โดยทั่วไปแล้ว ปัญหานี้จะถูกประเมินเป็นปัญหาการกำหนดเส้นทางส่วนโค้งด้วยกราฟ เวลาที่ใช้ในการเดินทางบนถนน ซึ่งเรียกว่าเวลาเดินทางเปล่า จะเร็วกว่าเวลาที่ใช้ในการไถหิมะออกจากถนน (หรือส่งจดหมายหรือส่งพัสดุ) อีกแง่มุมหนึ่งที่ต้องพิจารณาเมื่อนำการกำหนดเส้นทางส่วนโค้งมาใช้ในการไถหิมะคือข้อเท็จจริงที่ว่าบนถนนที่ลาดชัน การไถขึ้นเนินนั้นทำได้ยากหรือเป็นไปไม่ได้เลย วัตถุประสงค์คือเส้นทางที่หลีกเลี่ยงการไถขึ้นเนินบนถนนที่ลาดชัน ซึ่งจะทำให้งานเสร็จเร็วขึ้นโดยการเพิ่มเวลาเดินทางเปล่าให้สูงสุดเพื่อไปยังตำแหน่งที่ต้องการ ปัญหานี้ได้รับการจำลองด้วยอัลกอริทึมแบบฮิวริสติกที่ประมาณค่าขอบล่างโดย Dussault, Golden และ Wasil ^{[ 3 ]}นี่คือปัญหาการไถลงเนิน (DPP) ทีมไถหิมะชอบไถลงเนินและไถขึ้นเนินโดยไม่มีรถวิ่ง ปัญหานี้สมมติว่าสภาพการณ์รุนแรงมากจนถนนถูกปิดและไม่มีการจราจร

ปัญหาการไถหิมะลงเนิน (Downhill Plowing Problem หรือ DPP) ละเลยปัญหาการไถหิมะโดยมีลำดับความสำคัญ (Plowing with Precedence Problem หรือ PPP) ซึ่งสร้างขึ้นบนสมมติฐานที่สมเหตุสมผลว่า หากหิมะลึกเกินไป รถไถหิมะจะไม่สามารถไถหิมะในถนนที่ยังไม่ได้ไถได้ DPP สมมติว่าระดับหิมะต่ำพอที่จะสามารถไถหิมะในถนนที่ยังไม่ได้ไถได้ แต่หิมะลึกพอที่จะไม่มีการจราจร หากมีการจราจรบนถนน สมมติฐานที่ว่าไม่สามารถไถหิมะขึ้นเนินได้ก็จะไม่เป็นจริงอีกต่อไป การจำลองสำหรับ DPP พบว่ามีการไถหิมะในถนนที่ยังไม่ได้ไถประมาณ 5% ของเวลา ซึ่งเป็นหัวข้อสำหรับการวิจัยทฤษฎีกราฟและการกำหนดเส้นทางส่วนโค้งในอนาคต

พิจารณากราฟแบบไม่มีทิศทางโดยที่เป็นเซตของจุดยอดและจุดโหนด และเป็นเซตของส่วนโค้ง แต่ละส่วนโค้งที่แสดงด้วยมีค่าใช้จ่ายสี่อย่าง ได้แก่ซึ่งกำหนดให้เป็นค่าใช้จ่ายในการไถจากไป, , ค่าใช้จ่ายในการไถจากไป, , ค่าใช้จ่ายในการเดินทางเปล่าจากไป, และ, ค่าใช้จ่ายในการเดินทางเปล่าจากไปการตั้งค่านี้สมมติว่ามีระดับความสูงที่สูงกว่าซึ่งนำไปสู่ข้อความ: ในทางปฏิบัติ เวลาในการไถลงเนินมีประสิทธิภาพมากกว่าการไถขึ้นเนินสองเท่า และการเดินทางเปล่ามีประสิทธิภาพมากกว่าการไถสองเท่า อัลกอริทึมจะค้นหาเส้นทางที่จะเริ่มต้นและสิ้นสุดที่สถานีและไถส่วนโค้งสองครั้งเนื่องจากด้านซ้ายและด้านขวาของถนนต้องใช้การไถสองรอบ ${\displaystyle G=\{V,A\}}$${\displaystyle V}$${\displaystyle A}$${\displaystyle (v_{i},v_{j})}$${\displaystyle c_{ij}^{+}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle c_{ji}^{+}}$${\displaystyle v_{j}}$${\displaystyle v_{i}}$${\displaystyle c_{ij}^{-}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle c_{ji}^{-}}$${\displaystyle v_{j}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle v_{i}}$${\displaystyle c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}}$${\displaystyle k}$${\displaystyle v_{0}}$

วิธีแก้ปัญหาที่ดีที่สุดคือการลดความยาวเส้นทางสูงสุดให้เหลือน้อยที่สุด Dussault, Golden และ Wasil พบอัลกอริทึมที่ไม่เกินขอบเขตล่าง 5.5% ในการทดสอบมากกว่า 80 ครั้ง ความเบี่ยงเบนเพิ่มขึ้นเมื่อความซับซ้อนของแบบจำลองเพิ่มขึ้น เนื่องจากมีการประมาณค่าที่ไม่ได้รับการปรับให้เหมาะสมมากกว่าการประมาณค่าที่ได้รับการปรับให้เหมาะสมเมื่อแบบจำลองมีขนาดใหญ่ขึ้น การปรับปรุงอัลกอริทึม DPP ของ Dussault และคณะ อาจมีบทลงโทษสำหรับการกลับรถ การเลี้ยวซ้าย หรือการตรงไปข้ามทางแยก ซึ่งจะใช้เวลาเพิ่มเติมและผลักหิมะไปอยู่กลางทางแยกตามลำดับ (ดูปัญหา Directed Rural Postman Problem with Turn Penalties ซึ่งมักเรียกกันว่า DRPP-TP ด้านล่าง)

ปัญหาk -Chinese Postman สามารถระบุได้ดังนี้: "กำหนดกราฟG ที่มีน้ำหนักขอบเชื่อมต่อกัน และจำนวนเต็มpและkตัดสินใจว่ามีทางเดินปิดอย่างน้อยkทางเดินหรือไม่ โดยที่ขอบทุกขอบของGอยู่ในทางเดินอย่างน้อยหนึ่งทาง และน้ำหนักรวมของขอบในทางเดินมีค่าไม่เกินp ?" กระบวนการในการหาคำตอบของk -CPP เป็นปัญหา NP-complete Gutin, Muciaccia และ Yeo พิสูจน์ในปี 2013 ว่าk -CPP สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่^{[ 19 ]}ผู้เขียนพิสูจน์ว่าk -CPP ยอมรับเคอร์เนลที่มีจุดยอด และเวอร์ชันแบบมีทิศทางของk -CPP เป็นปัญหา NP-complete ${\displaystyle O(k^{2}\log(k))}$

ปัญหาไปรษณีย์ชนบท (RPP) กำหนดให้บางเส้นทางเป็นเส้นทางบังคับและแน่นอน แต่ผู้ที่เดินทางผ่านกราฟไม่จำเป็นต้องไปในทิศทางใดทิศทางหนึ่งโดยเฉพาะ RPP เป็นปัญหา NP-hard และสมบูรณ์ เช่นเดียวกับ kCPP, DPP และ PPP ซึ่งเป็นปัญหา NP-hard Benevant ได้ศึกษาการวางนัยทั่วไปของปัญหานี้ในชื่อปัญหาไปรษณีย์ชนบทแบบมีทิศทางพร้อมบทลงโทษการเลี้ยว (DRPP-TP) ^{[ 20 ]}อัลกอริทึมของ Benevant ประมาณค่าคำตอบโดยการแปลง DRPP-TP ให้เป็นปัญหาพนักงานขายเดินทางแบบไม่สมมาตร (ATSP)

อัลกอริทึมส่วนใหญ่จำเป็นต้องมีการประมวลผลกราฟล่วงหน้า ซึ่งจะช่วยลดความซับซ้อนของกราฟเริ่มต้นโดยการลบขอบทั้งหมดที่ไม่ใช่เส้นทางที่สั้นที่สุดระหว่างขอบสองขอบที่ต้องการ การลดความซับซ้อนอีกอย่างที่การประมวลผลล่วงหน้าเพิ่มเข้ามาคือ การแปลงเส้นทางที่สั้นที่สุดระหว่างขอบสองขอบที่ต้องการให้เป็นขอบเดียวที่ไม่จำเป็น โดยไม่คำนึงถึงจำนวนขอบในเส้นทางนั้น ตราบใดที่ไม่มีขอบที่จำเป็นอยู่ในเส้นทางนั้น

เมื่อทำการประมวลผลเบื้องต้นเสร็จแล้ว ปัญหาดังกล่าวสามารถสรุปได้เป็น ปัญหา การหาขอบนูนโดยที่ขอบจะเป็นจุดของขอบนูน ปัญหาการหาขอบนูนสามารถแก้ไขได้โดยใช้การเขียนโปรแกรมเชิงเส้นหรือโดยใช้อัลกอริธึมการหาขอบนูน แต่กระบวนการหาขอบนูนนั้นเป็นปัญหาแบบเลขชี้กำลัง

วิธีการแก้ปัญหา URPP หลังจากการประมวลผลล่วงหน้าเสร็จสิ้นแล้ว ประกอบด้วยอัลกอริทึมระนาบตัดและระเบียบ วิธีแยกสาขาและตัด^{[ 21 ]}

นี่คือรายการความซับซ้อนในการคำนวณสำหรับปัญหาการกำหนดเส้นทางส่วนโค้งแบบต่างๆ

ตัวแปร CP	ความซับซ้อนแบบคลาสสิก	การประมาณค่า	ความซับซ้อนแบบพารามิเตอร์
ไม่มีทิศทาง	${\displaystyle O(|V|^{3})}$อัลกอริทึมเวลา[ 22 ]
กำกับ	${\displaystyle O(|V|^{3})}$อัลกอริทึมเวลา[ 22 ] ${\displaystyle O((|E|-|V|)|V|^{2})}$-อัลกอริทึมเวลา[ 23 ]
ผสม	NP-สมบูรณ์[ 24 ] ${\displaystyle O(|V|^{3})}$-สามารถแก้ได้ในเวลาที่กำหนดหากแต่ละจุดยอดมีดีกรีคู่[ 22 ]	${\displaystyle O(\max\{|V|^{3},|A|(\max\{|A|,|E|\})^{2}\})}$-ปัจจัยเวลา 3/2 [ 25 ]	${\displaystyle O(2^{|E|}\cdot |V|^{3})}$อัลกอริทึมเวลา[ 26 ] ใน FPT ที่เกี่ยวข้องกับ |A| [ 26 ] ใน XP ที่เกี่ยวข้องกับ treewidth [ 27 ]
ลมแรง	NP-สมบูรณ์[ 28 ] P ในบางกรณีพิเศษ[ 28 ] [ 29 ]	ปัจจัย 3/2 [ 30 ]
k-ลำดับชั้น	NP-สมบูรณ์[ 31 ] ${\displaystyle O(k|V|^{4})}$- แก้ปัญหาได้หากความสัมพันธ์เชิงลำดับขั้นเป็นแบบเชิงเส้น
ผลรวมขั้นต่ำ k บุรุษไปรษณีย์	${\displaystyle O(|V|^{3})}$-อัลกอริทึมเวลาที่มีจุดยอดที่ทำการไปรษณีย์[ 32 ]มิฉะนั้นจะเป็น NP-complete [ 33 ]		ใน FPT ที่เกี่ยวข้องกับ k โดยไม่มีจุดยอดที่ทำการไปรษณีย์[ 34 ]
มินิ-แม็กซ์ k บุรุษไปรษณีย์	NP-สมบูรณ์[ 35 ]	${\displaystyle O(|V|^{3})}$-ปัจจัยเวลา(2-1/k) [ 35 ]

• หน้าค้นหาปัญหาการกำหนดเส้นทางส่วนโค้งที่มหาวิทยาลัยแลงแคสเตอร์
• แนวโน้มในการกำหนดเส้นทางส่วนโค้ง

• ปัญหาบุรุษไปรษณีย์จีน  – การหาเส้นทางเดินที่สั้นที่สุดผ่านขอบทั้งหมดของกราฟหน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• ปัญหาการกำหนดเส้นทางยานพาหนะ  – ปัญหาการหาค่าที่เหมาะสมที่สุด
• ปัญหาพนักงานขายเดินทาง  – ปัญหา NP-hard ในการเพิ่มประสิทธิภาพเชิงการจัดเรียง
• เส้นทางออยเลอร์  – เส้นทางในกราฟที่ผ่านขอบแต่ละด้านเพียงครั้งเดียว
• ปัญหาการกำหนดเส้นทางส่วนโค้งที่มีความจุ
• รายการปัญหาทฤษฎีกราฟ  – สาขาคณิตศาสตร์เชิงดิสครีตหน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• ปัญหาการกำหนดเส้นทางรถไถหิมะ  – การประยุกต์ใช้ปัญหาการกำหนดเส้นทางส่วนโค้งและยานพาหนะในการกำจัดหิมะ
• รายการความซับซ้อนของปัญหาบุรุษไปรษณีย์จีน  – หมวดหมู่ของปัญหาการกำหนดเส้นทางที่ลดระยะทางและเวลาโดยรวมให้น้อยที่สุดหน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง