21557

21557

ارائه الگوريتم بهينه‌سازي تخصيص مسافرين به تاكسي‌هاي اشتراكي

كارشناسي ارشد

برنامه‌ريزي حمل و نقل

1398/8/19

دكتر محمود احمدي نژاد - دكتر شهريار افنديزاده

عمران

موضوع به اشتراك­گذاري سواري از دهه 70 ميلادي مطرح بوده است، اما ظهور تلفن‌هاي هوشمند در سال‌هاي اخير آن را به يك گزينه قابل رقابت با ساير شيوه‌هاي جابجايي در سطح شهر تبديل كرده است. عدم محدوديت در جابجايي سيستم‌هاي اشتراك سواري مبتني بر اينترنت در سطح شبكه (كه به نوعي نشان دهنده مقياس‌پذيري بالاي آنهاست)، منتج به گشت زدن تعداد زياد خودروهاي شخصي مي‌شود، كه اين مسئله تشديد ازدحام در نواحي پر تردد را در پي دارد. از طرف ديگر حضور قابل توجه تاكسي­هاي گردشي و عملكرد غيركاراي آنها، جريان عادي ترافيك را در ساعات اوج مختل كرده، و منجر به افزايش زمان سفر مي‌شود. در پايان­نامه حاضر، ارائه الگوريتمي جهت تخصيص سفرهاي تكراري و يا از پيش برنامه­ريزي شده (كاري، آموزشي و ...) به صورت اشتراكي مورد نظر است. در ادامه، جهت مقايسه نتايج تخصيص مسافرين مبتني بر الگوريتم پيشنهادي، تعدادي سناريو از ميان سناريوهاي ممكن، تعريف خواهد شد، كه يك سري شاخص از جمله مسافت پيموده شده از نگاه شبكه و ضريب سرنشين، مقايسه آنها را ممكن مي‌سازد. 1. سناريوي مبتني بر الگوريتم ارسال نزديك­ترين خودرو كه رايج­ترين استفاده را در كاربردهاي واقعي دارد؛ 2. سناريوي مبتني بر تخصيص مسافرين به نزديكترين تاكسي به صورت اشتراكي؛ 3. سناريوي مبتني بر الگوريتم پيشنهادي و در نهايت 4. سناريوي انجام هيچ كاري (انجام سفر با خودروي شخصي) كه به عنوان مبناي مقايسه سناريوها در نظر گرفته شده است. هدف از ارائه اين سناريوها، شبيه­سازي وضعيت سرويس­هاي رايجي است، كه در بيشتر موارد از آنها استفاده مي­شود. نتايج سناريوهاي سه گانه در مقايسه با سناريوي انجام هيچ كاري، به ترتيب با تغيير 51/10-، 16/10 و 56/25 درصدي در مسافت پيموده شده كل، برتري سناريوي 3 (مبتني بر الگوريتم پيشنهادي) را نشان مي‌دهد. از جمله دستاوردهاي تحقيق پيش رو مي‌توان، به ساماندهي تاكسي­هاي گردشي، سرويس­دهي سفرهاي تكراري و از پيش برنامه­ريزي شده، معرفي ضريب اهميت اشتراك،‌ كاهش قابل توجه در مسافت پيموده شده كل، افزايش ضريب سرنشين و شناسايي الگوهاي جابجايي در سطح شبكه اشاره كرد. شناسايي و تعريف مفهوم ضريب اهميت اشتراك، به كارگيري الگوريتم ‌Apriori در مرحله پيش­پردازش داده­ها و شناسايي الگوهاي جابجايي، به عنوان نوآوري‌هاي اصلي اين تحقيق قابل اشاره هستند.

1398/10/25

A Matching Algorithm for Shared Taxis

11/10/2019 12:00:00 AM

The subject of ride-sharing has been broached since the 1980s, but in recent years the advent of smartphones has made it a competitive option compared to other transportation modes. The high scalability of Internet-based ride-sharing systems leads to a large number of private vehicles patrolling the network, which has caused increased congestion in high-traffic areas. On the other hand, the significant presence of cruising (circulating) taxis and their inefficient performance disrupt the normal flow of traffic at peak hours and lead to increased travel time. This thesis investigates the necessity of introducing an internet-based system developed based on the proposed assignment algorithm. The primary purpose is to serve recurring or pre-planned trips (work, education) by sharing. Next, to compare the results of passenger assignment through the proposed matching algorithm, some scenarios will be defined among the possible scenarios; indicators such as the distance traveled from a network perspective and occupancy rate will make it possible to analyze and evaluate them. 1. The first scenario, based on the Nearest Vehicle Dispatch (NVD) algorithm, is most commonly used in real applications; 2. The second scenario based on the assignment of passengers to the nearest taxi collectively; 3. The third scenario based on the proposed matching algorithm and finally, 4. The do-nothing scenario (private car travel) is intended as a basis for comparing scenarios. The purpose of these scenarios is to simulate the status of current services, which are used in most cases. The results of the three scenarios compared to the do-nothing, with a change of -10.51, 10.16, and 25.56% in total vehicle kilometer traveled (VKT), respectively, lead to choosing the third scenario (based on the proposed matching algorithm) as the best scenario. Some of the research accomplishments can be noted, such as the organization of cruising taxis, giving service to commuters, the introduction of the Sharing Importance Factor (SIF), the significant reduction in total VKT, the improvement in occupancy rate and the identification of movement patterns at the network level. Identifying and defining the concept of the Sharing Importance Factor, applying the Apriori algorithm at the data preprocessing stage, and identifying patterns of movement are the main innovations of this research.