Volume List  / Volume 6 (2)

Article

A SOLUTION FOR THE BI-OBJECTIVE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS USING LOCAL SEARCH AND GENETIC ALGORITHMS

DOI: 10.7708/ijtte.2016.6(2).03


6 / 2 / 149-158 Pages

Author(s)

Anan Mungwattana - Kasetsart University, Bangkok, Thailand -

Tharinee Manisri - Sripatum University, Bangkok, Thailand -

Kanjanaporn Charoenpol - Surindra Rajabhat University, Surin, Thailand -

Gerrit K. Janssens - Hasselt University, Diepenbeek, Belgium -


Abstract

This paper deals with the vehicle routing problem with time windows (VRPTW). The VRPTW routes a set of vehicles to service customers having two-sided time windows, i.e. earliest and latest start of service times. The demand requests are served by capacitated vehicles with limited travel times to return to the depot. The purpose of this paper is to develop a hybrid algorithm that uses the modified push forward insertion heuristic (MPFIH), a λ-interchange local search descent method (λ-LSD) and a genetic algorithm to solve the VRPTW with two objectives. The first objective aims to determine the minimum number of vehicles required and the second is to find the solution that minimizes the total travel time. A set of well-known benchmark problems are used to compare the quality of solutions. The results show that the proposed algorithm provides effective solutions compared with best found solutions and better than another heuristic used for comparison.


Download Article

Number of downloads: 834


Acknowledgements:

This work is supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office (research project COMEX, Combinatorial Optimization: Metaheuristics & Exact Methods).


References:

Belfiore, P.P.; Fávero, L.P. 2007. Scatter search for the fleet size and mix vehicle routing problem with time windows, Central European Journal of Operations Research, 15(4): 351-368.

 

Berger, J.; Barkaoui, M. 2004. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, 31(12): 2037-2053.

 

Bräysy, O.; Gendreau, M. 2005a. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms, Transportation Science, 39(1):104-118.

 

Bräysy, O.; Gendreau, M. 2005b. Vehicle routing problem with time windows, Part II: Metaheuristics, Transportation Science, 39(1): 119-139.

 

Bräysy, O.; Dullaert, W.; Hasle, G.; Mester, D.; Gendreau, M. 2008. An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle routing problem with time windows, Transportation Science, 42(3): 371-386.

 

Braekers, K.; Caris, A.; Janssens, G.K. 2014. Bi-objective optimization of drayage operations in the service area of intermodal terminals, Transportation Research Part E: Logistics and Transportation Review, 65: 50-69.

 

Christofides, N. 1985. Vehicle Routing. In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B.Schmoys (eds.), The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization, Chapter 12, Wiley, Chichester.

 

Cordeau, J.-F.; Gendreau, M.; Laporte, G.; Potvin, J.-Y.; Semet, F. 2002. A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53(5): 512-522.

 

Dell’ Amico, M.; Monaci, M.; Pagani, C.; Vigo, D. 2007. Heuristic approaches for the fleet size and mix vehicle routing problem with time windows, Transportation Science, 41(4): 516-526.

 

Dullaert, W.; Janssens, G.K.; Sörensen, K.; Vernimmen, B. 2002. New heuristics for the fleet size and mix vehicle routing problem with time windows, Journal of the Operational Research Society (UK), 53(11): 1232-1238.

 

Garcia-Najera, A.; Bullinaria, J.A. 2011. An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows, Computers & Operations Research, 38(1): 287-300.

 

Ghoseiri, K.; Ghannadpour, S.F. 2010. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Applied Soft Computing, 10(4): 1096-1107.

 

Hartl, R.F; Hasle, G.; Janssens, G.K. 2006. Editorial to the Special Issue on Rich Vehicle Routing Problems, Central European Journal of Operations Research, 14(2): 103-104.

 

Jozefowiez, N.; Semet, F.; Talbi, E. 2008. Multi-objective vehicle routing problems, European Journal of Operational Research, 189(2): 293-309.

 

Manisri, T.; Mungwattana, A.; Janssens, G.K. 2009. Algorithm for the Multi-objective Vehicle Routing Problem with Time Windows. In Proceedings of the 5th International Congress on Logistics and Supply Chain Management Systems, Seoul, South Korea.

 

Mitrinovic-Minic, S.; Laporte, G. 2006. The pickup and delivery problem with time windows and transshipment, INFOR, 44(3): 217-227.

 

Ombuki, B.; Ross, B.J.; Hanshar, F. 2006. Multi-objective genetic algorithms for vehicle routing problem with time windows, Applied Intelligence, 24(1): 17-30.

 

Osman, I. 1993. Metastrategy simulated annealing and tabu search for the vehicle routing problem, Annals of Operations Research, 41(4): 421-451.

 

Osman, I.H.; Christofides, N. 1994. Capacitated clustering problems by hybrid simulated annealing and tabu search, International Transactions in Operational Research, 1(3): 317-336.

 

Repoussis, P.; Tarantilis, C. 2010. Solving the fleet size and mix vehicle routing problem with time windows via adaptive memory, Transportation Research Part C: Emerging Technologies, 18(5): 695-712.

 

Savelsbergh, M.W.P. 1985. Local search for routing problems with time windows, Annals of Operations Research, 4(1-4): 285-305.

 

Solomon, M.M. 2008. VRPTW benchmark problems, Available from Internet: http://web.cba.neu.edu/~msolomon/problems.htm.

 

Tan, K.C.; Chew, Y.H.; Lee, L.H. 2006. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Computational Optimization and Applications, 34(1): 115-151.

 

Tarantilis, C.D.; Kiranoudis, C.T.; Vassiliadis, V.S. 2004. A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, European Journal of Operational Research, 152(1): 148-158.