Solving a New Mathematical Model for a Multi-Objective and Multi-Depot Vehicle Routing Problem by a Non-dominated Sorting Genetic Algorithm

Document Type : Research Paper

Authors

1 Professor, School of Industrial Engineering, College of Engineering, University of Tehran

2 Islamic Azad University

Abstract

The vehicle routing problem (VRP) can be studied in variant cases, in which two related important problems are the VRP with hard time windows and the multi-depot VRP with heterogeneous vehicles. Most problems presented in this field are single-objective problems with the aim of the minimum cost; however, the complexity of real problems usually doubts the use of single objective problems. This paper considers not only the minimum travel cost, but also the distance travelled by the used vehicles and their loads. Since this problem is the NP-hard one, the non-dominated sorted genetic algorithm - II is used. To show its efficiency for solving small-sized problems, the obtained results are evaluated with the results obtained by the ε-constraint method. The results show that the obtained gap of the objective function values is less than 4% in all the solved problems indicating the efficiency of the proposed algorithm.

Keywords

Main Subjects

References

[1]       Baños, R., Ortega, J., Gil, C. (1959). Márquez, A.L. & de Toro, F. A hybrid meta-heuristic for multi- objective vehicle routing problems with time windows, Computers & Industrial Engineering 2013; 65(286-296).
[2]       Dantzig, G.B. & Ramser, J.H. The truck dispatching problem, Management Science, 6(80-91).
[3]       Clarke, G., Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12:568–581.
[4]       Tavakkoli-Moghaddam, R., Safaei, N., Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length, Applied Mathematics and Computation, 176:445-454.
[5]      توکلی مقدم، ر.، نوروزی، ن.، سلامت بخش، ع.ر.، علینقیان، م.، (1390)، مسأله مسیریابی وسایل نقلیه با در نظر گرفتن ایجاد توازن در توزیع کالاها با استفاده از الگوریتم بهبود یافته بهینه سازی انبوه ذرات، پژوهشنامه حمل و نقل، سال هشتم، شماره 4، زمستان: 375-363.
[6]       Mirabi, M., Fatemi Ghomi, S.M.T. & Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem, Robotics and Computer-Integrated Manufacturing 2010; 26(564-569).
[7]       Bettinelli, A., Ceselli, A. Righini, G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows, Transportation Research - Part C, 19:723-740.
[8]       Ghoseiri, K., Ghannadpour, S.F. (2010). Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Applied Soft Computing, 10:1096-1107.
[9]       Noori, S. & Ghannadpour, S.F. (2012). High-level relay hybrid metaheuristic method for multi-depot vehicle routing problem with time windows, Journal of Mathematical Modeling and Algorithms, 11:159-179.
[10]   Ghannadpour, S.F., Noori, S., Tavakkoli-Moghaddam, R. (2014). A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority, Journal of Combinatorial Optimization, 28:414-446.
[11]  کهفی، ع.، توکلی مقدم، ر. (1394)، حل مدل مسیریابی وسایل نقلیه چندانباره مبتنی بر کاهش ریسک با استفاده از یک الگوریتم خفاش چندهدفه، مهندسی حمل و نقل، سال ششم، شماره سوم: 507-522.
[12]  صباغ، م، س.، علینقیان، م.، زمانلو، ک. (1394)، مسأله مسیریابی وسایل نقلیه وابسته به زمان با محدودیت­های بارگیری دوبعدی: مدلسازی و حل، نشریه پژوهش­های مهندسی صنایع در سیستم­های تولید، دوره سوم، شماره پنجم:43-59.
[13]   Kritikos, M.N. Ioannou, G. (2013). The heterogeneous fleet vehicle routing problem with overloads and time windows, Int. J. of Production Economics, 144:68-75.
[14]   Lenstra, J.K. Rinnooy Kan, A.H.G. (1981). Complexity of vehicle and scheduling problem, Networks, 11:221-227.
Journal of Industrial Engineering Research in Production Systems
Volume 3, Issue 6 - Serial Number 6
Fall and Winter 2016
February 2016
Pages 167-175

Files

Share

How to cite

Statistics