Vehicle routing problem with time constraints
This paper addresses the Vehicle Routing Problem (VRP) with time constraints which been solved by several heuristic algorithms. The problem starting at the depot where the customer orders which associated with due date determined by customer, are released with different point of time. Ideally, to avoid any lateness in delivery process, the orders need to be delivered as soon as it released and available at the depot. However, this may increase the traveling cost because one vehicle needs to go and come back to depot for the other deliveries which this can be saved by batching the deliveries. Therefore, the study will focus on minimizing the tradeoff between traveling and tardiness costs. Literatures show that implementing the heuristic algorithms for solving various instances of VRPs manage to minimize the distribution cost within the reasonable computing times. An initial feasible solution was generated using a constructive heuristic. The solution then was improved by several metaheuristic algorithms were developed for solving the problem studied; Variable Neighborhood Search, Large Neighborhood Search and Tabu Search. To cater with the problem studied, a modification to the benchmark problems of Solomon has been done. The performance of the algorithms can be seen through the comparison of the solution obtained. The results showed that there is a significant saving in producing the least cost solution and manually constructed routes are very ineffective.
Kumar, S.N., and Panneerselvam, R, A Survey on Vehicle Routing Problem and Its Variants, Intelligent Information Management(2012), 4, 66-74.
BI.Kim, S.Kim, and S.Sahoo, Waste collection vehicle route problem with time window. Computers & Operational Research 33 (2006), pp.3624-3642.
N.Balakrishnan, Simple heuristics for the vehicle routeing problem with soft time windows. Journal of the Operational Research Society 44, 3 (1993), pp.279-287.
J.C.Chen, H. W. H. C. C., and C.Chen, Hybrid meta-heuristics for vehicle routing problem with time window constraints,In Service System and Service Management, 2009. ICSSSM`09. 6th International Conference Proceedings, International Conference on (2009), IEEE, pp. 766-771.
H.A.Min,Amultiobjective vehicle routing problem with soft time windows: the case of a public library distribution system. Socio-Economic Planning Sciences 25, 3 (1991), pp.179-188.
L.Bodin, B.Golden, A. Assad, and M.Ball, Routing and scheduling of vehicles and crews: The state of the art. COMP. & OPER. RES. 10, 2 (1983), pp.63-211.
M.Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research (1987), pp.254-265.
J.Cordeau, M.Gendreau, G.Laporte, J.Potvin,and F.Semet, A guide to vehicle routing heuristics. Journal of the Operational Research Society (2002), pp.512-522.
O.Braysy andM.Gendreau,Vehicle routing problem with time windows. Part I: Route construction and local search algorithms. Transportation Science 39, 1 (2005), pp.104-118.
O.Braysy andM.Gendreau,Vehicle routing problem with time windows. Part II: Metaheuristics. Transportation Science 39, 1 (2005), pp.119-139.
F.Liu, and S.Shen,An overview of a heuristic for vehicle routing problem with time windows. Computers & industrial engineering 37, 1-2 (1999), pp.331-334.
Figliozzi, M.A. The time dependent vehicle routing problem with time windows: Benchmarks problems, an efficient solution algorithm and solution characteristics, Transportation Research Part E 48 (2012), 616-636.
El-Sherbeny, N. Vehicle routing with time windows: An Overview of exact, heuristic and metaheuristic methods. Journal of King Sad University (Science) (2010), 121-131.
Taner, F., Galic, A. and Caric, T. Solving practical vehicle routing problem with time windows using metaheuristic algorithms, Traffic&Transportation, (2012), 24, 343-351.
Minocha, B. and Tripathi, S. Two phase algorithm for solving VRPTW problem. International Journal of Artificial Intelligence and Expert Systems (IJAE)(2013), 4, 1-16.
Mladenovic, N., and Hansen, P. Variable neighborhood search. Computers & Operations Research 24, 11(1997), 1097-1100.
L. Hong, An improved LNS algorithm for real-time vehicle routing problem with time windows. Computers & Operations Research 39 (2012), 151-163.
Stenger A., Vigo D., Enz S., Schwind M., An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping. Transportation Science 47 (1), 2013, 64-80.
Korsvik, J. E., Fagerholt, K., Laporte, G., A large neighbourhood search heuristic for ship routing and scheduling with split loads. Computers & Operations Research 38 (2011), 474-483.
Kovacs, A. A., Parragh S. N., and Hartl R. F., A template based adaptive large neighborhood search for the consistent vehicle routing problem. Networks 63 (1), 2014, 60-81.
Glover, F., and Laguna, M., Tabu search. 1997.
Marinakis, Y., and Migdalas, A., Heuristic solutions of vehicle routing problem in supply chain management. Series on Applied Mathematics-World Scientific Publishing Company-14 (2002), 205-236.
Cordeau, J., and Laporte, G., Tabu search heuristics for the vehicle routing problem. Metaheuristic Optimization via Memory and Evolution (2005), 145-163.
Moccia, L., Cordeau, J. F., and Laporte G., An incremental tabu search heuristic for the generalized vehicle routing problem with time windows. Journal of the Operational Research Society 63, (2012), 232-244.
R. Liu, X. Xie, Augusto, V., Rodriguez, C., Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research 230 (2013), 475-486.
Ceschia, S., Gaspero, L. D., Schaerf A., Tabu search techniques for the heterogeneous vehicle routing problem with time windows and carrier-dependent costs. Journal of Scheduling 14, 6 (2011), 601-615.
H. Lau, M. Sim, and K. Teo, Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research 148, 3 (2003), 559-569.
A. Lim, and F. Wang, A smoothed dynamic tabu search embedded GRASP for m-VRPTW. In Tools with Artificial Intelligence, 2004. ICTAI 2004. 16th IEEE International Conference on (2005), IEEE, pp. 704-708.
A. Lim, X. Zhang, A two-stage heuristic for the vehicle routing problem with time windows and a limited number of vehicles. In Proceedings of the 38th Hawaii International Conference on System Sciences (2005).
X. Wang, C. Xu, X. Hu, Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles. In Management Science and Engineering, 2008. ICMSE 2008.15th Annual Conference Proceedings. International Conference on (2008), IEEE, pp. 128-133.
Y. Park, A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines. International Journal of Production Economics 73, 2 (2011), 175-188.
K. H. Kang, B. K. Lee, Y. H. Lee, Y. H. Lee, A heuristic for the vehicle routing problem with due times. Computers & Industrial engineering 54 (2008), 421-431.
X.Wang, C.Xu, and X.Hu, Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles. In Management Science and Engineering, 2008. ICMSE 2008. 15th Annual Conference Proceedings, International Conference on (2008), IEEE, pp. 128-133.