2. Literature Review This literatur

2. Literature Review
This literature review is split into two parts: firstly, the literature related to the vehicle routing problems in terms of time dependency and randomness of link travel times is overviewed and secondly, the research on optimal path problem in STD networks is discussed. 2.1. Vehicle Routing Problem. Vehicle assignment and routing problems have been studied for several decades. Most traditional methodologies for this class of problems have been proposed based on adaptations of static algorithms and developed under static travel time, but they less consider dynamic traffic flow conditions [3]. As an extension of VRP, in order to consider possible variations of travel times in the network, Dynamic Vehicle Routing Problem is proposed. Malandraki and Daskin [4] put forward a strict mathematical model for TDVRP. They treat the travel time between two customers as a function of distance and the time of the day and design a nearest-neighbor heuristic algorithms and a cut plane heuristic algorithm. Ichoua et al. [5] introduce a First in First out (FIFO) principle into TDVRP and use time dependent function of speed to represent dynamic network, which avoids the deficiency of waiting in customer node in Malandraki and Daskin’s model [4]. Donati et al. [6] extend this line of research by indicating the importance of optimizing the starting time and designing a more efficient heuristic algorithm in a time-dependent environment Recently, many research works adopt the timedependent speed assumption proposed in [5]. Using queuing models for time-dependent speeds, analytical expressions for the expected travel times as well as for the variance of the travel times are derived in [7]. A continuous function model of time-dependent link speeds is proposed in [8]. More realistic time-dependent information is obtained from archived historical travel data, as seen in [9]. A general modeling framework with finer time-dependent traffic information and efficient solution algorithm are proposed in [1] and are applicable to large-scale real world. In this paper, we consider the VRP with dynamic and stochastic travel times (STDVRP), while there is limited research related to this topic. Lecluyse et al. [10] address the STDVRP by capturing the uncertainty in an analytical way using queuing theory and introduced the variability in traffic flows into the model, which allows for an evaluation of the routes based on the uncertainty involved. Nahum and Hadas [11] combine two important variants to form and define the STDVRP. Two algorithms for solving the stochastic time-dependent VRP are compared. As Ichoua et al. [5] indicate, stochastic and time-dependent travel times are more extensively operated on optimal path analysis between two service nodes when executing VRP delivery (see details in Section 2.2). Although mean and variance contain the most important information about path travel time, finding the single route with expected shortest travel time is not appropriate for routing when planners are not risk neutral. So in order to take account of the STD travel times in STDVRPTW, the optimal path problem in STD networks should be addressed as a subproblem first.

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

2. เอกสารประกอบการทบทวน การทบทวนวรรณกรรมนี้แบ่งออกเป็นสองส่วน: overviewed วรรณกรรมที่เกี่ยวข้องกับปัญหาสายรถเวลาอ้างอิงและ randomness ลิงค์เดินทางครั้งแรก และประการที่สอง การกล่าวถึงการวิจัยปัญหาเส้นทางที่เหมาะสมที่สุดในเครือข่ายมาตรฐาน 2.1. รถสายปัญหา กำหนดยานพาหนะและปัญหาเส้นทางมีการศึกษาในหลายทศวรรษที่ผ่านมา วิธีการแบบดั้งเดิมมากที่สุดสำหรับคลาสของปัญหานี้ได้ท้องตามเสนอของอัลกอริทึมแบบคง และพัฒนาภายใต้เวลาเดินทางคง แต่พวกเขาไม่พิจารณาจราจรแบบไดนามิกเงื่อนไขกระแส [3] เป็นส่วนขยายของ VRP เพื่อพิจารณารูปแบบได้เวลาเดินทางในเครือข่าย ปัญหาการกำหนดเส้นทางรถแบบไดนามิกมีเสนอ Malandraki และ Daskin [4] นำแบบจำลองทางคณิตศาสตร์ที่เข้มงวดสำหรับ TDVRP ผู้รักษาเวลาการเดินทางระหว่างลูกค้าสองรายเป็นฟังก์ชันของระยะทางและเวลาของวัน และการออกแบบเป็นเพื่อนบ้านที่ใกล้ที่สุดแล้วอัลกอริทึมและการบินตัดแล้วอัลกอริทึม Ichoua et al. [5] แนะนำเป็นครั้งแรกในหลักแรก (fifo) เป็น TDVRP และใช้เวลาขึ้นอยู่กับฟังก์ชันความเร็วถึงเครือข่ายแบบไดนามิก การหลีกเลี่ยงการขาดของในโหนลูกค้าในรุ่น Malandraki และ Daskin ของ [4] เบรคฟาสท์ et al. [6] ขยายสายงานวิจัยนี้ โดยการระบุความสำคัญของการปรับเวลาเริ่มต้น และออกแบบขั้นตอนวิธีแล้วมีประสิทธิภาพมากขึ้นในสภาพแวดล้อมขึ้นอยู่กับเวลาล่าสุด งานวิจัยจำนวนมากนำสมมติฐานความเร็ว timedependent ที่นำเสนอใน [5] ใช้รูปแบบการจัดคิวสำหรับเวลาขึ้นอยู่กับความเร็ว วิเคราะห์นิพจน์สำหรับเวลาเดินทางที่คาดไว้เช่นส่วนความแปรปรวนของเวลาเดินทางจะมาใน [7] มีเสนอแบบจำลองฟังก์ชันอย่างต่อเนื่องของความเร็วในการเชื่อมโยงขึ้นอยู่กับเวลาใน [8] คุณสามารถรับข้อมูลขึ้นอยู่กับเวลายิ่งเดินทางประวัติศาสตร์ที่เก็บข้อมูล แก๊ป [9] กรอบงานโมเดลทั่วไป finer เวลาขึ้นอยู่กับปริมาณการใช้ข้อมูลและอัลกอริทึมของโซลูชันที่มีประสิทธิภาพมีการนำเสนอใน [1] และใช้กับโลกจริงขนาดใหญ่ ในเอกสารนี้ เราพิจารณา VRP เวลาเดินทางแบบไดนามิก และแบบเฟ้นสุ่ม (STDVRP), ในขณะที่มีการจำกัดการวิจัยที่เกี่ยวข้องกับหัวข้อนี้ Lecluyse et al. [10] อยู่ STDVRP โดยการจับที่ความไม่แน่นอนในวิธีการวิเคราะห์โดยใช้ทฤษฎีการจัดคิว และนำความแปรผันในกระแสจราจรเข้าสู่รุ่น ซึ่งช่วยให้การประเมินเส้นทางตามความไม่แน่นอนเกี่ยวข้อง Nahum และ Hadas [11] รวมตัวแปรที่สำคัญสองฟอร์ม และกำหนด STDVRP มีการเปรียบเทียบสองอัลกอริทึมสำหรับแก้ VRP ขึ้นอยู่กับเวลาแบบเฟ้นสุ่ม แสดงเป็น Ichoua et al. [5] การสโทแคสติก และเดินทางขึ้นอยู่กับเวลาเวลาจะดำเนินการในการวิเคราะห์เส้นทางที่เหมาะสมระหว่างสองโหนบริการเมื่อดำเนินการจัดส่งสินค้า VRP อย่างกว้างขวางมากขึ้น (ดูรายละเอียดในหัวข้อ 2.2) หมายถึงแม้ว่าต่างมีข้อมูลที่สำคัญเกี่ยวกับเวลาการเดินทางเส้นทาง ค้นหาเส้นทางเดียวกับเวลาเดินทางสั้นที่สุดที่คาดไว้ไม่เหมาะสมกับสายงานการวางแผนมีความเสี่ยงที่เป็นกลางไม่ เพื่อใช้บัญชีมาตรฐานเดินทางเวลาใน STDVRPTW ปัญหาเส้นทางที่เหมาะสมที่สุดในเครือข่ายมาตรฐานควรส่งเป็น subproblem เป็นครั้งแรก

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

2.
ทบทวนวรรณกรรมทบทวนวรรณกรรมนี้จะแบ่งออกเป็นสองส่วนคือส่วนแรกวรรณกรรมที่เกี่ยวข้องกับปัญหาการกำหนดเส้นทางยานพาหนะในแง่ของการพึ่งพาเวลาและแบบแผนของการเดินทางครั้งเชื่อมโยงoverviewed และประการที่สองการวิจัยเกี่ยวกับปัญหาเส้นทางที่ดีที่สุดในระบบเครือข่าย STD จะกล่าวถึง . 2.1 สายงานการผลิตยานพาหนะปัญหา ยานพาหนะที่ได้รับมอบหมายและปัญหาการกำหนดเส้นทางได้รับการศึกษาสำหรับหลายทศวรรษ วิธีการแบบดั้งเดิมมากที่สุดสำหรับการเรียนของปัญหานี้ได้รับการเสนอขึ้นอยู่กับการปรับตัวของขั้นตอนวิธีแบบคงที่และการพัฒนาภายใต้เวลาในการเดินทางคงที่ แต่พวกเขาน้อยพิจารณาสภาพการจราจรแบบไดนามิก [3] ในฐานะที่เป็นส่วนขยายของ VRP การเพื่อพิจารณารูปแบบที่เป็นไปได้ของการเดินทางครั้งในเครือข่ายปัญหาเส้นทางยานพาหนะแบบไดนามิกจะเสนอ Malandraki และ Daskin [4] วางอยู่ข้างหน้าแบบจำลองทางคณิตศาสตร์ที่เข้มงวดสำหรับ TDVRP พวกเขาปฏิบัติต่อเวลาในการเดินทางระหว่างสองลูกค้าเป็นหน้าที่ของระยะทางและเวลาของวันและการออกแบบขั้นตอนวิธีการที่ใกล้ที่สุดเพื่อนบ้านแก้ปัญหาและเครื่องบินตัดขั้นตอนวิธีการศึกษาสำนึก Ichoua et al, [5] แนะนำเป็นครั้งแรกในแรกออก (FIFO) หลักการเข้า TDVRP และใช้เวลาในการทำงานขึ้นอยู่กับความเร็วในการเป็นตัวแทนของเครือข่ายแบบไดนามิกที่หลีกเลี่ยงการขาดการรอคอยในโหนดลูกค้าใน Malandraki Daskin และรูปแบบของ [4] Donati et al, [6] ขยายสายงานวิจัยนี้แสดงให้เห็นความสำคัญโดยการเพิ่มประสิทธิภาพเวลาเริ่มต้นและการออกแบบขั้นตอนวิธีการแก้ปัญหามีประสิทธิภาพมากขึ้นในสภาพแวดล้อมที่ขึ้นกับเวลาเมื่อเร็ว ๆ นี้ผลงานวิจัยจำนวนมากนำมาใช้ความเร็ว timedependent สมมติฐานเสนอใน [5] โดยใช้แบบจำลองการเข้าคิวสำหรับความเร็วเวลาขึ้นอยู่กับการแสดงออกการวิเคราะห์สำหรับการเดินทางครั้งที่คาดหวังเช่นเดียวกับความแปรปรวนของการเดินทางครั้งจะได้มาใน [7] รูปแบบฟังก์ชั่นอย่างต่อเนื่องของความเร็วในการเชื่อมโยงขึ้นกับเวลามีการเสนอใน [8] ข้อมูลที่ขึ้นกับเวลาจริงมากขึ้นจะได้รับจากการเดินทางข้อมูลที่เก็บไว้ในประวัติศาสตร์เท่าที่เห็นใน [9] กรอบการสร้างแบบจำลองทั่วไปที่มีข้อมูลการจราจรขึ้นกับเวลาและขั้นตอนวิธีปลีกย่อยโซลูชั่นที่มีประสิทธิภาพมีการเสนอใน [1] และมีผลบังคับใช้ไปทั่วโลกขนาดใหญ่จริง ในบทความนี้เราจะพิจารณา VRP ที่มีเวลาในการเดินทางแบบไดนามิกและการสุ่ม (STDVRP) ในขณะที่มีการวิจัยที่เกี่ยวข้องกับการ จำกัด หัวข้อนี้ Lecluyse et al, [10] ที่อยู่ STDVRP โดยจับความไม่แน่นอนในทางทฤษฎีการวิเคราะห์โดยใช้การเข้าคิวและแนะนำความแปรปรวนในการจราจรไหลเข้ามาในรูปแบบซึ่งจะช่วยให้สำหรับการประเมินผลของเส้นทางบนพื้นฐานของความไม่แน่นอนเกี่ยวข้อง นาฮูมและ Hadas [11] รวมสองสายพันธุ์ที่สำคัญในรูปแบบและกำหนด STDVRP สองขั้นตอนวิธีการสำหรับการแก้ VRP ขึ้นกับเวลาสุ่มจะเปรียบเทียบ ในฐานะที่เป็น Ichoua et al, [5] ระบุสุ่มและเวลาการเดินทางข้ามเวลาขึ้นอยู่กับจะดำเนินการอย่างกว้างขวางมากขึ้นในการวิเคราะห์เส้นทางที่ดีที่สุดระหว่างสองโหนดบริการเมื่อมีการดำเนินการจัดส่ง VRP (ดูรายละเอียดในข้อ 2.2) แม้ว่าค่าเฉลี่ยและความแปรปรวนมีข้อมูลที่สำคัญที่สุดเกี่ยวกับเวลาในการเดินทางเส้นทางการหาเส้นทางเดียวที่มีเวลาในการเดินทางที่สั้นที่สุดคาดว่าไม่เหมาะสมสำหรับการกำหนดเส้นทางเมื่อวางแผนจะไม่เสี่ยงที่เป็นกลาง ดังนั้นเพื่อที่จะใช้บัญชีของการเดินทางครั้ง STD ใน STDVRPTW ปัญหาเส้นทางที่ดีที่สุดในระบบเครือข่าย STD ควรได้รับการแก้ไขเป็นครั้งแรก subproblem

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

2 . การทบทวนวรรณกรรม
ทบทวนวรรณกรรมนี้แบ่งออกเป็น 2 ส่วน คือ วรรณกรรมที่เกี่ยวข้องกับปัญหาการจัดเส้นทางยานพาหนะ ในแง่ของการสุ่มของเวลาและช่วงเวลาเดินทางเชื่อมโยง overviewed และประการที่สอง การวิจัยปัญหาเส้นทางที่เหมาะสมในเครือข่าย STD กล่าวถึง . 2.1 . ปัญหาการจัดเส้นทางยานพาหนะ .งานยานพาหนะและเส้นทางปัญหาได้รับการศึกษามานานหลายทศวรรษ วิธีการแบบดั้งเดิมมากที่สุดในชั้นเรียน ปัญหานี้ได้ถูกเสนอโดยการดัดแปลงอัลกอริทึมแบบคงที่และพัฒนาภายใต้เวลาเดินทางคงที่ แต่พวกเขาไม่พิจารณาสภาพการจราจรแบบไดนามิก [ 3 ] เป็นส่วนขยายของ vrp ในการพิจารณาการเปลี่ยนแปลงที่เป็นไปได้ของการเดินทางครั้ง ในเครือข่ายปัญหาการจัดเส้นทางยานพาหนะแบบไดนามิก คือ เสนอ และ malandraki daskin [ 4 ] ใส่ไปข้างหน้าแบบจำลองทางคณิตศาสตร์อย่างเข้มงวดสำหรับ tdvrp . พวกเขารักษา เวลาเดินทางระหว่างสองลูกค้าเป็นฟังก์ชันของระยะทางและเวลาของวันและการออกแบบฮิวริสติกอัลกอริทึม และเพื่อนบ้านใกล้ที่สุดเครื่องบินตัดฮิวริสติกอัลกอริทึม ichoua et al .[ 5 ] แนะนำ เข้าก่อน - ออกก่อน ( FIFO ) หลักการใน tdvrp และใช้ฟังก์ชันที่ขึ้นกับเวลาของความเร็วของเครือข่ายแบบไดนามิก ซึ่งการขาดรอลูกค้าใน malandraki โหนด และ daskin นางแบบ [ 4 ] โดนาติ et al .[ 6 ] ขยายสายของการวิจัยนี้ โดยระบุว่า ความสำคัญของการเพิ่มเวลาเริ่มต้นและการออกแบบขั้นตอนวิธีการแก้ปัญหามีประสิทธิภาพมากขึ้นในสภาพแวดล้อมที่เวลาล่าสุด หลายงานวิจัย ใช้ความเร็ว timedependent อัสสัมชัญเสนอใน [ 5 ] โดยใช้เวลาแถวคอยสำหรับความเร็ว ,วิเคราะห์นิพจน์สำหรับคาดว่าการเดินทางครั้งเป็นค่าความแปรปรวนของการเดินทางครั้งจะได้มาใน [ 7 ] รูปแบบของฟังก์ชันที่ต่อเนื่องความเร็วลิงค์เวลาเสนอ [ 8 ] ข้อมูลเชิงเวลามีเหตุผลเพิ่มเติมได้จากเก็บข้อมูลท่องเที่ยวทางประวัติศาสตร์ที่เห็น [ 9 ]กรอบแบบทั่วไปกับข้อมูลจราจรแบบเวลาปลีกย่อยและโซลูชั่นที่มีประสิทธิภาพที่นำเสนอใน [ 1 ] และจะสามารถใช้ได้กับขนาดใหญ่โลกที่แท้จริง ในกระดาษนี้เราพิจารณา vrp ที่มีพลวัตและ Stochastic เวลาเดินทาง ( stdvrp ) ในขณะที่มีการวิจัย จำกัด ที่เกี่ยวข้องกับหัวข้อนี้ lecluyse et al .[ 10 ] ที่อยู่ stdvrp โดยจับความไม่แน่นอนในวิธีวิเคราะห์โดยใช้ทฤษฎีแถวคอยและแนะนำความแปรปรวนในการจราจรไหลเข้าไปในโมเดล ซึ่งช่วยให้สามารถประเมินเส้นทางขึ้นอยู่กับความไม่แน่นอนมาเกี่ยวข้อง นา ม และ ฮาดาส [ 11 ] รวมสองตัวแปรสำคัญฟอร์ม และกำหนด stdvrp . สองขั้นตอนวิธีสำหรับแก้ปัญหา vrp เวลาสุ่มเปรียบเทียบเป็น ichoua et al . [ 5 ] แสดง , Stochastic และเวลาการเดินทางครั้งเป็นอย่างกว้างขวางมากขึ้นความสามารถในการวิเคราะห์เส้นทางที่ดีที่สุดระหว่างโหนดสองเมื่อรัน vrp บริการจัดส่ง ( ดูรายละเอียดในส่วน 2.2 ) แม้ว่าค่าเฉลี่ยและความแปรปรวนมีมากข้อมูลเกี่ยวกับเวลาในการเดินทางเส้นทางการหาเส้นทางที่สั้นที่สุด เดียว คาดว่าจะใช้เวลาเดินทางไม่เหมาะกับเส้นทางที่วางแผนจะไม่เสี่ยงที่เป็นกลาง ดังนั้น ในการใช้บัญชีของ STD เดินทางครั้งใน stdvrptw ปัญหาเส้นทางที่เหมาะสมในเครือข่าย STD ควรให้ความสนใจเป็น subproblem
1