مساله ی مسیریابی روی کمان مبتنی بر همکاری با محدودیت زمان

الموضوعات :

محمد صادق شیری ¹ ( گروه ریاضی، دانشکده مهندسی و علوم پایه، واحد ارسنجان، دانشگاه آزاد اسلامی، ارسنجان، ایران )
سید مصطفی خرمی زاده ² ( گروه ریاضی، دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران )

تاريخ الإرسال : 09 الإثنين , جمادى الثانية, 1444 تاريخ التأكيد : 13 الخميس , ربيع الأول, 1445 تاريخ الإصدار : 15 الأحد , محرم, 1446

الکلمات المفتاحية: Overtime, Profit, Arc routing problem, Collaboration,

ملخص المقالة :

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

المصادر:

[1] M. Gansterer and R. F. Hartl, “Collaborative vehicle routing: a survey,” Eur. J. Oper. Res., vol. 268, no. 1, pp. 1–12, 2018.

[2] A. Aloui, R. Derrouiche, N. Hamani, and L. Delahoche, “Collaboration horizontale durable des reseaux de transport de marchandises: etat de l’art et perspectives,” in 13ème Conférence Internationale de Modélisation, Optimisation et Simulation (MOSIM’20), 2020.

[3] A. Muñoz-Villamizar, C. L. Quintero-Araújo, J. R. Montoya-Torres, and J. Faulin, “Short-and mid-term evaluation of the use of electric vehicles in urban freight transport collaborative networks: a case study,” Int. J. Logist. Res. Appl., vol. 22, no. 3, pp. 229–252, 2019.

[4] S. Ben Jouida, M. Guajardo, W. Klibi, and S. Krichen, “Profit maximizing coalitions with shared capacities in distribution networks,” Eur. J. Oper. Res., vol. 288, no. 2, pp. 480–495, 2021.

[5] S. Ben Jouida, S. Krichen, and W. Klibi, “Coalition-formation problem for sourcing contract design in supply networks,” Eur. J. Oper. Res., vol. 257, no. 2, pp. 539–558, 2017.

[6] C. Vanovermeire and K. Sörensen, “Measuring and rewarding flexibility in collaborative distribution, including two-partner coalitions,” Eur. J. Oper. Res., vol. 239, no. 1, pp. 157–165, 2014.

[7] E. Angelelli, V. Morandi, and M. G. Speranza, “Optimization models for fair horizontal collaboration in demand-responsive transportation,” arXiv Prepr. arXiv2105.04815, 2023.

[8] B. Dai and H. Chen, “Mathematical model and solution approach for carriers’ collaborative transportation planning in less than truckload transportation,” Int. J. Adv. Oper. Manag., vol. 4, no. 1–2, pp. 62–84, 2012.

[9] F. Cruijssen, O. Bräysy, W. Dullaert, H. Fleuren, and M. Salomon, “Joint route planning under varying market conditions,” Int. J. Phys. Distrib. Logist. Manag., 2007.

[10] Ö. Ergun, G. Kuyzu, and M. Savelsbergh, “Shipper collaboration,” Comput. Oper. Res., vol. 34, no. 6, pp. 1551–1560, 2007.

[11] A. A. Juan, J. Faulin, E. Pérez-Bernabeu, and N. Jozefowiez, “Horizontal cooperation in vehicle routing problems with backhauling and environmental criteria,” Procedia-Social Behav. Sci., vol. 111, pp. 1133–1141, 2014.

[12] M. J. Santos, S. Martins, P. Amorim, and B. Almada-Lobo, “A green lateral collaborative problem under different transportation strategies and profit allocation methods,” J. Clean. Prod., vol. 288, p. 125678, 2021.

[13] E. Fernández, D. Fontana, and M. G. Speranza, “On the Collaboration Uncapacitated Arc Routing Problem,” Comput. Oper. Res., vol. 67, pp. 120–131, 2016, doi: 10.1016/j.cor.2015.10.001.

[14] A. Aloui, N. Hamani, R. Derrouiche, and L. Delahoche, “Systematic literature review on collaborative sustainable transportation: overview, analysis and perspectives,” Transp. Res. Interdiscip. Perspect., vol. 9, p. 100291, 2021.

[15] Á. Corberán, R. Eglese, G. Hasle, I. Plana, and J. M. Sanchis, “Arc routing problems: A review of the past, present, and future,” Networks, vol. 77, no. 1, pp. 88–115, 2021.

[16] G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Manage. Sci., vol. 6, no. 1, pp. 80–91, 1959.

[17] M. N. Kritikos and G. Ioannou, “The balanced cargo vehicle routing problem with time windows,” Int. J. Prod. Econ., vol. 123, no. 1, pp. 42–51, 2010.

[18] S. Irnich, P. Toth, and D. Vigo, “Chapter 1: The family of vehicle routing problems,” in Vehicle Routing: Problems, Methods, and Applications, Second Edition, SIAM, 2014, pp. 1–33.

[19] S. Mancini, M. Gansterer, and R. F. Hartl, “The collaborative consistent vehicle routing problem with workload balance,” Eur. J. Oper. Res., vol. 293, no. 3, pp. 955–965, 2021.

[20] H. Larrain, L. C. Coelho, C. Archetti, and M. G. Speranza, “Exact solution methods for the multi-period vehicle routing problem with due dates,” Comput. Oper. Res., vol. 110, pp. 148–158, 2019.

[21] C. Malandraki and M. S. Daskin, “The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem,” Eur. J. Oper. Res., vol. 65, no. 2, pp. 218–234, 1993.

[22] C. Archetti, D. Feillet, A. Hertz, and M. G. Speranza, “The undirected capacitated arc routing problem with profits,” Comput. Oper. Res., vol. 37, no. 11, pp. 1860–1869, 2010.

[23] E. Fernández, M. Roca-Riu, and M. G. Speranza, “The shared customer collaboration vehicle routing problem,” Eur. J. Oper. Res., vol. 265, no. 3, pp. 1078–1093, 2018.

[24] B. Padmanabhan, N. Huynh, W. Ferrell, and V. Badyal, “Potential benefits of carrier collaboration in vehicle routing problem with pickup and delivery,” Transp. Lett., pp. 1–16, 2021.

[25] M. Khorramizadeh and M. S. Shiri, “Integer programming formulation and polyhedral results for windy collaborative arc routing problem,” Comput. Oper. Res., vol. 142, p. 105727, 2022.

[26] P. Vansteenwegen, W. Souffriau, and K. Sörensen, “Solving the mobile mapping van problem: A hybrid metaheuristic for capacitated arc routing with soft time windows,” Comput. Oper. Res., vol. 37, no. 11, pp. 1870–1876, 2010.

[27] T.-S. Chang and H.-M. Yen, “City-courier routing and scheduling problems,” Eur. J. Oper. Res., vol. 223, no. 2, pp. 489–498, 2012.

[28] S. Lannez, C. Artigues, J. Damay, and M. Gendreau, “A railroad maintenance problem solved with a cut and column generation matheuristic,” Networks, vol. 66, no. 1, pp. 40–56, 2015.

[29] G. Razmara, “Snow removal routing problems: Theory and applications.” Linköpings universitet, 2004.

[30] J. Fink, M. Loebl, and P. Pelikánová, “Arc-routing for winter road maintenance,” Discret. Optim., vol. 41, p. 100644, 2021.

[31] J. Aráoz, E. Fernández, and O. Meza, “Solving the prize-collecting rural postman problem,” Eur. J. Oper. Res., vol. 196, no. 3, pp. 886–896, 2009.

[32] A. Corberán and J. M. Sanchis, “A polyhedral approach to the rural postman problem,” Eur. J. Oper. Res., vol. 79, no. 1, pp. 95–114, 1994.

[33] N. Christofides, V. Campos, A. Corberán, and E. Mota, “An algorithm for the rural postman problem on a directed graph,” in Netflow at pisa, Springer, 1986, pp. 155–166.

[34] A. Hertz, G. Laporte, and P. N. Hugo, “Improvement procedures for the undirected rural postman problem,” INFORMS J. Comput., vol. 11, no. 1, pp. 53–62, 1999.

[35] J. de Armas, P. Keenan, A. A. Juan, and S. McGarraghy, “Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics,” Ann. Oper. Res., vol. 273, no. 1, pp. 135–162, 2019.