AJOR  Vol.7 No.1 , January 2017
Development of an Efficient Genetic Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows
Abstract: This research considers the time-dependent vehicle routing problem (TDVRP). The time-dependent VRP does not assume constant speeds of the vehicles. The speeds of the vehicles vary during the various times of the day, based on the traffic conditions. During the periods of peak traffic hours, the vehicles travel at low speeds and during non-peak hours, the vehicles travel at higher speeds. A survey by TCI and IIM-C (2014) found that stoppage delay as percentage of journey time varied between five percent and 25 percent, and was very much dependent on the characteristics of routes. Costs of delay were also estimated and found not to affect margins by significant amounts. This study aims to overcome such problems arising out of traffic congestions that lead to unnecessary delays and hence, loss in customers and thereby valuable revenues to a company. This study suggests alternative routes to minimize travel times and travel distance, assuming a congestion in traffic situation. In this study, an efficient GA-based algorithm has been developed for the TDVRP, to minimize the total distance travelled, minimize the total number of vehicles utilized and also suggest alternative routes for congestion avoidance. This study will help to overcome and minimize the negative effects due to heavy traffic congestions and delays in customer service. The proposed algorithm has been shown to be superior to another existing algorithm in terms of the total distance travelled and also the number of vehicles utilized. Also the performance of the proposed algorithm is as good as the mathematical model for small size problems.
Cite this paper: Kumar, S. and Panneerselvam, R. (2017) Development of an Efficient Genetic Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows. American Journal of Operations Research, 7, 1-25. doi: 10.4236/ajor.2017.71001.

[1]   Ichoua, S., Gendreau, M. and Potvin, J.Y. (2003) Vehicle Dispatching with Time-Dependent Travel Times. European Journal of Operational Research, 144, 379-396.

[2]   Malandraki, C. and Daskin, M.S. (1992) Time-Dependent Vehicle-Routing Problems: Formulations, Properties and Heuristic Algorithms. Transportation Science, 26, 185-200.

[3]   Eglese, R., Maden, W. and Slater, A. (2006) A Road Timetable to Aid Vehicle Routing and Scheduling. Computers and Operations Research, 33, 3508-3519.

[4]   Ford, J.L.R. and Fulkerson, D.R. (1956) Maximal Flow through a Network. Canadian Journal of Mathematics, 8, 399-404.

[5]   Marguier, P. and Cedar, A. (1984) Passenger Waiting Strategies for Overlapping Bus Routes. Transportation Science, 18, 207-230.

[6]   Miller, C.E., Tucker, A.W. and Zemlin, R.A. (1960) Integer Programming Formulations and Traveling Salesman Problems. Journal of the Association for Computing Machinery, 7, 326-329.

[7]   Kok, A.L., Hans, E.W. and Schutten, J.M.J. (2011) Optimizing Departure Times in Vehicle Routes. European Journal of Operational Research, 210, 579-587.

[8]   Li, H. and Lim, A. (2001) A Metaheuristic for the Pickup and Delivery Problem with Time Windows. IEEE Proceedings of the 13th International Conference on Tools with Artificial Intelligence, Dallas, 7-9 November 2001, 160-167.

[9]   Lei, H., Laporte, G. and Guo, B. (2011) The Capacitated Vehicle Routing Problem with Stochastic Demands and Time Windows. Computers & Operations Research, 38, 1775-1783.

[10]   Figliozzi, M.A. (2009) A Route Improvement Algorithm for the Vehicle Routing Problem with Time Dependent Travel Times. Proceedings of the 88th Transportation Research Board Annual Meeting, Washington DC, 11-15 January 2009, 616-636.

[11]   Kuo, Y., Wang, C.-C. and Chuang, P.-Y. (2009) Optimizing Goods Assignment and the Vehicle Routing Problem with Time-Dependent Travel Speeds. Computers and Industrial Engineering, 57, 1385-1392.

[12]   Shin Ahn, B.-H. and Shin, J.Y. (1991) Vehicle-Routing with Time Windows and Time-Varying Congestion. Journal of the Operational Research Society, 42, 393-400.

[13]   Hill, A.V. and Benton, W.C. (1992) Modelling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems. Journal of the Operational Research Society, 43, 343-351.

[14]   Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J.-Y. (1997) A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science, 31, 170-186.

[15]   Gendreau, M., Laporte, G. and Potvin, J.-Y. (2002) Metaheuristics for the VRP. In: Toth, P. and Vigo, D., Eds., The Vehicle Routing Problem (Monographs on Discrete Mathematics and Applications), SIAM, Philadelphia, 129-154.

[16]   Fleischmann, B., Gietz, M. and Gnutzmann, S. (2004) Time-Varying Travel Times in Vehicle Routing. Transportation Science, 38, 160-173.

[17]   Haghani, A. and Jung, S. (2005) A Dynamic Vehicle Routing Problem with Time-Dependent Travel Times. Computers & Operations Research, 32, 2959-2986.

[18]   Woensel, T.V., Kerbache, L., Peremans, H. and Vandaele, N. (2008) Vehicle Routing with Dynamic Travel Times: A Queueing Approach. European Journal of Operational Research, 186, 990-1007.

[19]   Augerat, P., Belenguer, J., Benavent, E., Corber’an, A., Naddef, D. and Rinaldi, G. (1995) Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem. Technical Report 949-M, Université Joseph Fourier, Grenoble.

[20]   Maden, W., Eglese, R. and Black, D. (2010) Vehicle Routing and Scheduling with Time-Varying Data: A Case Study. Journal of the Operational Research Society, 61, 515-522.

[21]   Potvin, J.-Y. and Rousseau, J.-M. (1995) An Exchange Heuristic for Routeing Problems with Time Windows. Journal of the Operational Research Society, 46, 1433-1446.

[22]   Solomon, M. (1987) Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Operations Research, 35, 254-265.

[23]   Balseiro, S.R., Loiseau, I. and Ramonet, J. (2011) An Ant Colony Algorithm Hybridized with Insertion Heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research, 38, 954-966.

[24]   Ehmke, S., Meisel, S. and Engelmann, D.C. (2009) Mattfeld Data Chain Management for Planning in City Logistics. International Journal of Data Mining, Modelling and Management, 1, 335-356.

[25]   Desrochers, M., Lenstra, J.K., Savelsbergh, M.W.P. and Soumis, F. (1988) Vehicle Routing with Time Windows: Optimization and Approximation. Vehicle Routing: Methods and Studies, 16, 65-84.

[26]   Hashimoto, H., Ibaraki, T., Imahori, S. and Yagiura, M. (2006) The Vehicle Routing Problem with Flexible Time Windows and Travelling Times. Discrete Applied Mathematics, 154, 2271-2290.

[27]   Kumar, S.N. and Panneerselvam, R. (2015) A Comparative Study of Proposed Genetic Algorithm-Based Solution with Other Algorithms for Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supply Chain. Journal of Service Science and Management, 8, 844-859.

[28]   Sivasankaran, P. and Shahabudeen, P. (2013) Genetic Algorithm for Concurrent Balancing of Mixed-Model Assembly Lines with Original Task Times of Models. Intelligent Information Management, 5, 84-92.

[29]   Panneerselvam, R. (2012) Design and Analysis of Experiments. PHI Learning Pvt. Ltd., New Delhi.

[30]   Demir, E. (2012) Models and Algorithms for the Pollution-Routing Problem and Its Variations. PhD Thesis, University of Southampton, Southampton.

[31]   SINTEF. Solomon’s Benchmark Instances.