A THREE-PHASE ALGORITHM FOR SOLVING A FLEET SIZE AND MIX VEHICLE ROUTING PROBLEM WITH TIME WINDOWS UNCERTAIN DEMANDS
Article Sidebar
Published:
Apr 26, 2018
Keywords:
Robustness Fleet size and mix vehicle routing problem with time windows Uncertain demand Modified genetic algorithm Insertion search algorithm
Main Article Content
Abstract
This paper focuses to contribute to a new challenging study of a fleet size and mix vehicle routing problem by considering the additional variants of time windows constraint under uncertain demands. A methodology of three-phase algorithm is proposed for solving this particular problem. The major techniques are consisting of a modified genetic algorithm, a two-step of random route merging and splitting operation, and a robustness decision making based on worst case scenarios operation. The performance of the robust solution is evaluated by using the extra cost, the unmet demand against the deterministic approach. Moreover, the deterministic solution obtained from the proposed scheme yields the good result after compared with the previous outcomes of the other authors.
Article Details
Section
บทความวิจัย
References
Aguirre, A., Coccola, M., Zamarripa, M., Méndez, C., & Espuña, A. (2011). A robust MILP-based approach to vehicle routing problems with uncertain demands. (E. N. Pistikopoulos, M. C. Georgiadis, & A. Kokos, Eds.) 21st European Symposium on Computer Aided Process Engineering – ESCAPE 21, 633-637.
Amico, M. D., 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.
Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120, 347–380.
Baldacci, R., Battarra, M., & Daniele, V. (2007). Routing a heterogeneous fleet of vehicles. Technical Report DEIS OR.INGCE, 1.
Belfiore, P. P., & Fávero, L. P. (2007). Scatter search for the fleet size and mix vehicle routing problem with time windows. CEJOR(15), 351–368.
Belfiore, P., & Yoshizaki, H. T. (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.
Belfiore, P., & Yoshizaki, H. T. (2013). Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Computers & Industrial Engineering, 64, 589–601.
Brandão, J. (2009). A deteministic tabu search algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 195, 716-728.
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.
Bräysy, O., Porkka, P. P., Dullaert, W., Repoussis, P. P., & Tarantilis, C. D. (2009). A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows. Expert Systems with Applications, 36(4), 8460–8475.
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 Operation Research Society.
Gendreau, M., Laporte, G., Musaraganyi, C., & Taillard, É. D. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 26, 1153-1173.
Goodson, J. C., Ohlmann, J. W., & Thomas, B. W. (2012). Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. European Journal of Operational Research, 217, 312–323.
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, 5987–5991.
Janssens, G. K., Soonpracha, K., Manisri, T., & Mungwattana, A. (2014). 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. Malaysia: IGI.
Kouvelis, P., & Yu, G. (1996). Robust discrete optimization and its applications. Dordrecht, The Netherlands: Kluwer academic publishers.
Liu, F. H., & Shen, S. Y. (1999). The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Reseach Society, 721-732.
Liu, S., Huang, W., & Ma, H. (2009). An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E, 45, 434-445.
Manisri, T. (2009). The Probability Scenario-Based Approach for a Vehicle Routing Problem with Uncertain Travel Times. Sripatum Review, Vol. 1 No.1, 5-12.
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 problem with uncertain demands: An advanced particle swarm algorithm. Computers & Industrial Engineering, 62, 306–317.
Moghaddam, B. F., Sadjadi, S. J., & Seyedhosseini, S. M. (2010). Comparing Mathematical and Heuristic Methods. IJRRAS, 2(2), 108-116.
Osman, I. H., & Salhi, S. (1996). Local search strategies for the vehicle fleet mix problem. In Modern heuristic search methods. (V. Rayward-Smith, I. Osman, C. R. Reeves, & G. Smith, Eds.) Chichester, UK: John Wiley & Sons.
Penna, P. H., Subramanian, A., & Ochi, L. S. (2011). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19(2), 201-232.
Prins, C. (2002). Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case. Journal of Mathematical Modelling and Algorithms, 1, 135-150.
Renaud, J., & Boctor, F. F. (2002). A sweep-based algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 140, 618-628.
Repoussis, P., & Tarantilis, C. (2010). An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle routing problem with time windows. Transportation Research Part C, 18, 695–712.
Salhi, S., & Sari, M. (1997). A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European Journal of Operational Research, 103, 95-112.
Solomon , M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time windows constraints. Operational Research, 33(1), 254-265.
Soonpracha, K., Mungwattana, A., Janssens, G. K., & Manisri, T. (2014). Heterogeneous VRP Review and Conceptual Framework. The International MultiConference of Engineers and Computer Scientists, (pp. 5012-5019). Hong Kong.
Sörensen, K., & Sevaux, M. (2009). A Practical Approach for Robust and Flexible Vehicle Routing Using Metaheuristics and Monte Carlo Sampling. J Math Model Algor, 8, 387–407.
Subramanian, A., Penna, P. H., Uchoa, E., & Ochi, L. S. (2011). A Hybrid Algorithm for the Fleet Size and Mix Vehicle Routing Problem. International Conference on Industrial Engineering and Systems Management.
Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. Inst. Ind. Eng. Trans., 40(5), 509-523.
Amico, M. D., 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.
Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120, 347–380.
Baldacci, R., Battarra, M., & Daniele, V. (2007). Routing a heterogeneous fleet of vehicles. Technical Report DEIS OR.INGCE, 1.
Belfiore, P. P., & Fávero, L. P. (2007). Scatter search for the fleet size and mix vehicle routing problem with time windows. CEJOR(15), 351–368.
Belfiore, P., & Yoshizaki, H. T. (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.
Belfiore, P., & Yoshizaki, H. T. (2013). Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Computers & Industrial Engineering, 64, 589–601.
Brandão, J. (2009). A deteministic tabu search algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 195, 716-728.
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.
Bräysy, O., Porkka, P. P., Dullaert, W., Repoussis, P. P., & Tarantilis, C. D. (2009). A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows. Expert Systems with Applications, 36(4), 8460–8475.
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 Operation Research Society.
Gendreau, M., Laporte, G., Musaraganyi, C., & Taillard, É. D. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 26, 1153-1173.
Goodson, J. C., Ohlmann, J. W., & Thomas, B. W. (2012). Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. European Journal of Operational Research, 217, 312–323.
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, 5987–5991.
Janssens, G. K., Soonpracha, K., Manisri, T., & Mungwattana, A. (2014). 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. Malaysia: IGI.
Kouvelis, P., & Yu, G. (1996). Robust discrete optimization and its applications. Dordrecht, The Netherlands: Kluwer academic publishers.
Liu, F. H., & Shen, S. Y. (1999). The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Reseach Society, 721-732.
Liu, S., Huang, W., & Ma, H. (2009). An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E, 45, 434-445.
Manisri, T. (2009). The Probability Scenario-Based Approach for a Vehicle Routing Problem with Uncertain Travel Times. Sripatum Review, Vol. 1 No.1, 5-12.
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 problem with uncertain demands: An advanced particle swarm algorithm. Computers & Industrial Engineering, 62, 306–317.
Moghaddam, B. F., Sadjadi, S. J., & Seyedhosseini, S. M. (2010). Comparing Mathematical and Heuristic Methods. IJRRAS, 2(2), 108-116.
Osman, I. H., & Salhi, S. (1996). Local search strategies for the vehicle fleet mix problem. In Modern heuristic search methods. (V. Rayward-Smith, I. Osman, C. R. Reeves, & G. Smith, Eds.) Chichester, UK: John Wiley & Sons.
Penna, P. H., Subramanian, A., & Ochi, L. S. (2011). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19(2), 201-232.
Prins, C. (2002). Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case. Journal of Mathematical Modelling and Algorithms, 1, 135-150.
Renaud, J., & Boctor, F. F. (2002). A sweep-based algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 140, 618-628.
Repoussis, P., & Tarantilis, C. (2010). An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle routing problem with time windows. Transportation Research Part C, 18, 695–712.
Salhi, S., & Sari, M. (1997). A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European Journal of Operational Research, 103, 95-112.
Solomon , M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time windows constraints. Operational Research, 33(1), 254-265.
Soonpracha, K., Mungwattana, A., Janssens, G. K., & Manisri, T. (2014). Heterogeneous VRP Review and Conceptual Framework. The International MultiConference of Engineers and Computer Scientists, (pp. 5012-5019). Hong Kong.
Sörensen, K., & Sevaux, M. (2009). A Practical Approach for Robust and Flexible Vehicle Routing Using Metaheuristics and Monte Carlo Sampling. J Math Model Algor, 8, 387–407.
Subramanian, A., Penna, P. H., Uchoa, E., & Ochi, L. S. (2011). A Hybrid Algorithm for the Fleet Size and Mix Vehicle Routing Problem. International Conference on Industrial Engineering and Systems Management.
Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. Inst. Ind. Eng. Trans., 40(5), 509-523.