@article { author = {حبیبی, مجید and کریمی, حسین}, title = {Modelling and Solving Time Dependent Vehicle Routing Problem with Semi Soft Time Windows in Multigraphs}, journal = {Journal of Transportation Research}, volume = {10}, number = {3}, pages = {-}, year = {2013}, publisher = {}, issn = {1735-3459}, eissn = {2008-3351}, doi = {}, abstract = {In the traditional “Time dependent Vehicle Routing Problems”, it is assumed there is only one edge between two nodes. In other words, these are designed based on a simple graph. However, in many urban areas, where there is complex urbanism and different traffic constraints and conditions, traditional VRP viewpoint is not very suitable. In this article, an extension of the Time Dependent Vehicle Routing Problem (TDVRP) is studied, where more than one edge between the depot and customers and between customers is possible. The multigraph is a graph which is permitted to have multiple edges or parallel edges. Today, many of the transportation networks are defined in multiple graphs. Given the importance of FIFO property, it must be ensured. In this article, This is done using a special process. We proposed a model that is called “TDVRPMSSTW”. In this model, Semi Soft Time Windows is defined for customers. This formulation minimizes the total travel time, Time Window penalties and vehicle fixed cost. Time Dependent Vehicle Routing Problem is an extension of Vehicle Routing Problem and since VRP is a NP-hard problem, therefore TDVRP is NP-hard too. So heuristics is used usually to solving these problems. In here, a Tabu Search (TS) algorithm is suggested for solving proposed model. The main feature of the proposed heuristic is randomly selection between two switching strategies in every stage of neighborhood search. These two strategies are binary switching and reverse switching. This feature improves the algorithm performance. Finally, computational results of proposed Tabu search algorithm and the exact solution using GAMS software on the 40 designed instances are compared. These instances cover a good range of different problems with small dimensions. This result presents the efficiency of the proposed algorithm in computational time and quality of the solution.}, keywords = {Time Dependent Vehicle Routing Problem,Time Dependent Vehicle Routing Problem; multigraph; Semi Soft Time Window; Tabu Search; FIFO property,multigraph,Semi Soft Time Window,Tabu Search,FIFO property}, title_fa = {مدلسازی و حل مساله مسیریابی وسیله نقلیه وابسته به زمان با پنجره‌های زمانی نیمه نرم در گراف‌های چندگانه}, abstract_fa = {مسائل مسیریابی کلاسیک عموما بگونه‌ای طراحی می‌شوند که ارتباط دو نقطه تنها از طریق یک یال یا سویه امکانپذیر است. با این حال گاهی شرایطی وجود دارد که از طریق بیش از یک یال از نقطه‌ای به نقطه دیگر می‌توان دسترسی داشت. این مقاله توسعه‌‌ای از مساله مسیریابی وسیله حمل و نقل وابسته به زمان را مورد بررسی قرار می‌دهد، که در آن امکان تخصیص بیش از یک یال یا سویه برای ارتباط نقاط مختلف میسر است. مساله مورد بررسی تحت پنجره‌های زمانی نیمه نرم برای برآورد تقاضای مشتریان مدلسازی شده است. مدل ارائه شده در این مقاله به اختصار TDVRPMSSTW نام نهاده شده است. در این مدل برای جلوگیری از مشکلات مفهومی ناشی از توابع زمان سفر گسسته، ویژگی "اولین ورودی اولین خروجی" برای تبدیل تابع سرعت سفر به تابع زمان سفر پیوسته، مورد استفاده قرار گرفته است. با توجه به NP-hard بودن مساله مورد مطالعه، یک الگوریتم جستجوی ممنوع پیشنهاد گردید. در روش ابتکاری پیشنهادی، جستجوی همسایگی بر اساس انتخاب تصادفی یکی از دو استراتژی تعویض دوتایی یا تعویض معکوس در هر تکرار انجام می‌شود. این مساله به بهبود نتایج حاصل از اجرای الگوریتم کمک می‌کند. در پایان نتایج محاسباتی الگوریتم جستجوی ممنوع و حل دقیق نرم‌افزار GAMS بر روی 40 مساله نمونه با هم مقایسه و کارایی الگوریتم پیشنهادی بر اساس کیفیت جواب و زمان حل در مقایسه با حل دقیق، نشان داده شده است.}, keywords_fa = {مساله مسیریابی وسیله نقلیه وابسته به زمان,گراف چندگانه,پنجره زمانی نیمه نرم,جستجوی ممنوع,ویژگی اولین ورودی اولین خروجی}, url = {https://www.trijournal.ir/article_11495.html}, eprint = {} }