A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm

Suresh Nanda Kumar¹, Ramasamy Panneerselvam²

¹Doctoral Candidate, School of Management, Pondicherry University, Pondicherry, India.
²Professor, School of Management, Pondicherry University, Pondicherry, India.

DOI: 10.4236/iim.2015.74015                

Abstract

The 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 actual solution, we use heuristics and metaheuristics which are of the combinatorial optimization type. A literature review of VRPTW, TDVRP, and a metaheuristic such as the genetic algorithm was conducted. In this paper, the implementation of the VRPTW and its extension, the time-dependent VRPTW (TDVRPTW) has been carried out using the model as well as metaheuristics such as the genetic algorithm (GA). The algorithms were implemented, using Matlab and HeuristicLab optimization software. A plugin was developed using Visual C# and DOT NET framework 4.5. Results were tested using Solomon’s 56 benchmark instances classified into groups such as C1, C2, R1, R2, RC1, RC2, with 100 customer nodes, 25 vehicles and each vehicle capacity of 200. The results were comparable to the earlier algorithms developed and in some cases the current algorithm yielded better results in terms of total distance travelled and the average number of vehicles used.

Keywords

Vehicle Routing Problem, Exact Methods, Heuristics, Metaheuristics, VRPTW, TDVRPTW, Optimization, Genetic Algorithms, Matlab, HeuristicLab, C#, DOT NET

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.L. (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 5th 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.
[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, K.Q.L. (2000) A New Genetic Algorithm for VRPTW. National University of 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]	Mester, D. 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, R.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]	Malandraki, C. (1989) Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computational Experiments. PhD Dissertation, Northwestern University, Evanston.
[25]	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. http://dx.doi.org/10.1057/jors.1991.81
[26]	Malandraki, C. and Dial, R.B. (1996) A Restricted Dynamic Programming Heuristic Algorithm for the Time Dependent Traveling Salesman Problem. European Journal of Operational Research, 90, 45-55. http://dx.doi.org/10.1016/0377-2217(94)00299-1
[27]	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
[28]	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
[29]	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
[30]	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
[31]	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
[32]	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, Eindhoven University of Technology, School of Industrial Engineering, Netherl-ands.
[33]	Kok, A.L. (2010) Congestion Avoidance and Break Scheduling within Vehicle Routing. PhD Thesis, University of Twente, Enschede.
[34]	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, 616-636.
[35]	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
[36]	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
[37]	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
[38]	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
[39]	Rodger J.A. (2014) Application of a Fuzzy Feasibility Bayesian Probabilistic Estimation of Supply Chain Backorder Aging, Unfilled Backorders, and Customer Wait Time Using Stochastic Simulation with Markov Blankets. Expert Systems with Applications, 41, 7005-7022. http://dx.doi.org/10.1016/j.eswa.2014.05.012
[40]	Tuysuz, F. and Kahraman, C. (2010) Modeling a Flexible Manufacturing Cell Using Stochastic Petri Nets with Fuzzy Parameters. Expert Systems with Applications, 37, 3910-3920. http://dx.doi.org/10.1016/j.eswa.2009.11.026
[41]	Toktas-Palut, P. and Ulengin, F. (2011) Coordination in a Two-Stage Capacitated Supply Chain with Multiple Suppliers. European Journal of Operational Research, 212, 43-53. http://dx.doi.org/10.1016/j.ejor.2011.01.018
[42]	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.
[43]	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
[44]	Gambardella, L.M. (1999) MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. McGraw-Hill, London, 63-76.
[45]	Stegers, E. (2009) A Solution Method for Vehicle Routing Problems with Time-Dependent Travel Times. Masters Thesis, Delft University of Technology, Delft.
[46]	SINTEF. Solomon’s Benchmark Instances. https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark/