Optimal Path Finder

Summary

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

Algorithm Capabilities

ไลบรารีของเรามีความสามารถในการสร้าง เส้นทางที่เหมาะสมที่สุดระหว่างสองจุด บนแผนที่ มีคุณสมบัติหลักดังต่อไปนี้:

1. ค้นหาเส้นทางที่เหมาะสมที่สุดบนแผนที่ โดยพิจารณาจากเส้นทางและอุปสรรค: เราคำนึงถึงไม่เพียงแต่ถนนเท่านั้น แต่ยังรวมถึงเส้นทางนอกถนน เช่น เส้นทางเดินป่า ทางเท้า และสิ่งกีดขวางที่อาจส่งผลต่อการเลือกเส้นทางที่เหมาะสมที่สุด

2. ค้นหาเส้นทางที่เหมาะสมที่สุดเฉพาะบนถนนเท่านั้น: หากคุณต้องการค้นหาเส้นทางเฉพาะบนถนน เรามีฟังก์ชันนี้ให้ คุณสมบัตินี้มีประโยชน์ ตัวอย่างเช่น สำหรับยานพาหนะที่จำกัดให้ออกเดินทางบนถนนเท่านั้น

3. การตั้งค่าความเร็วที่แตกต่างกันสำหรับถนน: เรามีความสามารถในการกำหนดความเร็วที่แตกต่างกันให้กับถนนต่างๆ ที่แตกต่างกัน ตัวอย่างเช่น สามารถตั้งค่าความเร็วที่สูงขึ้นสำหรับทางหลวงหลัก และความเร็วที่ต่ำลงสำหรับช่องทางแคบๆ

4. การตั้งค่าสิ่งกีดขวางสี่เหลี่ยมผืนผ้า: คุณสามารถกำหนดสิ่งกีดขวางสี่เหลี่ยมผืนผ้าบนแผนที่ซึ่งจะต้องนำมาพิจารณาเมื่อสร้างเส้นทางที่เหมาะสมที่สุด สิ่งนี้มีประโยชน์เมื่อมีสิ่งกีดขวางที่เป็นที่รู้จัก เช่น อาคารหรือทะเลสาบ (การประมาณค่าของพวกมัน)

5. การจำกัดรัศมีการค้นหาสำหรับถนน: คุณสามารถจำกัดรัศมีการค้นหาสำหรับถนนเพื่อลดเวลาในการค้นหาและมุ่งเน้นเฉพาะในพื้นที่เฉพาะ

6. การควบคุมประสิทธิภาพและความแม่นยำ: เรามีฟังก์ชันให้คุณควบคุมประสิทธิภาพและความแม่นยำของอัลกอริทึม คุณสามารถปรับแต่งเพื่อให้ได้สมดุลที่ต้องการระหว่างความเร็วในการค้นหาและความถูกต้องของการสร้างเส้นทาง

ต่อไป เราจะให้คำอธิบายโดยละเอียดเพิ่มเติมเกี่ยวกับแต่ละคุณสมบัติเหล่านี้ และตรวจสอบตัวอย่างการใช้งาน

Approach to Solution

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

ในการนำไปใช้ เราได้ใช้อัลกอริทึม Lee ที่ปรับปรุงแล้ว เรามีตารางเซลล์บนระนาบ จากจุดเริ่มต้น คลื่นจะแพร่กระจายออกไปใน 8 ทิศทาง (รวมถึงแนวทแยง) ไปยังเซลล์ที่อยู่ใกล้เคียง โดยคำนวณเวลาที่ต้องใช้ในการเข้าถึงแต่ละเซลล์ เซลล์ที่อยู่ใกล้เคียงอาจมีสิ่งกีดขวางหรือถนน ถนนสามารถมีความเร็วที่แตกต่างกัน ดังนั้นเราจึง “ทำเครื่องหมาย” ตารางของเราด้วยเวลาที่ต้องใช้ในการเข้าถึงแต่ละเซลล์จากเซลล์เริ่มต้นภายในรัศมีหนึ่ง หรือจนกว่าจะถึงจุดหมายปลายทาง หากเราไปถึงจุดหมายปลายทาง เราสร้างเส้นทางย้อนกลับโดยใช้ตารางของเรา

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

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

Demo Project on GitHub

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

ตัวอย่างประกอบด้วยขั้นตอนต่อไปนี้:

1. การสร้างรายการข้อมูลถนน (RoadInfo) ซึ่งรวมถึงข้อมูลเกี่ยวกับส่วนของถนน (Segment) และความเร็วในการเคลื่อนที่ (Velocity)
2. เพิ่มถนนที่เร็วกว่าลงในรายการ
3. เพิ่มถนนวงแหวนที่ช้ากว่าลงในรายการ
4. สร้างตัวสร้างชั้นทาง (WayLayerGenerator) และเพิ่มถนนให้กับเครื่องกำเนิดไฟฟ้า
5. ค้นหาเส้นทางหลายเส้นจากจุดเริ่มต้น (startPoint) ไปยังจุดหมายปลายทาง (goalPoint01, goalPoint02, goalPoint03) โดยใช้รัศมีที่ระบุ (radius)
6. เตรียมชั้นถนน (roadsLayer) เพื่อแสดงบนแผนที่ และเพิ่มวัตถุถนน
7. เตรียมชั้นทาง (wayLayer) เพื่อแสดงบนแผนที่ และสร้างวัตถุเรขาคณิตสำหรับแต่ละเส้นทางที่พบ
8. แสดงแผนที่ โดยใช้ฟังก์ชัน ShowMap และบันทึกแผนที่ในพาธที่ระบุ

รหัสนี้สร้างและแสดงเส้นทางถนนบนแผนที่สำหรับจุดที่ระบุโดยใช้ข้อมูลถนนและตัวสร้างชั้นทาง

Search Options

การค้นหาเส้นทางดำเนินการโดยใช้คลาส WayLayerGenerator ซึ่งอยู่ในเนมสเปซ Aspose.Gis.GeoTools.WayAnalyzer

คลาส WayLayerGenerator มี วิธี FindTheWay สำหรับการค้นหาเส้นทางจากจุดเริ่มต้นไปยังเป้าหมาย ในการสร้างอินสแตนซ์ของคลาส WayLayerGenerator เราส่งผ่าน WayOptions เป็นพารามิเตอร์ (พารามิเตอร์ทั้งหมดเป็นตัวเลือก):

• StartPoint: จุดเริ่มต้น

• GoalPoint: จุดหมายปลายทาง

• Radius: รัศมีการค้นหา

• Scale: ขนาดของกริด

• IsMoveOnlyRoad: ไม่ว่าจะค้นหาเส้นทางเฉพาะบนถนนหรือไม่

คุณสมบัติที่โดดเด่นที่นี่คือพารามิเตอร์ Scale หากระบุไว้ในคอนสตรัคเตอร์ เราจะแก้ไขขนาดคงที่สำหรับการค้นหาต่อเนื่อง หากพารามิเตอร์ Scale ไม่ได้ตั้งค่า แต่ StartPoint และ GoalPoint ถูกตั้งค่า เราจะคำนวณขนาดเป็นระยะห่างระหว่างจุดเริ่มต้นและจุดหมายปลายทางหารด้วย 100 ในกรณีอื่นๆ ค่าเริ่มต้นของ Scale คือ 1 สำหรับผู้ใช้ที่มีประสบการณ์ จะเป็นการดีกว่าที่จะตั้งค่า Scale หรือตั้งค่า StartPoint และ GoalPoint โดยตรงเพื่อแสดงถนนและสิ่งกีดขวางบนกริดอย่างมีประสิทธิภาพสูงสุด (โดยเฉพาะอย่างยิ่งหากมีจำนวนมาก)

ในการใช้เมธอด FindTheWay เราต้องระบุจุดเริ่มต้นและจุดหมายปลายทาง เรายังสามารถตั้งค่ารัศมีการค้นหา (ระยะทางที่คลื่นแพร่กระจาย) ได้ โดยค่าเริ่มต้น รัศมีจะคำนวณเป็นระยะห่างระหว่างจุดเริ่มต้นและจุดหมายปลายทางคูณด้วย 3 จุดเริ่มต้นและจุดหมายปลายทางอาจอยู่ใกล้กันหรือไกลจากกันมาก ดังนั้นตามระยะห่างระหว่างพวกมัน เราจึงคำนวณขนาดของกริดของเรา หากขนาดปัจจุบันไม่ตรงกับขนาดก่อนหน้า เราจะคำนวณกริดใหม่ ขนาดสามารถแก้ไขได้โดยใช้พารามิเตอร์ Scale ในกรณีนี้ จะไม่ได้คำนวณ และกริดจะไม่ถูกคำนวณใหม่

ก่อนที่จะเริ่มการค้นหา เราต้องกำหนดแผนที่ถนนและสิ่งกีดขวางโดยใช้วิธี AddRoad และ AddBlock ที่เกี่ยวข้องของคลาส WayLayerGenerator

สำหรับ วิธี AddRoad เราต้องระบุ:

• startPoint: จุดเริ่มต้นของถนน

• endPoint: จุดสิ้นสุดของถนน

• velocity: ความเร็วในการเคลื่อนที่บนถนน

สำหรับ วิธี AddBlock เราต้องระบุ:

• x: พิกัด x ของมุมซ้ายบนของบล็อก

• y: พิกัด y ของมุมซ้ายบนของบล็อก

• sizeX: ขนาดในแกน x

• sizeY: ขนาดในแกน y

วิธีการเหล่านี้ช่วยให้เราสามารถกำหนดแผนที่ถนนและสิ่งกีดขวางก่อนที่จะเริ่มกระบวนการค้นหาเส้นทางได้

Code examples

นี่คือตัวอย่างโค้ดบางส่วนที่แสดงให้เห็นถึงวิธีการตั้งค่าถนนและสิ่งกีดขวางในอัลกอริทึมการค้นหาเส้นทาง และค้นหาเส้นทางที่เหมาะสมที่สุด

ตัวอย่าง 1: การค้นหาเส้นทางระหว่างจุดเริ่มต้นและจุดหมายปลายทาง

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(5, 7);
Point goalPoint = new Point(15, 13);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

ตัวอย่าง 2: การตั้งค่าพารามิเตอร์ Scale และมีพิกัดเชิงลบสำหรับจุด

WayOptions mapGeneratorOptions = new WayOptions(1);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(-50, -70);
Point goalPoint = new Point(150, 130);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

ตัวอย่าง 3: การตั้งค่าพารามิเตอร์ IsMoveOnlyRoad และรัศมีการค้นหา

WayOptions mapGeneratorOptions = new WayOptions();
mapGeneratorOptions.IsMoveOnlyRoad = true;
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddRoad(new Point(100, 100), new Point(140, 150), 10);
generator.AddRoad(new Point(140, 150), new Point(190, 100), 10);
Point startPoint = new Point(100, 100);
Point goalPoint = new Point(190, 100);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 100);

ตัวอย่าง 4: การตั้งค่าพารามิเตอร์ Scale เพื่อการค้นหาที่รวดเร็วยิ่งขึ้น

WayOptions mapGeneratorOptions = new WayOptions(10);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(50, 70);
Point goalPoint = new Point(1650, 1300);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 2500);

ตัวอย่าง 5: ตัวอย่างการค้นหาหลายรายการ

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddBlock(200, 1700, 1500, 100, 0);
generator.AddBlock(1700, 200, 100, 1600, 0);
generator.AddBlock(200, 200, 1500, 100, 0);
generator.AddRoad(new Point(1000, 1150), new Point(200, 600), 10);
generator.AddRoad(new Point(50, 450), new Point(150, 1850), 10);

Point startPoint = new Point(1000, 1000);
Point goalPoint = new Point(1900, 1000);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 3500);

Point startPoint = new Point(50, 50);
Point goalPoint = new Point(70, 70);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

ตัวอย่างโค้ดเหล่านี้สร้างและแสดงเส้นทางถนนบนแผนที่สำหรับจุดที่ระบุ โดยใช้ข้อมูลถนนและตัวสร้างชั้นทาง

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