Abstract
Recent work of the fleet size and mix vehicle routing problem with time windows mostly assumes that the input variables are deterministic. Practice in the real world, however, faces considerable uncertainty in the data. But recent research studies lack emphasis on this uncertainty. This paper focuses to contribute to a new challenging study by considering the customer demand as uncertain. This characteristic increases the difficulty for solving. The meta-heuristic algorithms are developed consisting a modification of a genetic algorithm and an adaptation of a greedy search hybridized with inter-route neighborhood search methods. Because this paper relates to uncertain customer demands, decision making is performed using the robust approach based on worst case scenarios. The final results are evaluated by using the extra cost and the unmet demand against the deterministic approach to balance the decision making.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Soonpracha, K., Mungwattana, A., Janssens, G.K., Manisri, T.: Heterogeneous VRP Review and Conceptual Framework. In: The International MultiConference of Engineers and Computer Scientists, APIEMS 2014, Hong Kong, pp. 1052–1059 (2014)
Hoff, A., Andersson, H., Christiansen, M., Hasle, G., Lokketangen, A.: Industrial aspects and literature survey: fleet composition and routing. Computers & Operations Research 37(12), 2041–2061 (2010)
Baldacci, R., Battarra, M., Daniele, V.: Routing a heterogeneous fleet of vehicles. Technical Report DEIS OR.INGCE. 1 (2007)
Osman, I.H., Salhi, S.: Local search strategies for the vehicle fleet mix problem. In: Rayward-Smith, V., Osman, I., Reeves, C.R., Smith, G. (eds.) Modern Heuristic Search Methods, pp. 131–154. John Wiley & Sons, Chichester (1996)
Renaud, J., Boctor, F.F.: A sweep-based algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research 140, 618–628 (2002)
Gendreau, M., Laporte, G., Musaraganyi, C., Taillard, É.D.: A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research 26, 1153–1173 (1999)
Wassan, N.A., Osman, I.H.: Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society 53, 768–782 (2002)
Brandão, J.: A deteministic tabu search algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research 195, 716–728 (2009)
Liu, S., Huang, W., Ma, H.: An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E 45, 434–445 (2009)
Prins, C.: Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence 22, 916–928 (2009)
Baldacci, R., Mingozzi, A.: A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming 120, 347–380 (2009)
Subramanian, A., Penna, P.H.V., Uchoa, E., Ochi, L.S.: A Hybrid Algorithm for the Fleet Size and Mix Vehicle Routing Problem. In: International Conference on Industrial Engineering and Systems Management (2011)
Redmer, A., Żak, J., Sawicki, P., Maciejewski, M.: Heuristic approach to fleet composition problem. Social and Behavioral Sciences 54, 414–427 (2012)
Penna, P.H.V., Subramanian, A., Ochi, L.S.: An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics 19(2), 201–232 (2011)
Dullaert, W., Janssens, G.K., Sörensen, K., Vernimmen, B.: New heuristics for the fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research Society (2002)
Amico, M.D., Monaci, M., Pagani, C., Vigo, D.: Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Transportation Science 41(4), 516–526 (2007)
Belfiore, P.P., Fávero, L.P.L.: Scatter search for the fleet size and mix vehicle routing problem with time windows. Central European Journal of Operations Research 15, 351–368 (2007)
Bräysy, O., Dullaert, W., Hasle, G., Mest, D.: An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle routing problem with time windows. Transportation Science 42(3), 371–386 (2008)
Bräysy, O., Porkka, P.P., Dullaert, W., Repoussis, P.P., Tarantilis, C.D.: A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows. Expert Systems with Applications 36(4), 8460–8475 (2009)
Repoussis, P., Tarantilis, C.: 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 (2010)
Belfiore, P., Yoshizaki, H.T.: 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 (2009)
Belfiore, P., Yoshizaki, H.T.: Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Computers & Industrial Engineering 64, 589–601 (2013)
Salhi, S., Sari, M.: A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European Journal of Operational Research 103, 95–112 (1997)
Baldacci, R., Mingozzi, A.: A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming 120, 347–380 (2009)
List, G.F., Wood, B., Nozick, L.K., Turnquist, M.A., Jones, D.A., Kjeldgaard, E.A., Lawton, C.R.: Robust optimization for fleet planning under uncertainty. Transportation Research Part E 39, 209–227 (2002)
Sungur, I., Ordónez, F., Dessouky, M.: A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. Inst. Ind. Eng. Trans. 40(5), 509–523 (2008)
Janssens, G.K., Caris, A., Ramaekers, K.: Time Petri nets as an evaluation tool for handling travel time uncertainty in vehicle routing solutions. Expert Systems with Applications 36, 5987–5991 (2009)
Yin, Y., Madanat, S.M., Lu, X.-Y.: Robust improvement schemes for road networks under demand uncertainty. European Journal of Operational Research 198, 470–479 (2009)
Sörensen, K., Sevaux, M.: A Practical Approach for Robust and Flexible Vehicle Routing Using Metaheuristics and Monte Carlo Sampling. Journal of Mathematical Modelling and Algorithms 8, 387–407 (2009)
Moghaddam, B.F., Sadjadi, S.J., Seyedhosseini, S.M.: Comparing mathematical and heuristic methods. International Journal of Research and Reviews in Applied Sciences 2(2), 108–116 (2010)
Zhu, J., Gao, M., Huang, J.: A robust approach to vehicle routing for medical supplies in large-scale emergencies. In: International Symposium on Emergency Management (ISEM 2009) (December 2009)
Aguirre, A., Coccola, M., Zamarripa, M., Méndez, C., Espuña, A.: A robust MILP-based approach to vehicle routing problems with uncertain demands. In: 21st European Symposium on Computer Aided Process Engineering - ESCAPE 21, pp. 633–637 (2011)
Manisri, T., Mungwattana, A., Janssens, G.K.: 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 (2011)
Moghaddam, B.F., Ruiz, R., Sadjadi, S.J.: Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Computers & Industrial Engineering 62, 306–317 (2012)
Goodson, J.C., Ohlmann, J.W., Thomas, B.W.: Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. European Journal of Operational Research 217, 312–323 (2012)
Jabali, O., Gendreau, M., Laporte, G.: A continuous approximation model for the fleet compositon problem. Transportation Research Part B 46, 1591–1606 (2012)
Kouvelis, P., Yu, G.: Robust discrete optimization and its applications. Kluwer Academic Publishers, Dordrecht (1996)
Kirk, J.: Mathlab Central (2007), http://www.mathworks.com
Dasgupta, S., Papadimitriou, C., Vazirani, U.V.: Algorithms, 1st edn., McGraw-Hill Science/Engineering/Math. (2006)
Solomon, M.M.: VRPTW Benchmark Problems (2005), http://w.cba.neu.edu/~msolomon/problems.html
Cachon, G., Terwiesch, C.: Matching Supply with Demand: An Introduction to Operations Management, 3rd edn. McGraw-Hill (2011)
Liu, F.H., Shen, S.Y.: The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research Society 50, 721–732 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
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: Handa, H., Ishibuchi, H., Ong, YS., Tan, KC. (eds) Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems - Volume 2. Proceedings in Adaptation, Learning and Optimization, vol 2. Springer, Cham. https://doi.org/10.1007/978-3-319-13356-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-13356-0_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13355-3
Online ISBN: 978-3-319-13356-0
eBook Packages: EngineeringEngineering (R0)