AbstractA time-constrained shortest

Abstract
A time-constrained shortest path problem is a shortest path problem including time constraints that are
commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem
associated with constraints that are difficult to define or optimize simultaneously. Depending on the types
of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence
of time–window constraints, waiting time occurs but is largely ignored. Given a network with such
constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first
K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK2|V1|3), where
r is the number of different windows of a node and |V1| is the number of nodes in the original network.

2005 Elsevier Inc. All rights reserved

ผลลัพธ์ (ไทย) 1:

บทคัดย่อปัญหาเส้นทางที่สั้นที่สุดรวมถึงข้อจำกัดของเวลาที่มีจำกัดเวลาสั้นที่สุดเส้นทางปัญหาจำลองโดยทั่วไป โดยรูปแบบของหน้าต่างเวลา เส้นทางที่สั้นที่สุดค้นหา K เหมาะสำหรับปัญหาเกี่ยวข้องกับข้อจำกัดที่ยากต่อการกำหนด หรือปรับให้เหมาะสมกัน ขึ้นอยู่กับชนิดข้อจำกัด เส้นทางเหล่านี้ K โดยทั่วไปแบ่งออกง่าย ๆ เส้นทางหรือเส้นทางแบบวนรอบ ในสถานะข้อจำกัดเวลา – หน้าต่าง รอเวลาเกิด แต่ส่วนใหญ่จะถูกละเว้น กำหนดเครือข่าย ด้วยเช่นข้อจำกัด ของเอกสารนี้คือการ พัฒนาอัลกอริทึมเวลาโพลิโนเมียที่พบครั้งแรกมีการวนรอบเส้นทางรวมถึงเวลารอสั้น K เวลาความซับซ้อนของอัลกอริทึมเป็น O (rK2|V1|3), ที่r คือ จำนวนหน้าต่างที่ต่างกันของโหน และ |V1| มีจำนวนโหนดในเครือข่ายเดิมอิงค์ Elsevier 2005 สงวนลิขสิทธิ์ทั้งหมด

ผลลัพธ์ (ไทย) 2:

บทคัดย่อ
ปัญหาเส้นทางที่สั้นที่สุดเวลา จำกัด เป็นปัญหาเส้นทางที่สั้นที่สุดรวมทั้งข้อ จำกัด ด้านเวลาที่มีการ
สร้างแบบจำลองโดยทั่วไปรูปแบบของหน้าต่างเวลา การหาเส้นทางที่สั้นที่สุด K มีความเหมาะสมสำหรับปัญหา
ที่เกี่ยวข้องกับข้อ จำกัด ที่มีความยากที่จะกำหนดหรือเพิ่มประสิทธิภาพพร้อมกัน ทั้งนี้ขึ้นอยู่กับชนิด
ของข้อ จำกัด เส้นทาง K เหล่านี้โดยทั่วไปเป็นอย่างใดอย่างหนึ่งเส้นทางที่ง่ายหรือเส้นทางที่วนลูป ในการปรากฏตัว
ของข้อ จำกัด หน้าต่างเวลารอเวลาที่เกิดขึ้น แต่ส่วนมากไม่สนใจ ป.ร. ให้เครือข่ายด้วยเช่น
ข้อ จำกัด ของการมีส่วนร่วมของการวิจัยนี้คือการพัฒนาอัลกอริทึมเวลาพหุนามที่พบครั้งแรกที่
K ที่สั้นที่สุดเส้นทางการวนลูปรวมทั้งเวลาที่รอคอย ความซับซ้อนของเวลาของขั้นตอนวิธีเป็น O (rK2 | V1 | 3) โดยที่
r คือจำนวนหน้าต่างที่แตกต่างกันของโหนดและ | V1 | เป็นจำนวนโหนดในเครือข่ายเดิม.
? 2005 เอลส์อิงค์สงวนลิขสิทธิ์

ผลลัพธ์ (ไทย) 3:

นามธรรม
เวลา จำกัด ปัญหาวิถีสั้นสุดคือเส้นทางที่สั้นที่สุดปัญหา รวมทั้งข้อจํากัดเวลาที่
ปกติแบบฟอร์มของ Windows เวลา การหาเส้นทางสั้นที่สุด K เหมาะสำหรับปัญหาที่เกี่ยวข้องกับข้อจำกัด
ที่ยากต่อการกำหนด หรือปรับพร้อมกัน ขึ้นอยู่กับชนิดของข้อจำกัด
,เหล่านี้โดยทั่วไปจะแบ่งเส้นทาง K ทั้งเรียบง่ายหรือปิดเส้นทางเส้นทาง ในการปรากฏตัว
เวลา–หน้าต่างข้อจำกัดเวลาที่รอคอยเกิดขึ้นแต่จะถูกละเว้นส่วนใหญ่ ระบุเครือข่ายด้วยเช่น
ข้อจำกัดส่วนของบทความนี้คือเพื่อพัฒนาขั้นตอนวิธีพหุนามเวลาที่พบครั้งแรก
K ปิดเส้นทางที่สั้นที่สุด รวมถึงเวลาที่รอคอยเวลาที่ซับซ้อนของขั้นตอนวิธีคือ O ( rk2 | V1 | 3 ) ที่
r คือจำนวนของหน้าต่างที่แตกต่างกันของโหนดและ | V1 | เป็นโหนดในเครือข่ายเดิม

2005 Elsevier Inc สงวนสิทธิ์ทั้งหมด