T I M E D E P E N D E N T V E H I C L E R O U T I N G P R O B L E M I N M U L T I G R A P H S
Author(s):
Abstract:
In classical time dependent routing problems, it is assumed there is a unique edge between two nodes. In other words, these are designed based on a simple graph. However, for many urban areas, where there is complex urbanism and different traffic constraints, the traditional VRP viewpoint is not very suitable. In this article, a novel 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. For this purpose, this paper proposes a model called the ``Time Dependent Vehicle Routing Problem in Multigraphs''. The multigraph is a graph which is allowed to have multiple edges or parallel edges. Today, many of the transportation networks are defined in multiple graphs. Particularly, the model for studying vehicle routing problems in large cities can be useful. This model is designed, based on the Malandranki and Daskin (1992) proposed model for TDVRP. This formulation minimizes total travel time. The time dependent vehicle routing problem is an extension of vehicle routing problem and since VRP is a NP-hard problem, TDVRP is also NP-hard. For this reason, heuristics is used usually to solve these problems. In here, a tabu search (TS) algorithm is suggested for solving the proposed model. The main feature of the proposed heuristic is random selection between two switching strategies at every stage of neighborhood search. These two strategies are binary switching and reverse switching. This feature improves the algorithm performance. Finally, computational results of the proposed Tabu search algorithm, and the exact solution, using a CPLEX solver in GAMS V23.5 software, on 99 random instances, are compared. These instances cover a good range of different problems. This result presents the efficiency of the proposed algorithm in the computational time and quality of the solution.
Keywords:
Language:
Persian
Published:
Industrial Engineering & Management Sharif, Volume:30 Issue: 1, 2014
Pages:
119 to 127
magiran.com/p1359075
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
دسترسی سراسری کاربران دانشگاه پیام نور!
اعضای هیئت علمی و دانشجویان دانشگاه پیام نور در سراسر کشور، در صورت ثبت نام با ایمیل دانشگاهی، تا پایان فروردین ماه 1403 به مقالات سایت دسترسی خواهند داشت!
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!