A THREE-PHASE ALGORITHM FOR SOLVING A FLEET SIZE AND MIX VEHICLE ROUTING PROBLEM WITH TIME WINDOWS UNCERTAIN DEMANDS
Article Sidebar
เผยแพร่แล้ว:
เม.ย. 26, 2018
คำสำคัญ:
ความทนทาน ปัญหาการจัดเส้นทางเดินรถขนส่งแบบมีรถหลายขนาดภายใต้กรอบระยะเวลา ความต้องการไม่แน่นอน ขั้นตอนวิธีเชิงพันธุกรรมแบบปรับปรุง ขั้นตอนวิธีการค้นหาแบบแทรก
Main Article Content
บทคัดย่อ
งานวิจัยนี้มุ่งเน้นการศึกษาปัญหาใหม่ซึ่งเป็นปัญหาเฉพาะของปัญหาการจัดเส้นทางเดินรถขนส่งแบบมีรถหลายขนาดแบบทั่วไป โดยเพิ่มขอบเขตของข้อจำกัดด้านกรอบระยะเวลา และความต้องการของลูกค้าเป็นแบบไม่แน่นอน โดยขั้นตอนวิธีที่นำเสนอเพื่อใช้ในการแก้ปัญหา คือ ขั้นตอนวิธีแบบสามเฟส โดยเทคนิคหลักประกอบด้วย ขั้นตอนวิธีเชิงพันธุกรรมแบบปรับปรุง ขั้นตอนวิธีแบบสองขั้นโดยประยุกต์ใช้การสุ่มเพื่อทำการรวมและแยกเส้นทาง และขั้นตอนการตัดสินใจเพื่อหาคำตอบเชิงทนทานบนพื้นฐานของสถานการณ์ที่เลวร้ายที่สุด ทั้งนี้สมรรถนะของผลเฉลยเชิงทนทานใช้การประเมินโดยตัวชี้วัด คือ ต้นทุนเพิ่มเติม และ ความต้องการที่แท้จริง นอกจากนี้ผลเฉลยเชิงกำหนดที่ได้จากการแก้ปัญหาด้วยวิธีการที่นำเสนอ ได้นำไปเปรียบเทียบกับผลลัพธ์ของนักวิจัยท่านอื่นซึ่งชี้ให้เห็นความมีประสิทธิภาพของขั้นตอนวิธีที่นำเสนอ
Article Details
ประเภทบทความ
บทความวิจัย
เอกสารอ้างอิง
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.
