مقاله #552

چکیده- الگوریتم Dijkstra که به منظور حل مساله کوتاه ترین مسیر (SSP) از آن استفاده می‌شود، الگوریتمی شناخته شده است. هنگامی که این الگوریتم به موقعیت‌های حقیقی اعمال می‌شود، اگرچه می توان کوتاه ترین مسیر را با آن محاسبه کرد، اما این مسیر همواره مسیر انتخابی نیست. مثلاً در شرایط ترافیک، ممکن است راننده از طول دقیق مسیرها مطلع نباشد یا نداند که کوتاهترین مسیری که باید در آن حرکت کند، کدام است. حتی راننده ای ممکن است با اینکه بداند کوتاه ترین مسیر کدام است، اما مسیر دیگری را انتخاب نماید.

در این مقاله، الگوریتم PEDA (تعمیم احتمالاتی الگوریتم Dijkstra) را ارائه می کنیم  که تغییرات احتمالاتی وزن edgeها (لبه‌ها) و تغییرات احتمالاتی تصمیم‌ها را در هنگام انتخاب کوتاه ترین مسیر، معرفی می کند. هنگامی که PEDA به جریان ترافیک اعمال می‌شود، شبیه سازی‌های دقیق تری حاصل می شوند که در آنها لزوما همواره کوتاه ترین مسیر انتخاب نمی گردد و سبب ایجاد شبیه سازی دقیق تری از رفتار عادی رانندگان می شود.

به عنوان یک مثال کاربردی، مدل ATISMART⁺ را به صورت تعمیم مدل ATISMART معرفی می کنیم  که در آن، شبیه سازی سریعتری از ترافیک اتومبیل ها در شهر هوشمند تشریح شده است. در کار پیشین (ATISMART) تمامی اتومبیل ها به منظور انتخاب مسیر از الگوریتم Dijkstra استفاده میکردند، در حالیکه اتومبیلها در مدل توسعه یافته ATISMART⁺ به منظور سریعتر شدن زمان شبیه سازی جریان ترافیک در شهرهای هوشمند، از الگوریتم PEDA استفاده میکنند. نتایج نشان می دهند که ATISMART⁺ با در نظر گیری رفتار رانندگان مختلف، شبیه‎سازی‎های حقیقی تری را ایجاد می کند.