مساله ی مسیریابی روی کمان مبتنی بر همکاری با محدودیت زمان
محورهای موضوعی : تحقیق در عملیات
محمد صادق شیری
1
,
سید مصطفی خرمی زاده
2
1 - گروه ریاضی، دانشکده مهندسی و علوم پایه، واحد ارسنجان، دانشگاه آزاد اسلامی، ارسنجان، ایران
2 - گروه ریاضی، دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
کلید واژه: Overtime, Profit, Arc routing problem, Collaboration,
چکیده مقاله :
در این مقاله مساله مسیریابی روی کمان مبتنی بر همکاری با پارامتر زمان مورد بررسی قرار گرفته که به صورت اضافه‌کاری برای حامل‌ها و خدمت‌دهی به مشتریان، با هدف بیشینه کردن سود ائتلاف مستقل از سود فردی هر حامل در نظر گرفته شده است. در مدل ارایه شده دو نوع مشتری به صورت ضروری و اشتراکی در نظر گرفته شده که خدمت‌دهی به هر دو سودآور است. خدمت‌دهی به مشتریان نوع اول الزامی و به مشتریان نوع دوم با توجه به میزان سود حاصله و محدودیت زمان صورت می‌گیرد. درکاربردهای واقعی، زمان ارایه فعالیت حامل‌ها محدود به زمان کاری مرسوم حامل‌ها و از پیش مشخص است که می‌توان به صورت قید سخت اعمال شود. در این مقاله، افزایش زمان فعالیت حامل‌ها در قالب اضافه‌کاری با در نظر گرفتن هزینه‌های مرتبط بررسی شده که منجر به افزایش تعداد مشتریان خدمت‌دهی شده و در نتیجه باعث سودآوری بیشتر حامل‌ها می‌شود. مساله به صورت یک مدل برنامه‌ریزی خطی صحیح فرمولبندی شده است و بر روی 118 نمونه از نمونه‌های مساله‌ی پستچی روستایی تست و نتایج آن گزارش شده است.
In this paper, the collaboration arc routing problem with the time parameter is investigated, which is considered as overtime for carriers and customer service, with the aim of maximizing coalition profits independent of the individual profits of each carrier. In the proposed model, two types of customers are considered as required and shared customers, and serving both is profitable. Service to the first type of customers is mandatory and to the second type of customers according to the amount of profit and time limit is optional. In actual applications, the activity time of the carriers is limited to the carriers' usual working time and can be strictly constrained. In this paper, increasing the activity time of carriers in the form of overtime is considered by considering the related costs, which leads to an increase in the number of customers served and thus makes carriers more profitable. The problem is formulated as an integer linear programming model and is tested on 118 instances of rural postman problem and its results are reported.
[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.