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

Suresh Nanda Kumar, Ramasamy Panneerselvam

School of Management, Pondicherry University, Pondicherry, India.

DOI: 10.4236/jssm.2015.86085                

Abstract

The vehicle routing problem (VRP) is classified as an NP-hard problem. Hence exact optimization methods may be difficult to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. To get solutions in determining routes which are realistic and very close to the optimal solution, one has to use heuristics and meta-heuristics. In this paper, an attempt has been made to develop a GA based meta-heuristic to solve the time dependent vehicle route problem with time windows (TDVRPTW). This algorithm is compared with five other existing algorithms in terms of minimizing the number of vehicles used as well as the total distance travelled. The algorithms are implemented using Matlab and HeuristicLab optimization software. A plugin was developed using Visual C# and NET Framework 4.5. Results were tested using Solomon’s 56 benchmark instances (of which 24 instances are used with 4 in each of the 6 problem classes) classified into groups such as C1, C2, R1, R2, RC1, and RC2. For each of the performance measures, through a complete factorial experiment with two factors, it is proved that the proposed algorithm is the best among all the six algorithms compared in this paper.

Keywords

Vehicle Routing Problem, Exact Methods, Heuristics, Metaheuristics, VRPTW, TDVRPTW, Optimization, Genetic Algorithms, Tabu Search, Matlab, HeuristicLab

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bullnheimer, B., Hartl, R.F. and Strauss, C. (1997) Applying the Ant System to the Vehicle Routing Problem. Department of Management Science, University of Vienna.
[2]	Dantzig, G. and Ramser, J. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91. http://dx.doi.org/10.1287/mnsc.6.1.80
[3]	Clarke, G. and Wright, J.R. (1964) Scheduling of Vehicle Routing Problem from a Central Depot to a Number of Delivery Points. Operations Research, 12, 568-581. http://dx.doi.org/10.1287/opre.12.4.568
[4]	Laporte, G. (1992) The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59, 345-358. http://dx.doi.org/10.1016/0377-2217(92)90192-C
[5]	Gendreau, M., Laporte, G. and Potvin, J.-Y. (2002) Metaheuristics for the VRP. In: Toth, P. and Vigo, D., Eds., The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 129-154. http://dx.doi.org/10.1137/1.9780898718515.ch6
[6]	Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G. and Sormany, J.S. (2005) New Heuristics for the Vehicle Routing Problem. In: Langevin, A. and Riopel, D., Eds., Logistics Systems: Design and Optimization, Springer, New York, 279-297. http://dx.doi.org/10.1007/0-387-24977-x_9
[7]	Fu, L. (2002) Scheduling Dial-a-Ride Paratransit under Time-Varying, Stochastic Congestion. Transportation Research Part B, 36, 485-506. http://dx.doi.org/10.1016/S0191-2615(01)00014-5
[8]	Meng, Q., Lee, D.H. and Cheu, R. (2005) Multiobjective Vehicle Routing and Scheduling Problem with Time Window Constraints in Hazardous Material Transportation. Transportation Engineering, 131, 699-707. http://dx.doi.org/10.1061/(ASCE)0733-947X(2005)131:9(699)
[9]	Solomon, M. (1987) Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Operations Research, 35, 254-265. http://dx.doi.org/10.1287/opre.35.2.254
[10]	Malandraki, C. and Daskin, M.S. (1992) Time-Dependent Vehicle-Routing Problems—Formulations, Properties and Heuristic Algorithms. Transportation Science, 26, 185-200. http://dx.doi.org/10.1287/trsc.26.3.185
[11]	Hill, A.V. and Benton, W.C. (1992) Modeling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems. Journal of the Operational Research Society, 43, 343-351. http://dx.doi.org/10.1057/jors.1992.49
[12]	Ichoua, S., Gendreau, M. and Potvin, J.Y. (2003) Vehicle Dispatching with Time-Dependent Travel Times. European Journal of Operational Research, 144, 379-396. http://dx.doi.org/10.1016/S0377-2217(02)00147-9
[13]	Le Bouthillier, A. and Crainic, T.G. (2005) A Cooperative Parallel Meta-Heuristic for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 32, 1685-1708. http://dx.doi.org/10.1016/j.cor.2003.11.023
[14]	Blanton, J.L. and Wainwright, R.L. (1993) Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms. In: Forrest, S., Ed., Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann Publishing, San Francisco, 452-459.
[15]	Berger, J., Salois, M. and Begin, R.A. (1998) Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. Lecture Notes in Artificial Intelligence, 1418, 114-127. http://dx.doi.org/10.1007/3-540-64575-6_44
[16]	Thangiah, S.R., Osman, I.H. and Sun, T. (1995) Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows. Technical Report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury.
[17]	Potvin, J.-Y. and Bengio, S. (1996) The Vehicle Routing Problem with Time Windows—Part II: Genetic Search. INFORMS Journal on Computing, 8, 165-172. http://dx.doi.org/10.1287/ijoc.8.2.165
[18]	Zhu, Z. and Kenny, Q.L. (2000) A New Genetic Algorithm for VRPTW. National University of Singapore, Singapore.
[19]	Wee Kit, H., Chin, J. and Lim, A. (2001) A Hybrid Search Algorithm for the Vehicle Routing Problem with Time Windows. International Journal on Artificial Intelligence Tools, 10, 431-449. http://dx.doi.org/10.1142/S021821300100060X
[20]	Homberger, J. and Gehring, H. (2005) A Two-Phase Hybrid Meta-Heuristic for the Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 162, 220-238. http://dx.doi.org/10.1016/j.ejor.2004.01.027
[21]	David, M. and Bräysy, O. (2005) Active Guided Evolution Strategies for Large-Scale Vehicle Routing Problems with Time Windows. Computers & Operations Research, 32, 1593-1614. http://dx.doi.org/10.1016/j.cor.2003.11.017
[22]	Russell Robert, A. and Chiang, W.-C. (2006) Scatter Search for the Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 169, 606-622. http://dx.doi.org/10.1016/j.ejor.2004.08.018
[23]	Alba, E. and Dorronsoro, B. (2005) The Exploration/Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms. IEEE Transactions on Evolutionary Computation, 9, 126-142. http://dx.doi.org/10.1109/TEVC.2005.843751
[24]	Glover, F. (1993) Tabu Thresholding: Improved Search by Non-Monotonic Trajectories. Working Paper, Graduate School of Business, University of Colorado, Boulder, 80309-0419.
[25]	Glover, F. (1990) Tabu Search-Part II. ORSA Journal on Computing, 2, 4-32. http://dx.doi.org/10.1287/ijoc.2.1.4
[26]	Glover, F., Taillard, E. and de Werra, D. (1993) A User’s Guide to Tabu Search. Annals of Operations Research, 41, 3-28. http://dx.doi.org/10.1007/BF02078647
[27]	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. http://dx.doi.org/10.1109/ictai.2001.974461
[28]	Ichoua, S., Gendreau, M. and Potvin, J.Y. (2007) Planned Route Optimization for Real-Time Vehicle Routing. In: Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M. and Minis, I., Eds., Dynamic Fleet Management, Springer, New York, 1-18. http://dx.doi.org/10.1007/978-0-387-71722-7_1
[29]	Lau, H.C., Sim, M. and Teo, K.M. (2003) Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles. European Journal of Operational Research, 148, 559-569. http://dx.doi.org/10.1016/S0377-2217(02)00363-6
[30]	Malandraki, C. (1989) Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computational Experiments. PhD Dissertation, Northwestern University, Evanston.
[31]	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. http://dx.doi.org/10.1057/jors.1991.81
[32]	Malandraki, C. and Dial, R.B. (1996) A Restricted Dynamic Programming Heuristic Algorithm for the Time Dependent Travelling Salesman Problem. European Journal of Operational Research, 90, 45-55. http://dx.doi.org/10.1016/0377-2217(94)00299-1
[33]	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. http://dx.doi.org/10.1287/trsc.31.2.170
[34]	Fleischmann, B., Gietz, M. and Gnutzmann, S. (2004) Time-Varying Travel Times in Vehicle Routing. Transportation Science, 38, 160-173. http://dx.doi.org/10.1287/trsc.1030.0062
[35]	Jung, S. and Haghani, A. (2001) Genetic Algorithm for the Time-Dependent Vehicle Routing Problem. Transportation Research Record, 1771, 164-171. http://dx.doi.org/10.3141/1771-21
[36]	Donati, A.V., Montemanni, R., Casagrande, N., Rizzoli, A.E. and Gambardella, L.M. (2008) Time Dependent Vehicle Routing Problem with a Multi Ant Colony System. European Journal of Operational Research, 185, 1174-1191. http://dx.doi.org/10.1016/j.ejor.2006.06.047
[37]	Soler, D., Albiach, J. and Martínez, E. (2009) A Way to Optimally Solve a Time-Dependent Vehicle Routing Problem with Time Windows. Operations Research Letters, 37, 37-42. http://dx.doi.org/10.1016/j.orl.2008.07.007
[38]	Dabia, S., Van Woensel, T. and De Kok, A.G. (2010) A Dynamic Programming Approach to Multi-Objective Time-Dependent Capacitated Single Vehicle Routing Problems with Time Windows. Working Paper 313, School of Industrial Engineering, Eindhoven University of Technology, Eindhoven.
[39]	Kok, A.L. (2010) Congestion Avoidance and Break Scheduling within Vehicle Routing. PhD Thesis, University of Twente, Enschede.
[40]	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.
[41]	van Woensel, T., 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. http://dx.doi.org/10.1016/j.ejor.2007.03.012
[42]	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. http://dx.doi.org/10.1016/j.ejor.2010.10.017
[43]	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. http://dx.doi.org/10.1016/j.cie.2009.07.006
[44]	Bettinelli, A., Ceselli, A. and 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. http://dx.doi.org/10.1016/j.trc.2010.07.008
[45]	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. http://dx.doi.org/10.4236/iim.2013.53009
[46]	Figliozzi, M.A. (2012) The Time Dependent Vehicle Routing Problem with Time Windows: Benchmark Problems, an Efficient Solution Algorithm, and Solution Characteristics. Transportation Research Part E, 48, 616-636. http://dx.doi.org/10.1016/j.tre.2011.11.006
[47]	Thompson, P.M. and Psaraftis, H. (1989) Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems. Operations Research, 41, 935-946. http://dx.doi.org/10.1287/opre.41.5.935
[48]	Thangiah, S.R., Nygard, K.E. and Juell, P.L. (1991) GIDEON: A Genetic Algorithm System for Vehicle Routing with Time Windows. In: Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications, IEEE Computer Society Press, Los Alamitos, 322-328. http://dx.doi.org/10.1109/caia.1991.120888
[49]	Potvin, J.-Y., Kervahut, T., Garcia, B.-L. and Rousseau, J.-M. (1992) A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows. Technical Report, CRT-855, Centre de Recherchesur les Transports, Universite de Montreal, Montreal.
[50]	Haghani, A. and Jung, S. (2005) A Dynamic Vehicle Routing Problem with Time-Dependent Travel Times. Computers & Operations Research, 32, 2959-2986. http://dx.doi.org/10.1016/j.cor.2004.04.013
[51]	Panneerselvam, R. (2012) Design and Analysis of Experiments. PHI Learning Pvt. Limited, New Delhi.
[52]	SINTEF. Solomon’s Benchmark Instances. https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark/
[53]	Kumar, S.N. and Panneerselvam, R. (2015) A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm. Intelligent Information Management, 7, 181-194. http://dx.doi.org/10.4236/iim.2015.74015
[54]	Chu, C.-P., Chen, C.-C., Ho, M.-C. and Wang, C.-Y. (2013) Time-Dependent Vehicle Routing Problems with Time Windows and Split Delivery in City Logistics. Proceedings of the Eastern Asia Society for Transportation Studies, 9.