Solving a Multi-Depot Routing Problem with Time Windows and Heterogeneous Vehicles by Multi-objective Differential Evolution Algorithm: A Case Study

Document Type : Scientific - Research

Authors

Abstract

A Multi-depot Heterogeneous Vehicle Routing Problem with Time Windows (MDHVRPTW) is a variant of the Vehicle Routing Problem (VRP), in which the vehicles do not necessarily have the same capacity and they belong to different depots. Therefore, the MDHVRPTW involves designing a set of vehicle routes, each starting and ending at the depot, for a heterogeneous fleet of vehicles which services a set of customers with known demands. Most problems presented in this field are single-objective problems with the aim of minimizing the 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 NP-hardness, the use of a meta-heuristic algorithm is obligatory. Therefore a meta-heuristic algorithm based on Multi-Objective Differential Evolution (MODE) is proposed. In addition, to show the efficiency of the proposed MODE, a number of test problems in small and large sizes are considered and then solved. The associated results are evaluated with the results obtained by the ε-constraint method and results showed that the gained function gap was less than 3.5% in all the solved problems. Furthermore, to run the proposed MODE, a real-case study in an oil distribution company is carried out. Finally, the obtained results are reported and discussed.

Keywords

References

- Bae, T. S., Hwang, H. S., Cho, G. S. and Goan, M. J. (2007) “Integrated GA-VRP solver for multi-depot system”, Computers & Industrial Engineering, Vol. 53, No. 2, pp. 233-240.
- Baños, R., Ortega, J., Gil, C, Márquez, A. L. and de Toro, F. (2013) “A hybrid meta-heuristic for multi- objective vehicle routing problems with time windows”, Computers & Industrial, Engineering, Vol. 65, No. 2, pp. 286-296.  
- Bettinelli, A., Ceselli, A. and Righini, G. (2010) “A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows”. Transportation Research - Part C, Vol. 19, No. 5, pp. 723-740.
- Chen, H .K., Hsueh, C. F. and Chang, M. S. (2009) “Production scheduling and vehicle routing with time windows for perishable food products”. Computers & Operations Research, Vol. 36, pp. 2311-2319.
- Clarke, G. and Wright, J. W. (1964) “Scheduling of vehicles from a central depot to a number of delivery points”. Operations Research, Vol. 12, pp. 568–589.
- Dantzig, G. and Ramser, J. H. (1959) “The truck dispatching problem”, Management Science, Vol. 6, pp. 80-91.
 - Fazel Zarandi, M. H., Hemmati, A. and Davari, S. (2011) “The multi-depot capacitated location- routing problem with fuzzy travel times”. Expert Systems with Applications Vol. 38, pp. 10075–10084.
- Gnoni, M. G., Lavagnilio, R. Mossa, G., Mommolo, G. and Leva, A. D. (2003) “Production of a multisite manufacturing system by hybrid modeling: A case study from the automotive industry”, International Journal of Production Economics, Vol. 5, pp. 251-262.
- Ghannadpour, S. F., Noori, S. and Tavakkoli-Moghaddam, R. (2014) “A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority”, Journal of Combinatorial Optimization, Accepted for publication, Vol. 28, No. 2, pp. 414-466
- Giosa, I. D., Tansini, I. L.and Viera, I. C. (2002) “New assignment algorithms for multi-depot vehicle routing problem”. Journal of Operational Research Society, Vol. 53, No. 9, pp. 977-984.
- Ghoseiri, K. and Ghannadpour, S. F. (2010) “Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm”, Applied Soft Computing, Vol. 10, No. 4, pp. 1096-1107.
- Gulczynski, D., Golden, G. and Wasil, E. (2011) “The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems and computational results”, Computers & Industrial Engineering, Vol. 61, No. 3, pp. 794-804.
- Khaled Ahsan Talukder, A. K. Kirley M. and, Buyya,  M. B. (2009) “Multiobjective differential evolution for scheduling workflow applications on global grids”, Concurrency and Computation: Practice and Experience, Vol. 21, No. 13, pp. 1742-1756.
- Kritikos, M. N. and Ioannou, G. (2013) “The heterogeneous fleet vehicle routing problem with overloads and time windows”. Int. J. Production Economics, Vol. 144, No. 1, pp. 68-75.
- Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981) “Complexity of vehicle and scheduling problem”, Networks, Vol. 11, pp. 221–227.
- Mirabi, M., FatemiGhomi, S. M. t. and Jolai, F. (2010) “Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem”, Robotics and Computer-Integrated Manufacturing, Vol. 26, No. 6, pp. 564–569.
- Nagy, G. and Salhi, S. (2005) “Heuristic algorithms for the single and multiple depot vehicle routing problems with pickups and deliveries”, European Journal of Operational Research, Vol. 162, No. 1, pp. 126-141.
- Noori, S. and Ghannadpour, S. F. (2012) “High-level relay hybrid metaheuristic method for Multi-depot Vehicle routing problem with time windows”, Journal of Math. Model Algor., Vol. 11, pp. 159–179.tt
- Storn, R. and Price, K.V. (1996) “Minimizing the real functions of the ICEC’96 contest by differentian evolution”. IEEE International Contrence on Evolutionary Computation,Vol. 14, pp. 824 844.
-Tavakkoli-Moghaddam, R., Safaei, N. and Gholipour, Y. (2006) “A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length”, Applied Mathematics and Computation, Vol. 176, pp. 445–454.
- توکلی مقدم، ر.، نوروزی، ن.، سلامت بخش، ع.ر.، علینقیان، م.، (1390)، "مسأله مسیریابی وسائط نقلیه با در نظر گرفتن ایجاد توازن در توزیع کالاها با استفاده از الگوریتم بهبود یافته بهینه سازی انبوه ذرات"، پژوهشنامه حمل و نقل، سال هشتم، شماره 4، زمستان 1390، ص. 375-363.
- توکلی مقدم، ر.، علینقیان، م.، نوروزی، ن.، سلامت بخش، ع. ر. (1391) "حل یک مدل جدید برای مسأله مسیریابی وسائط نقلیه با در گرفتن ایمنی در حمل و نقل مواد خطرناک"،  فصلنامه مهندسی حمل و نقل، سال دوم، شماره 3، بهار 1390، ص. 237-223.

Files

History

  • Receive Date: 05 December 2013
  • Accept Date: 31 May 2014

Share

How to cite

Statistics