بهینه سازی چند هدفه مسئله مسیر یابی و زمانبندی سبز وسایل نقلیه ناهمگون با عرضه و تقاضای احتمالی

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، گروه مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، مازندران، ایران

2 دانشیار، گروه مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، مازندران، ایران

3 استاد، گروه مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، مازندران، ایران

4 دانشیار، دانشکده مهندسی راه آهن، دانشگاه علم و صنعت ایران، تهران، ایران

10.22034/tri.2022.87030

چکیده

همواره یکی از مسائل مهم در مدیریت زنجیره تامین ، مسئله مسیر یابی و زمان بندی وسایل نقلیه بوده است که تاکنون بسیار مورد توجه محققان قرار گرفته شده است. در این مقاله سعی شده تا مسیریابی و زمانبندی بهینه برای یک سیستم حمل و نقل ناهمگون با عرضه و تقاضای تصادفی مشتریان و با در نظر گیری شرایط ترافیکی متنوع ، حداکثر زمان رانندگی مستمر رانندگان و محدودیت بازه زمانی تحویل تقاضای مشتریان و با رویکرد بهینه سازی ، مصرف انرژی و حداکثر سازی رضایتمندی مشتریان برای اولین بار ارائه گردد. بدوا" این مسئله در قالب یک مدل ریاضی خطی چند هدفه جدید ارائه و سپس با رویکرد ادغامی پیشنهادی که ترکیبی از روش های برنامه ریزی احتمالی مقید و برنامه ریزی آرمانی بوده با یک مسئله عددی حل گردیده و نتایج با تحلیل حساسیت مورد بررسی قرار گرفته و میزان تاثیر پارمترهای مسئله بر توابع هدف نشان داده شده است.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Multi-Objective Optimization for Green Heterogeneous Vehicle Routing and Scheduling Problem with Stochastic Demand and Supply

نویسندگان [English]

  • Yaser Zarook 1
  • Javad Rezaeian 2
  • Iraj Mahdavi 3
  • Masoud Yaghini 4
1 Ph.D. Student, Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Mazandaran, Iran.
2 Associate Professor, Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Mazandaran, Iran.
3 Professor, Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Mazandaran, Iran.
4 Associate Professor, School of Railway Engineering, Iran University of Science and Technology, Tehran, Iran.
چکیده [English]

One of the important issues in supply chain management, vehicle routing and scheduling problem has always been which has so far attracted considerable attention from researchers. This paper attempts to optimize routing and scheduling for a heterogeneous transportation system with considering stochastic supply and demand, various traffic conditions, maximum continuous driving time constraint and soft time window constraint of each customer delivery. The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. Also, the aim of this study is to minimize energy consumption and to maximize customer satisfaction, simultaneously. At first, this problem is presented in the form of a multi-objective linear programming model and then a novel integrated approach is proposed based on combination of chance constraint method and goal programming. Finally, the results of numerical example are analyzed with sensitivity analysis.
.

کلیدواژه‌ها [English]

  • Multi Objective Optimization
  • Green Routing and Scheduling
  • Heterogeneous Vehicles
  • Driver Fatigue
  • Service Time Window
-­B.-L. Garcia, J.-Y. Potvin, J.-M. Rousseau, (1994), “A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints”, Computers Ops. Res., 21, pp.1025-1033.

-­Bertsimas, D. J., (1992), “A vehicle routing problem with stochastic demand”, Oper. Res. 40(3), pp.574–585.

- Campbell, A. M. and B. W. Thomas, (2008), “Probabilistic traveling salesman problem with deadlines”, Transportation Science, 42 (1), pp.1 – 21.
- Clara M. Novoa and Robert Storer, (2009), “An approximate dynamic programming approach for the vehicle routing problem with stochastic demands”, European Journal of Operational Research, 196(2), pp.509–515.

- Cock Bastian and Alexander H. G. Rinnooy Kan., (1992), “The stochastic vehicle routing problem revisited”, European Journal of Operational Research, 56 (3), pp.407-412.

- Defra, (2012), “Guidelines to Defra/DECC’s GHG conversion factors for company reporting: methodology paper for emission factors”. Technical report, Department for Environment, Food and Rural Affairs, UK.
- Demir, E., Bekta¸s, T. e Laporte, G., (2014), “A review of recent research on green road freight transportation”, European Journal of Operational Research, v. pp.237,775-793.
- Demir, E., Bekta¸s, T. e Laporte, G., (2014), “The bi-objective pollution-routing problem”, European Journal of Operational Research, v. 232, n. 3, pp. 464 – 478.
- El Hachemi N, Gendreau M, Rousseau LM (2013), “A heuristic to solve the synchronized log-truck scheduling problem”, Computers & Operations Research ,40(3), pp.666–673.
- Forbes, M.A., Holt, J.N. & Watts, A. M. (1994), “An Exact Algorithm for Multiple Depot Bus Scheduling”. European Journal of Operational Research, vol. 72, pp.115- 124.
- Guo Y.NCheng JLuo SGong D.W., (2017),  “Robust Dynamic Multi-objective Vehicle Routing Optimization Method”. IEEE/ACM Trans Comput Biol Bioinform.
- Ioannou, G., M. Kritikos and G. Prastacos (2001), “A Greedy Look-Ahead Heuristic for the Vehicle Routing Problem with Time Windows”, Journal of the Operational Research Society, 52, pp.523−537.
- M. Dror, G. Laporte, and P. Trudeau., (1989), “Vehicle routing with stochastic demands: properties and solutions frameworks”, Transportation Science, 23, pp.166–176.
- Malandraki, C., (1989), “Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computational Experiments”, Ph.D. Dissertation, Northwestern University, Evanston, Illinois.
- Parragh S, Doerner K, and Hartl R., (2008), “A survey on pickup and delivery problems Part I: Transportation between customers and depot”, Journal für Betriebswirtschaft, 58, pp.21-51.
- R. Eglese, T. Bektaş, “Green vehicle routing In: Toth P., Vigo D. (Eds.), Vehicle Routing: Problems”, Methods, and Applications, 18, SIAM (2014), pp. 437-458.
- S.H. Zegordi and M.A. Beheshti nia., (2009), “A multi-population genetic algorithm for transportation scheduling”, Transportation Research Part E , 45 (6), pp.946-959.
- Sam Thangiah, (1995), “Vehicle routing with time windows using genetic algorithms. In Application Handbook of Genetic Algorithms”: CRC Press, Boca Raton, New Frontiers, Volume II, pp.253−277.
- Solomon, M.M., (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, 35, pp.254−265.
- Stewart, W. R. and B. L. Golden, (1983), “Stochastic Vehicle Routing: A Comprehensive Approach”, European J. Oper. Res. 14, pp.371-385.
- Xiao, Yiyong and Konak, Abdullah, (2016), “The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion”, Transportation Research Part E Logistics and Transportation Review, 88, pp.146-166.
-­­A. Franceschetti, D. Honhon, T. Van Woensel, T. Bektas, and G. Laporte, (2013), “The time-dependent pollution-routing problem”, Transportation Research Part B: Methodological, 56, 265–293.
-­Bae .H, and Moon. I., (2016), “Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles”, Appl. Math. Model, 40, pp.6536–6549.
-­Bae T.S., Hwang H.S., Cho G, S., & Goan M.J., (­2007), “Integrated GA-VRP solver for multi-depot system”, Computers & Industrial Engineering, 53, pp.233-240.
 
Burak EksiogluArif Volkan VuralArnold Reisman, (2009), ”­The vehicle routing problem: A taxonomic review”, Computers & Industrial Engineering, 57(4), pp.1472-1483.
-­C.A. Kontovas, (2014), “The green ship routing and scheduling problem (GSRSP)”,
A conceptual approach, Transportation Research Part D: Transport and Environment, 31, pp.61-69.
-­Christofides, N., Mingozzi, A., Toth, P. (1979), “The vehicle routing problem”, In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (Eds.), Combinatorial Optimization. Vol. 1. Wiley Interscience, pp. 315–338.
-Dantzig, G. and Ramser, J., (1959), "­The Truck Dispatching Problem", Management Science, 6, pp.80-91. 
-­E. Demir, T. Bektaş, G. Laporte, (2011), “A comparative analysis of several vehicle emission models for road freight transport”, Transportation Research Part D, 16, 
pp.347-357.
-­Gendreau, M, G Laporte and R Seguin (1996), “Stochastic vehicle routing”. European Journal of Operational Research, 88, pp.3–12.
-Golden, Assad, Levy, Gheysens, (1984), “The fleet size and mix vehicle routing problem”, Computers & Operations Research, 11, 
pp.49-66.

-­Golden, Bruce L., Raghavan, S., Wasil, Edward A., (2008), "The Vehicle Routing Problem", Latest Advances and New Challenges, springer.

-Imdat KaraBahar Yetis KaraM. Kadri Yetis., (2007), “Energy Minimizing Vehicle Routing Problem”, International Conference on Combinatorial Optimization and Applications, pp.62-71.
-­L. D. Bodin and B. L. Golden, (1981), “Classification in Vehicle Routing and Scheduling”, Networks, 11(2), pp.97-108.
-­Laporte, G., (1992), “The vehicle routing problem: An overview of exact and approximate algorithms”, European Journal of Operational Research, 59(3), pp.345-358.

-­Laporte, G.,Gendreau, M., Potvin, J. Y., Semet, F., (2000), “Classical and modern heuristics for the vehicle routing problem”, International Transactions in Operational Research,7(4-5), pp.285-300.

-­Nicola Secomandi and François Margot. (2009), “Re-optimization Approaches for the Vehicle-Routing Problem with Stochastic Demands”, Operations Research, 57(1), pp.214-230.
-­Parragh S, Doerner K, and Hartl R., (2008), “A survey on pickup and delivery problems Part II: Transportation between pickup and delivery locations”. Journal für Betriebswirtschaft, 58, pp.81-117.

-­Psaraftis H.N., (1995), “Dynamic vehicle routing: status and prospect”, Annals of Operations Research, 61, pp.143-164.

-Rodrigue, J-P, B. Slack and C. Comtois (2013), "Green Supply Chain Management", in J-P Rodrigue, T. Notteboom and J. Shaw (eds) The Sage Handbook of Transport Studies, London: Sage.

-­SOLOMON, M., (1983), “Vehicle Routing and Scheduling with Time Window Constraints: Models and Algorithms”, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania.

-­Somayeh Allahyari, Majid Salari, Daniele Vigo., (2015), “A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem”, European Journal of Operational Research, 242 (3), pp.756-768.
-­Toth, P and Vigo, D., (2002), “The Vehicle Routing Problem”, SIAM.
-­Toth, P and Vigo, D., (2014), “Vehicle Routing: Problems”, Methods, and Applications, Second Edition, SIAM.
-­Van Landeghem, H.R.G., (1988),
“A Bi-criteria Heuristic for the Vehicle Routing Problem with Time Windows”, European Journal of Operations Research, 36, pp.217−226.
-Van Woensel, T., Creten, R., & Vandaele, N., (2001), “Managing the environmental externalities of traffic logistic”s: The issue of emissions, Production and Operations Management, 10(2), pp. 207–223.
-­Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C., (2013), “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows”, Computers & Operations Research, 40(1), pp.475–489.
-­Y. Xiao, Q. Zhao, I. Kaku, Y. Xu., (2012), “Development of a fuel consumption optimization model for the capacitated vehicle routing problem”, Computers & Operations Research, 39, pp.1419-1431.
-­B.-L. Garcia, J.-Y. Potvin, J.-M. Rousseau, (1994), “A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints”, Computers Ops. Res., 21, pp.1025-1033.

-­Bertsimas, D. J., (1992), “A vehicle routing problem with stochastic demand”, Oper. Res. 40(3), pp.574–585.

- Campbell, A. M. and B. W. Thomas, (2008), “Probabilistic traveling salesman problem with deadlines”, Transportation Science, 42 (1), pp.1 – 21.
- Clara M. Novoa and Robert Storer, (2009), “An approximate dynamic programming approach for the vehicle routing problem with stochastic demands”, European Journal of Operational Research, 196(2), pp.509–515.

- Cock Bastian and Alexander H. G. Rinnooy Kan., (1992), “The stochastic vehicle routing problem revisited”, European Journal of Operational Research, 56 (3), pp.407-412.

- Defra, (2012), “Guidelines to Defra/DECC’s GHG conversion factors for company reporting: methodology paper for emission factors”. Technical report, Department for Environment, Food and Rural Affairs, UK.
- Demir, E., Bekta¸s, T. e Laporte, G., (2014), “A review of recent research on green road freight transportation”, European Journal of Operational Research, v. pp.237,775-793.
- Demir, E., Bekta¸s, T. e Laporte, G., (2014), “The bi-objective pollution-routing problem”, European Journal of Operational Research, v. 232, n. 3, pp. 464 – 478.
- El Hachemi N, Gendreau M, Rousseau LM (2013), “A heuristic to solve the synchronized log-truck scheduling problem”, Computers & Operations Research ,40(3), pp.666–673.
- Forbes, M.A., Holt, J.N. & Watts, A. M. (1994), “An Exact Algorithm for Multiple Depot Bus Scheduling”. European Journal of Operational Research, vol. 72, pp.115- 124.
- Guo Y.NCheng JLuo SGong D.W., (2017),  “Robust Dynamic Multi-objective Vehicle Routing Optimization Method”. IEEE/ACM Trans Comput Biol Bioinform.
- Ioannou, G., M. Kritikos and G. Prastacos (2001), “A Greedy Look-Ahead Heuristic for the Vehicle Routing Problem with Time Windows”, Journal of the Operational Research Society, 52, pp.523−537.
- M. Dror, G. Laporte, and P. Trudeau., (1989), “Vehicle routing with stochastic demands: properties and solutions frameworks”, Transportation Science, 23, pp.166–176.
- Malandraki, C., (1989), “Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computational Experiments”, Ph.D. Dissertation, Northwestern University, Evanston, Illinois.
- Parragh S, Doerner K, and Hartl R., (2008), “A survey on pickup and delivery problems Part I: Transportation between customers and depot”, Journal für Betriebswirtschaft, 58, pp.21-51.
- R. Eglese, T. Bektaş, “Green vehicle routing In: Toth P., Vigo D. (Eds.), Vehicle Routing: Problems”, Methods, and Applications, 18, SIAM (2014), pp. 437-458.
- S.H. Zegordi and M.A. Beheshti nia., (2009), “A multi-population genetic algorithm for transportation scheduling”, Transportation Research Part E , 45 (6), pp.946-959.
- Sam Thangiah, (1995), “Vehicle routing with time windows using genetic algorithms. In Application Handbook of Genetic Algorithms”: CRC Press, Boca Raton, New Frontiers, Volume II, pp.253−277.
- Solomon, M.M., (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, 35, pp.254−265.
- Stewart, W. R. and B. L. Golden, (1983), “Stochastic Vehicle Routing: A Comprehensive Approach”, European J. Oper. Res. 14, pp.371-385.
- Xiao, Yiyong and Konak, Abdullah, (2016), “The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion”, Transportation Research Part E Logistics and Transportation Review, 88, pp.146-166.
-­­A. Franceschetti, D. Honhon, T. Van Woensel, T. Bektas, and G. Laporte, (2013), “The time-dependent pollution-routing problem”, Transportation Research Part B: Methodological, 56, 265–293.
-­Bae .H, and Moon. I., (2016), “Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles”, Appl. Math. Model, 40, pp.6536–6549.
-­Bae T.S., Hwang H.S., Cho G, S., & Goan M.J., (­2007), “Integrated GA-VRP solver for multi-depot system”, Computers & Industrial Engineering, 53, pp.233-240.
 
Burak EksiogluArif Volkan VuralArnold Reisman, (2009), ”­The vehicle routing problem: A taxonomic review”, Computers & Industrial Engineering, 57(4), pp.1472-1483.
-­C.A. Kontovas, (2014), “The green ship routing and scheduling problem (GSRSP)”,
A conceptual approach, Transportation Research Part D: Transport and Environment, 31, pp.61-69.
-­Christofides, N., Mingozzi, A., Toth, P. (1979), “The vehicle routing problem”, In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (Eds.), Combinatorial Optimization. Vol. 1. Wiley Interscience, pp. 315–338.
-Dantzig, G. and Ramser, J., (1959), "­The Truck Dispatching Problem", Management Science, 6, pp.80-91. 
-­E. Demir, T. Bektaş, G. Laporte, (2011), “A comparative analysis of several vehicle emission models for road freight transport”, Transportation Research Part D, 16, 
pp.347-357.
-­Gendreau, M, G Laporte and R Seguin (1996), “Stochastic vehicle routing”. European Journal of Operational Research, 88, pp.3–12.
-Golden, Assad, Levy, Gheysens, (1984), “The fleet size and mix vehicle routing problem”, Computers & Operations Research, 11, 
pp.49-66.

-­Golden, Bruce L., Raghavan, S., Wasil, Edward A., (2008), "The Vehicle Routing Problem", Latest Advances and New Challenges, springer.

-Imdat KaraBahar Yetis KaraM. Kadri Yetis., (2007), “Energy Minimizing Vehicle Routing Problem”, International Conference on Combinatorial Optimization and Applications, pp.62-71.
-­L. D. Bodin and B. L. Golden, (1981), “Classification in Vehicle Routing and Scheduling”, Networks, 11(2), pp.97-108.
-­Laporte, G., (1992), “The vehicle routing problem: An overview of exact and approximate algorithms”, European Journal of Operational Research, 59(3), pp.345-358.

-­Laporte, G.,Gendreau, M., Potvin, J. Y., Semet, F., (2000), “Classical and modern heuristics for the vehicle routing problem”, International Transactions in Operational Research,7(4-5), pp.285-300.

-­Nicola Secomandi and François Margot. (2009), “Re-optimization Approaches for the Vehicle-Routing Problem with Stochastic Demands”, Operations Research, 57(1), pp.214-230.
-­Parragh S, Doerner K, and Hartl R., (2008), “A survey on pickup and delivery problems Part II: Transportation between pickup and delivery locations”. Journal für Betriebswirtschaft, 58, pp.81-117.

-­Psaraftis H.N., (1995), “Dynamic vehicle routing: status and prospect”, Annals of Operations Research, 61, pp.143-164.

-Rodrigue, J-P, B. Slack and C. Comtois (2013), "Green Supply Chain Management", in J-P Rodrigue, T. Notteboom and J. Shaw (eds) The Sage Handbook of Transport Studies, London: Sage.

-­SOLOMON, M., (1983), “Vehicle Routing and Scheduling with Time Window Constraints: Models and Algorithms”, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania.

-­Somayeh Allahyari, Majid Salari, Daniele Vigo., (2015), “A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem”, European Journal of Operational Research, 242 (3), pp.756-768.
-­Toth, P and Vigo, D., (2002), “The Vehicle Routing Problem”, SIAM.
-­Toth, P and Vigo, D., (2014), “Vehicle Routing: Problems”, Methods, and Applications, Second Edition, SIAM.
-­Van Landeghem, H.R.G., (1988),
“A Bi-criteria Heuristic for the Vehicle Routing Problem with Time Windows”, European Journal of Operations Research, 36, pp.217−226.
-Van Woensel, T., Creten, R., & Vandaele, N., (2001), “Managing the environmental externalities of traffic logistic”s: The issue of emissions, Production and Operations Management, 10(2), pp. 207–223.
-­Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C., (2013), “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows”, Computers & Operations Research, 40(1), pp.475–489.
-­Y. Xiao, Q. Zhao, I. Kaku, Y. Xu., (2012), “Development of a fuel consumption optimization model for the capacitated vehicle routing problem”, Computers & Operations Research, 39, pp.1419-1431.
-Yiyo Kuo, (2010) “Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem, Computers & Industrial Engineering, 59 (1), pp.157-165.