Volume List  / Volume 9 (1)

Article

A REAL-WORLD CASE STUDY OF A VEHICLE ROUTING PROBLEM UNDER UNCERTAIN DEMAND

DOI: 10.7708/ijtte.2019.9(1).08


9 / 1 / 101-117 Pages

Author(s)

Anan Mungwattana - Industrial Engineering Department, Kasetsart University, Bangkok, Thailand -

Kusuma Soonpracha - College of Logistics and Supply Chain, Sripatum University, Bangkok, Thailand -

Gerrit K. Janssens - Campus Diepenbeek, Research Group Logistics, Universiteit Hasselt University, Hasselt, Belgium -


Abstract

The research scope of the real-world logistics industry case study is extended by taking uncertainty in customer demand into account. The particular vehicle routing planning parameters of the logistics provider under study are formulated and are used in two algorithms. The algorithms solve practical problem cases considering a limited number of drivers and a limited company’s fleet size but unlimited when considering outsourcing. All trucks are allowed to service multiple trips. The computation is based on real-life data sets. The analysis of the running time and the total transportation cost are compared among three competitive methods. The methods are: the technique based on the company’s know-how, a genetic algorithm hybridized with three search operators, and a deterministic annealing hybridized with three search operators. The developed schemes have been proven successful to obtain a near-optimal solution within a reasonable running time. Furthermore, the adaptation of the minimax concept is embedded into the algorithms to find a robust solution for the worst case scenario subject to handling fluctuating situations in demand. In the last phase, two indicators comprising the extra cost and the unmet demand ratios are proposed to help a decision maker to obtain a better view on his decision.


Download Article

Number of downloads: 87


References:

Agra, A.; Christiansen, M.; Figueiredo, R.; Hvattum, L.M.; Poss, M.; Requejo, C. 2013. The robust vehicle routing problem with time windows, Computers and Operations Research 40(3): 856-866.

 

Battarra, M.; Monaci, M.; Vigo, D. 2009. An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem, Computers & Operations Research 36: 3041-3050.

 

Belfiore, P.; Tsugunobu, H.; Yoshizaki, Y. 2009. Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil, European Journal of Operational Research 199: 750–758.

 

Braekers, K.; Caris, A.; Janssens, G. K. 2011. A deterministic annealing algorithm for a bi-objective full truckload vehicle routing problem in drayage operations, Procedia Social and Behavioral Sciences 20: 344–353.

 

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 65: 50–69.

 

Braekers, K.; Ramaekers, K.; Van Nieuwenhuyse, I. 2016. The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering 99: 300–313.

 

Bräysy, O.; Dullaert, W.; Hasle, G.; Mest, D. 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.

 

Caceres-Cruz, J.; Arias, P.; Guimarans, D.; Riera, D.; Juan, A.A. 2014. Rich vehicle routing problem: survey, ACM Computing Surveys 47(2): 1-28.

 

Caris, A.; Janssens, G. K. 2010. A deterministic annealing heuristic for the pre- and end-haulage of intermodal container terminals, International Journal of Computer Aided Engineering and Technology 2(4): 340–355.

 

Dueck, G.; Scheuer, T. 1990. Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics 90(1): 161–175.

 

Gendreau, M.; Laporte, G.; Seguin, R. 1995. An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transportation Science 29(2): 143–155.

 

Gendreau, M.; Laporte, G.; Seguin, R. 1996. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Operations Research 44(3): 469–477.

 

Hartl, R.F.; Hasle, G.; Janssens, G.K. 2006. Special issue on rich vehicle routing problems, Central European Journal of Operations Research 14(2): 103–104.

 

Hasle, G.; Kloster, O. 2007. Industrial vehicle routing. In G. Hasle, K.A. Lie, and E. Quak (eds.). Geometric Modelling, Numerical Simulation, and Optimization, Springer, Berlin, Heidelberg, 397–435.

 

Haughton, M. A. 1998. The performance of route modification and demand stabilization strategies in stochastic vehicle routing, Transportation Research Part B: Methodological 32(8): 551–566.

 

Janssens, G.K.; Caris, A.; Ramaekers, K. 2009. Time Petri nets as an evaluation tool for handling travel time uncertainty in vehicle routing solutions, Expert Systems with Applications 36(3): 5987-5991.

 

Janssens, G. K.; Soonpracha, K.; Manisri, T.; Mungwattana, A. 2015. Robust Vehicle Routing Solutions to Manage Time Windows in the Case of Uncertain Travel Times. In: P. Vasant, ed. Handbook of Research on Artificial Intelligence Techniques and Algorithms. IGI Global, 655-678.

 

Kouvelis, P.; Yu, G. 1996. Robust discrete optimization and its applications. Dordrecht: Kluwer academic publishers.

 

Laporte, G.; Louveaux, F.; Mercure, H. 1992. The vehicle routing problem with stochastic travel times, Transportation Science 26(3): 161–170.

 

Lee, C.; Lee, K.; Park, S.-H. 2012. Robust vehicle routing problem with deadlines and travel time/demand uncertainty, The Journal of the Operational Research Society 63(9): 1294-1306.

 

Mancini, S. 2015. A real-life multi-depot multi-period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic, Transportation Research Part C Emerging Technologies 70: 100-112.

 

Manisri, T.; Mungwattana, A. 2012. Comparing the Solutions for Vehicle Routing Problem with Uncertain Travel Times by Robustness Approach, International Journal of Logistics and Transport 63-76.

 

Manisri, T.; Mungwattana, A.; Janssens, G. K. 2011. Minimax optimisation approach for the robust vehicle routing problem with time windows and uncertain travel times, International Journal of Logistics Systems and Management 10(4): 461-477.

 

Moghaddam, B. F.; Ruiz, R.; Sadjadi, S. J. 2012. Vehicle routing with uncertain demands: an advanced particle swarm algorithm, Computers & Industrial Engineering 62(1): 306–317.

 

Mulvey, J. M.; Vanderbei, R. J.; Zenios, S. A. 1995. Robust optimization of large-scale systems, Operations Research 43(2): 264-281.

 

Mungwattana, A.; Soonpracha, K.; Manisri, T. 2016. A practical case study of a heterogeneous fleet vehicle routing problem with various constraints. In Proceedings of the 2016 International Conference on Industrial Engineering and Operations Management, Kuala Lumpur, Malaysia, 948-957.

 

Pace, S.; Turky, A.; Aleti, A.; Moser, I. 2015. Distributing fibre boards: a practical application of the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints, Procedia Computer Science 51: 2257-2266.

 

Salhi, S.; Imran, A.; Salhi, S. 2014. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation, Computers & Operations Research 52: 315–325.

 

Soonpracha, K.; Mungwattana, A.; Manisi, T. 2014. A Three-Phase Algorithm for Solving a Fleet Size and Mix Vehicle Routing Problem with Time Windows Uncertain Demands, Sripatum Review of Science and Technology, 6: 77-89.

 

Soonpracha, K.; Mungwattana, A.; Manisri, T. 2015. A re-constructed meta-heuristic algorithm for robust fleet size and mix vehicle routing problem with time windows under uncertain demands. In Proceedings of the 18th Asia-Pacific Symposium on Intelligent and Evolutionary Systems, Springer, 347-361.

 

Sungur, F.; Ordonez, F.; Dessouky, M. M. 2008. A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty, IIE Transactions 40(5): 509–523.

 

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

 

Toth, P.; Vigo D. 2014. Vehicle Routing: Problems, Methods and Applications (2nd ed.), MOS-SIAM Series on Optimization.

 

Wang, B.; Xia, X.; Meng, H.; Li, T. 2017. Bad-scenario-set Robust Optimization Framework With Two Objectives for Uncertain Scheduling Systems, IEEE/CAA Journal of Automatica Sinica 4(1): 143-153.

 

Xu, Y.; Wang, L.; Yang, Y. 2012. A New Variable Neighborhood Search Algorithm for the Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows, Electronic Notes in Discrete Mathematics 39: 289–296.

 

Yin, Y.; Madanat, S.; Lu, X.-Y. 2009. Robust improvement schemes for road networks under demand uncertainty, European Journal of Operational Research 198(2): 470-479.

 

Zhang, Y.; Chen, X. 2014. An Optimization Model for the Vehicle Routing Problem in Multiproduct Frozen Food Delivery, Journal of Applied Research and Technology 12: 239-250.