On the collaboration arc routing problem with time constraint
Subject Areas : تحقیق در عملیات
Mohammad Sadegh Shiri
1
*
,
seyed mostafa khorramizadeh
2
1 - Member of faculty, Department of Mathematics, Arsanjan Branch, Islamic Azad University, Arsanjan, Iran.
2 - گروه ریاضی، دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
Keywords: سود, اضافه کاری, مساله مسیریابی روی کمان, همکاری,
Abstract :
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.
مسالهی مسیریابی روی کمان مبتنی بر همکاری با محدودیت زمان
چکیده:
در این مقاله مسالهی مسیریابی روی کمان مبتنی بر همکاری با پارامتر زمان مورد بررسی قرار گرفته که به صورت اضافهکاری برای حاملها و خدمتدهی به مشتریان، با هدف بیشینه کردن سود ائتلاف مستقل از سود فردی هر حامل در نظر گرفته شده است. در مدل ارایه شده دو نوع مشتری به صورت ضروری و اشتراکی در نظر گرفته شده که خدمتدهی به هر دو سودآور است. خدمتدهی به مشتریان نوع اول الزامی و به مشتریان نوع دوم با توجه به میزان سود حاصله و محدودیت زمان صورت میگیرد. درکاربردهای واقعی، زمان ارایه فعالیت حاملها محدود به زمان کاری مرسوم حاملها و از پیش مشخص است که میتوان به صورت قید سخت اعمال شود. در این مقاله، افزایش زمان فعالیت حاملها در قالب اضافهکاری با در نظر گرفتن هزینههای مرتبط بررسی شده که منجر به افزایش تعداد مشتریان خدمتدهی شده و در نتیجه باعث سودآوری بیشتر حاملها میشود. مساله به صورت یک مدل برنامهریزی خطی صحیح فرمولبندی شده است و بر روی 118 نمونه از نمونههای مسالهی پستچی روستایی تست و نتایج آن گزارش شده است.
کلید واژهها: مسالهی مسیریابی روی کمان، همکاری، اضافهکاری، سود.
On the collaboration arc routing problem with time constraint
Abstract
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.
Keywords: Arc routing problem, Collaboration, Overtime, profit.
1 - مقدمه:
صنعت حمل و نقل با نارساییهایی روبرو است که میتواند بر تولیدات شرکتها، محیط، ازدحام شهری، مدیریت زنجیره تامین و رفاه کارگران تاثیر منفی بگذارد. هیچ راهحل واحدی به همه این مسایل نمیپردازد. این صنعت کاملا رقابتی است و شرکتها برای ادامه کار خود باید حداکثر سطح کارایی را در نظر بگیرند. رقابت شدید قیمتها را پایین میآورد و بنابراین حاشیهی سود به سطح بسیار پایینی کاهش مییابد. برای افزایش کارایی، این شرکتها میتوانند در جایی که عملیات تدارکات آنها به طور مشترک برنامهریزی شده باشد، با یکدیگر همکاری کنند[1].
استراتژیهای همکاری اخیرا با پیشرفتهای فنآوری اطلاعات و ارتباطات افزایش یافته است که شرکتها را قادر میسازد تا درخواستهای حمل و نقل خود را برای افزایش عملکرد و سود شبکه و در عین حال کاهش هزینههای عملیاتی به اشتراک بگذارند [2]. علاوه بر افزایش بهرهوری، همکاریها به اهداف زیستمحیطی نیز کمک شایانی میکند. واضح است که حمل و نقل، یکی از عوامل اصلی انتشار گاز دی اکسید کربن است. بنابراین، مقامات دولتی شرکتها را به همکاری دعوت و تشویق میکنند. هدف آنها نه تنها کاهش انتشار مواد مضر، بلکه کاهش آلودگی صوتی و تراکم جادههاست. بعلاوه، همکاریها در زمینه تدارکات برای افزایش سطح خدمات، به دست آوردن سهم بازار، افزایش ظرفیتها و کاهش تاثیرات منفی به کار گرفته شدهاند.
اخیرا، موضوع همکاری مورد توجه بسیاری از محققان قرار گرفته است و نشان داده شده است که چگونه این تکنیک میتواند باعث بهبود: (الف) عملکرد لجستیکی حاملها [2]، (ب) شبکهی توزیع کالا ([3] و [4])، و (ج) پایداری اقتصادی، زیست محیطی و اجتماعی ([5] و [6]) گردد.
استراتژیهای مورد استفاده در سیستم حمل و نقل مبتنی بر همکاری ممکن است شامل تبادل مشتریان بین شرکتهای حمل و نقل ([7] و [8])، به اشتراکگذاری ظرفیت وسایل نقلیه حاملهای مختلف با انبار مشابه [9]، تجمیع محمولههای حاملهای مختلف در مسیرهای تحویل [10]، یا ارایه بار در مسیرهای برگشت برای کاهش سفرهای خالی ([11] و [12]) باشد.
در مسالهی مسیریابی روی کمان بدون ظرفیت مبتنی بر همکاری که نوع همکاری در آن از نوع متمرکز است، تصمیمات مشترک توسط یک متخصص مرکزی که دارای اطلاعات کامل است گرفته میشود. هر حامل یک انبار و مجموعهای از مشتریان دارد. هر مشتری از طریق یک کمان مشخص میشود و خدمتدهی به آن باعث ایجاد درآمد میشود. در این طرح همکاری، هر حامل باید به بخشی از مشتریان خود خدمتدهی کند و قسمت باقیمانده را به اشتراک بگذارد تا احتمالا توسط سایر حاملها خدمتدهی شوند. فرض بر این است که هر حامل دارای یک وسیلهی نقلیهی بدون ظرفیت است. در این مساله، تضمین میشود که سود جمعآوری شده توسط هر حامل در طرح همکاری، از سودی که حامل به صورت مستقل آن را انجام میدهد، کمتر نباشد.
بسیاری از برنامههای کاربردی این مساله در شرکتهای خصوصی، مانند توزیع پست و بستهبندیهای کوچک و خدمات تاکسی به وجود میآیند که همکاری و رقابت باعث افزایش عملکرد آنها میشود [13]. در برنامههای کاربردی مبتنی بر سود، ایدهی اصلی همکاری، استفاده از ظرفیت همهی حاملها برای کسب سود بیشتر در مقایسه با حالتی است که به طور مستقل کار میکنند. علاوه بر این، در دنیای واقعی، زمان کار عادی برای حاملها، از جمله زمان سفر و همچنین زمان خدمات، محدود به مقادیر از پیش تعریفشده است که میتوانند از طریق محدودیتهای سخت در مدل تعبیه شوند. با این حال، آزادسازی محدودیتهای زمانی با افزایش زمان کاری شرکتهای حمل و نقل، ممکن است مزایایی مانند سودآوری بیشتر برای ائتلاف به همراه داشته باشد.
از آن جایی که اکثر مقالات، مساله زمان را به صورت پنجره زمانی در نظر میگیرند، بدین گونه که تقاضای هر مشتری میبایست در پنجره زمانی خاصی برآورده گردد و چون تاکنون هیچ مقالهای بحث زمان را در مساله همکاری میان حاملها تحت عنوان اضافهکاری بررسی نکرده است. سهم اصلی این مقاله، ارایه اضافهکاری حاملها در ساعات غیر از ساعات کاری حاملها در بحث همکاری میان حاملهاست. که در این مقاله، با بررسی دقیق و تعریف متغیرها و پارامترها و تبدیل کردن آن، هم در تابع هدف به شکل سود که هدف اصلی مساله میباشد و هم در محدودیتهای مساله، آورده است. بنابراین این مقاله یک مدل برنامهریزی جدید را برای مسالهی مسیریابی روی کمان بدون ظرفیت مبتنی بر همکاری را در نظر میگیرد که شامل اضافهکاری برای حاملها است. در واقع، این مدل اضافهکاری را در سود ائتلافها لحاظ میکند که به شرکتهای حمل و نقل این امکان را میدهد تا زمان کار بیشتری را صرف خدمتدهی به مشتریان کنند تا در صورتی که این کار بصرفه باشد، سود بیشتری کسب کنند.
نگارش این مقاله به صورت زیر است. در بخش 2 مروری بر بیشینه تحقیق داریم. در بخش 3 مساله را تعریف و مدل ارایه شده، توصیف و فرمولبندی شده است. برای فهم بیشتر مطلب، یک مثال ساده و تجزیه و تحلیل دادهها و نتایج عددی در بخش 4 آورده شده است و در بخش 5 نتیجهگیری ارایه شده است.
2 – بیشینهی تحقیق
دنیای تجارت امروز تحت تاثیر جهانی سازی بازارها، تغییر سریع نیازهای مشتریان و نگرانی در مورد پایداری است. در نتیجه، شرکتها به طور مداوم در حال جستجو برای استراتژیهای جدید برای بهبود عملکرد تدارکات خود و اطمینان از رقابت خود در بازار امروز، به خصوص در شبکهی توزیع کالاها، که یک مولفهی اصلی در تمام زنجیرههای تامین است، هستند. در این زمینه، همکاری لجستیکی به عنوان یکی از موثرترین ساز و کارها برای شرکتهایی که مایلند بهرهوری تدارکات خود را افزایش دهند و به اهداف خود برای پایداری اقتصادی، زیست محیطی و اجتماعی دست یابند، در نظر گرفته میشود. این رویکرد اساسا بر هماهنگی و تلفیق فرآیندهای بین بازیگران زنجیرهی تامین متمرکز است و میتواند بصورت همکاری افقی بین گروهی از ذینفعان از زنجیرههای تامین مختلفی که در یک سطح عمل میکنند (شرکتهای انجام دهنده فعالیتهای مشابه مانند شرکتهای حمل و نقل)، یا بصورت همکاری عمودی با در نظر گرفتن روابط سلسله مراتبی در یک زنجیره تامین (مانند تولیدکننده، توزیعکننده، شرکت حمل و نقل و خردهفروش) یا با ترکیبی از همکاری افقی و عمودی، که به عنوان همکاری جانبی شناخته می شود، باشد [14].
مسایل مسیریابی به دلیل تاثیر اقتصادی زیاد و چالشهای ریاضیاتی که در مطالعه و حل آنها وجود دارد، طی 60 سال گذشته مورد توجهی بسیاری از محققان قرار گرفته است. مسایل مسیریابی میتواند به مسایل مسیریابی روی گرهها، که در آن مشتریان میتوانند توسط گرههای شبکه نمایش داده شوند و مسایل مسیریابی روی کمان، که در آن خدمتدهی در کمانها یا یالهای شبکه انجام میشود، طبقهبندی شوند [15]. مسالهی مسيريابي وسيلهی نقليه، اولين بار توسط دانتزيگ و رامسر [16] در سال 1959 میلادی معرفی شد. تا به امروز، این مساله یکی از گستردهترین مسایل در زمینه بهینهسازی ترکیباتی است [17]. یک ناوگان از وسایل نقلیه و یک مجموعهای از درخواستهای حمل و نقل داده شده است، هدف تعیین مجموعهای از مسیرهای بهینه برای تحقق این درخواستها ضمن برآورده ساختن محدودیتهای خاص است [18] و [19]. مقالهی [20]، مسالهی مسیریابی چنددورهای وسیلهی نقلیه را با زمان سررسید بررسی میکند. یک حامل مجبور است برای بازدید از مجموعهای از مشتریان در یک افق برنامهریزی شده، توسط ناوگانی از وسایل نقلیهی ظرفیتدار، برنامهی توزیع را با هدف به حداقل رساندن هزینههای توزیع و هزینههای مربوط به جریمهی تاخیر در تحویل کالا تعیین کند.
اولین مساله مسیریابی روی کمان که با ماکسیمم کردن سود سروکار دارد، مساله ماکسیمم کردن سود پستچی چینی است که توسط مالاندراکی و داسکین [21] در سال 1993 معرفی شده جایی که نوع جهتدار آن مورد مطالعه قرار گرفته شده است. در مقاله [22]، مسالهی مسیریابی روی کمان را در نظر میگیرد که سود و تقاضا و زمان سفر به هر یال از یک گراف، که مشتریان را نشان میدهد، اختصاص یافته است. هدف، یافتن مجموعهای از مسیرها است که محدودیتهای طول مسیر و ظرفیت وسیلهی نقلیه را برآورده کرده و کل سود جمعآوری شده را به حداکثر برساند.
در زمینه بهینهسازی مسایل مسیریابی، تنها چند مقاله، مدلهایی را با هدف بهینهسازی مسیرهای شرکتهای درگیر در یک طرح همکاری پیشنهاد کردهاند. مقالهی [13]، به مطالعه یک مسالهی مسیریابی روی کمان بدون ظرفیت سودآور با چندین مبدا میپردازد، جایی که حاملها برای بهبود سود به دست آمده همکاری میکنند. یک کران پایین برای سود فردی هر حامل لحاظ میشود. این کران پایین ممکن است سود حامل را در صورت عدم همکاری نشان دهد. در مقالهی [4]، هر حامل مشتریانی دارد که از نظر جغرافیایی در یک منطقه مشخص پراکنده هستند حاملها به منظور ایجاد شبکهی بهینه و سود بیشتر با به اشتراک گذاری مرکز توزیع خود تشکیل ائتلاف داده و با هم همکاری میکنند. و یک الگوریتم برای یافتن ساختار ائتلاف و تخصیص هزینه برای هر یک ایجاد میکند. مقالهی [23]، یک مسالهی جدید مسیریابی وسیلهی نقلیه را معرفی میکند که در آن چندین حامل برای خدمتدهی به مشتریان تشکیل ائتلاف دادهاند به گونهای که بعضی از مشتریان تقاضاهایی دارند که بیش از یک حامل آن را انجام میدهند. در این مساله هدف کاهش هزینهی عملیات همپوشانی در چارچوب همکاری میان حاملها برای خدمتدهی به مشتریان اشتراکی است. در مقالهی [24]، مزایای همکاری میان شرکتهای با بار کمتر از بار کامیون، در برآورده کردن کارهای برداشت و تحویل مورد بررسی قرار داده شده است. از طرح همکاری متمرکز استفاده میکند جایی که یک مدیر مرکزی کارهایی که توسط حاملهای مختلف در یک استخر عمومی قرار داده شدهاند را به حاملهای ائتلاف به وسیلهی تعیین مسیرهای بهینه برای برداشت و تحویل تمام کارها با هدف مینیمم کردن هزینهی کل حمل و نقل اختصاص میدهد. در مقالهی [19]، یک مسالهی مسیریابی وسیلهی نقلیه مبتنی بر همکاری چند دورهای متمرکز را با ثبات زمان و خدمات و تعادل بار کار بررسی میکند، جایی که حاملها میتوانند مشتریانی را که باید به طور منظم خدمتدهی شوند مبادله کنند. حاملها فقط در صورت تضمین حداقل سهم بازار ممکن است مایل به همکاری باشند. در مقاله [25] به مسالهی مسیریابی روی کمان بدون ظرفیت مبتنی بر همکاری در گرافهای طوفانی میپردازد. یک فرمول برنامهنویسی عدد صحیح در مساله به کار رفته و یک تکنیک جدید برای ساخت تورهای شدنی مستقل ارایه شده است و برای بررسی چند وجهی مرتبط استفاده میشود. علاوه بر این، برخی از نامساویهای معتبر شناخته شده مانند نامساویهای پل_مسیر برای مساله تنظیم شده و ثابت شده است که القا کننده وجه هستند. در نهایت، یک الگوریتم شاخه و برش برای مساله توسعه داده شده و برخی جداول از نتایج عددی برای مقایسه و ارزیابی کارایی الگوریتم فراهم گردیده است. در مقاله [7]، حاملهایی را در نظر میگیرد که بر اساس همکاری افقی تشکیل یک ائتلاف به صورت سرویس تاکسی اشتراکی میدهند، مدلهای برنامهنویسی عدد صحیح مختلط را برای بهینهسازی مسیرهایشان ارایه داده و محدودیتهایی را با هدف کنترل تبادل حجم کاری هر حامل با سایر حاملها بکار میگیرد. این محدودیتها تبادل حجم کار را از نظر زمان سفر و خدمتدهی به مشتریان محدود کرده به گونهای که حجم کار هر حامل در زمان همکاری بسیار کمتر از زمان قبل از توافق همکاری بین حاملهاست.
با توجه به اهمیت زمان در مطالعه بر روی مسایل مسیریابی روی کمان، مروری کوتاه بر ادبیات مرتبط شده است. در مسایل مسیریابی روی کمان مبتنی بر زمان، خدمت دهی روی کمان باید در یک زمان مشخص تکمیل شود. اگر زمان خدمت دهی نتواند از این آستانه تجاوز کند، زمان سخت محسوب می شود و اگر زمان خدمت دهی با هزینه بیشتر مجاز به انجام دیرتر از این محدودیت زمانی باشد، به آن زمان نرم می گویند [15]. چندین مطالعه کاربردهای مبتنی بر زمان واقعی مسایل مسیریابی روی کمان را در نظر میگیرند، مانند نقشهبرداری سیار [26]، پیک شهری و مسالهی زمانبندی [27]، تعمیر و نگهداری راهآهن [28]، برفروبی [29]، تحویل روزنامه، تحویل بسته و تحویل مبلمان [30].
تا آنجا که میدانیم، هیچ مطالعهای در مورد مسایل مسیریابی روی کمان سودآور همراه با زمان سفر به صورت اضافهکاری در چارچوب همکاری بین حاملها انجام نشده است. برای پر کردن این شکاف، این مقاله یک مدل برای مسالهی مسیریابی روی کمان بدون ظرفیت مبتنی بر همکاری با اضافهکاری در بخش حمل و نقل را با وارد کردن بحث زمان در تابع هدف و قیود پیشنهاد میکند. در این مدل، زمان کاری که شامل زمان پیمایش و خدمتدهی است را برای حامل ها در تابع هدف به صورت اضافه کاری و در قیود، آزادسازی زمان از محدودیت سخت به محدودیت نرم مورد بررسی قرار داده شده است.
3 – تعریف مساله
فرمولبندی این مساله حالتی از مسالهی همکاری بین حامل های خدمت رسان، با اضافه شدن زمان کاری حاملها در خدمتدهی به مشتریان است. در این مساله، مجموعه ای از حاملها که هرکدام دارای یک انبار(مبدا)، یک وسیلهی نقلیه بدون محدودیت ظرفیت که دارای محدودیت زمان برای انجام سفر هستند در نظر گرفته شده است. مشتریان روی کمانهای گراف در نظر گرفته میشوند و وقتی که وسیلهی نقلیه کمان را پیمایش میکند، مشتریان خدمتدهی میشوند. بنابراین، اصطلاحات کمانهای دارای تقاضا و مشتریان به جای یکدیگر استفاده میشوند. حاملها تحت نظارت و هدایت یک تصمیم گیرندهی مرکزی که به عنوان شخص ثالث به صورت بیطرفانه عمل میکند به صورت زیر به یک توافق همکاری میرسند. هدف یافتن مسیر برای هر حامل با توجه به زمان کاری مرسوم و حداکثر زمان اضافهکاری در چارچوب توافق همکاری است به گونهای که سود ائتلاف حداکثر گردد. طرح همکاری که در این مقاله مورد بررسی قرار گرفته شده است به صورت زیر است. هر مشتری به یک حامل خاص اختصاص داده شده و مشتریان هر حامل به دو دسته تقسیم میشوند:
دسته اول مشتریانی هستند که به دلیل الزامات قراردادی یا سایر انواع ملاحظات استراتژیک، مانند روابط خاص، راحتی یا سودآوری بالا باید توسط خود حامل خدمتدهی شود و دسته دوم مشتریانی هستند که حامل مایل است به دلیل سودآوری کم یا سطح پایین اشتراک جغرافیایی با سایر مشتریان، آنها را با سایر حاملها به اشتراک بگذارد. مشتریان متعلق به دستهی اول "مشتریان ضروری" نامیده شده و مجموعه ضروری را تشکیل میدهند و مشتریان مربوط به دستهی دوم " مشتریان اشتراکی" نامیده شده و مجموعه اشتراکی را تشکیل میدهند. به تمام مشتریان ضروری و اشتراکی، مشتریان تقاضا میگویند. توجه داشته باشید که اگرچه هر مشتری به یک حامل اختصاص داده میشود، اما میتوان چندین مشتری را به یک حامل اختصاص داد. در حالی که مشتریان ضروری باید توسط حامل اختصاص داده شده به آنها خدمتدهی شود، مشتریان اشتراکی مجاز هستند توسط هر حاملی خدمتدهی شوند یا اصلا توسط هیچ حاملی خدمتدهی نشوند. این معمولا زمانی اتفاق میافتد که مشتری برای هیچ حاملی سودآور نبوده یا قبل از خدمتدهی به محدودیت زمانی رسیده باشد.
هر مشتری که خدمتدهی شود مقداری پول به حاملی که مشتری به آن اختصاص داشته است پرداخت میکند. چنانچه یک مشتری اشتراکی توسط حاملی بجز حاملی که مشتری به آن اختصاص داده شده است خدمتدهی گردد قسمتی از درآمد بدست آمده توسط حامل اختصاص یافته، به حاملی که واقعا خدمتدهی را انجام داده است پرداخت میگردد. مقدار پرداخت جانبی روی هر کمان توسط حامل اصلی که کمان به آن اختصاص یافته تعیین میگردد. هر مشتری حداکثر یکبار و فقط توسط یک حامل خدمتدهی میشود. بنابراین درآمد فقط در بار اولی که کمان پیموده میشود بدست میآید حتی اگر کمان چندین بار پیمایش شود. هر بار که یک کمان پیموده میشود صرفنظر ار اینکه کمان تقاضا هست یا نه، یک هزینه به حامل تحمیل میشود.
هر حامل توسط یک انبار، یک وسیلهی نقلیه و یک مسیر مشخص میشود و توجه میکنیم که مسیر یک حامل از انبار شروع و به همان انبار ختم میگردد.
به منظور بیان مساله، نمادهای به کار رفته را معرفی میکنیم. گراف مساله به صورت یک گراف جهتدار همبند قوی 
با مجموعه رئوس
و مجموعه کمان
نشان داده میشود. مجموعههای ضروری و اشتراکی مشتریان به ترتیب با
و
نشان داده میشوند و اجتماع آنها مجموعه کمانهای تقاضا
را تشکیل میدهد، یعنی
و
. هر بار که هر کمان
توسط وسیلهی نقلیهی یک حامل پیموده میشود، صرفنظر از اینکه تقاضای کمان برآورده شده یا نه، مقدار
به عنوان هزینهی پیمایش برای آن حامل در نظر گرفته میشود. هر کمان تقاضا
توسط وسیلهی نقلیهی اختصاص داده شدهی خود حامل یا وسیلهی نقلیهی حامل دیگری که آن کمان را پیمایش می کند خدمتدهی میشود. چنانچه توسط حامل اختصاص داده شده خدمتدهی شود، مقداری پول
توسط مشتری
به حامل پرداخت میگردد. علاوه بر این، اگر یک کمان اشتراکی
توسط حاملی متفاوت از حامل اختصاص داده شده خدمتدهی شود، بخشی از درآمد جمعآوریشده روی آن کمان، توسط حامل اختصاصیافته، به حاملی که به آن کمان خدمتدهی میکند پرداخت میگردد (پرداختهای جانبی
). فرض کنیم
مجموعه اندیس حاملها باشد که انبار آنها در رئوس گراف هستند و با نماد
نشان داده شدهاند آنگاه برای هر حامل
خواهیم داشت
. مجموعهی مشتریان ضروری و اشتراکی حامل
را به ترتیب با
و
نشان داده و بنابراین داریم: 
،
،
و
.
در این مساله، هر کمان ضروری
باید توسط حامل
خدمتدهی شود در حالیکه هر کمان اشتراکی
میتواند توسط حامل یا حامل
خدمتدهی گردد و یا توسط هیج حاملی خدمتدهی نشود. حامل، بابت خدمتدهی به مشتری
مقدار
پول دریافت میکند که این درآمد بابت خدمتدهی به مشتریان ضروری
و خدمتدهی به مشتریان اشتراکی
است حتی اگر توسط حامل خدمتدهی شده باشند. اگر حامل
به مشتری اشتراکی خدمتدهی کند آنگاه مقدار
پرداخت جانبی از طرف حامل دریافت میکند که این مقدار به سود حامل اضافه و از سود حامل کسر میشود.
3 – 1 فعالیت اضافهکاری
در فرمولبندیهای مساله موجود در ادبیات، هر حامل حداکثر برای مدت معین
در هر روز کار میکند که معمولا به عنوان یک محدودیت سخت در زمان کار حامل منظور میشود. زمان کاری هر حامل شامل زمان پیمایش هر کمان
و زمان خدمتدهی به مشتریان روی هر کمان دارای تقاضا
در مسیر آن حامل است. با این حال در دنیای واقعی، اگر برای حاملها بصرفه باشد که بتوانند هزینههای اضافی (مانند پرداخت کارکنان و هزینههای مربوط به وسیلهی نقلیهی حامل) را توجیه کنند، معمولا ساعاتی را بعنوان ساعت اضافهکاری در نظر میگیرند. بنابراین، پیشنهاد میکنیم که به شرکتهای حمل و نقل اجازه داده شود حداکثر
ساعت اضافهکاری را انجام دهند. به عبارت دیگر، برای زمان کاری هر حامل، یک محدودیت نرم () و یک محدودیت سخت (
) وجود دارد. هزینهی اضافهکاری برای حامل را با
، نشان میدهیم که در اینجا، مقدار پول پرداخت شده توسط حامل برای هر ساعت اضافهکاری را نشان میدهد. بنابراین، با وجود سود بالقوه، یک حامل در صورت انجام اضافهکاری، متحمل هزینه نیز میشود.
سود هر حامل، اختلاف بین کل درآمدها و کل هزینههاست که هزینهها شامل هزینهی پیمایش و هزینهی اضافهکاری است. هدف، یافتن یک مسیر برای هر حامل با توجه به طرح همکاری است، به طوری که با توجه به محدودیت زمان، سود کل ائتلاف حاملها بیشینه گردد. باید توجه کرد که همکاری بین حاملها زمانی معنادار است و حاملها تشکیل ائتلاف میدهند که سود فردی هر حامل، از سودی که هر حامل در حالت همکاری بدست میآورد، کمتر نباشد.
را سود فردی حامل (حداقل سود مورد انتظار برای حامل
) نامیده و این موضوع را به عنوان یک محدودیت در نظر گرفته و در محدودیتهای مساله بکار برده میشود.
3 – 2 مدل پیشنهادی
برای فرمولبندی مساله دو مجموعه متغیر تصمیمگیری به صورت زیر تعریف میکنیم تا کمانهایی را که هر حامل خدمتدهی و پیمایش میکند را شناسایی کند. متغیر دودویی
برابر با یک است اگر کمان توسط وسیلهی نقلیهی حامل خدمتدهی شود، در غیر اینصورت برابر با صفر است و متغیر صحیح نامنفی
تعداد دفعاتی است که وسیلهی نقلیهی حامل کمان
را پیمایش میکند.
برای هر حامل، درآمد کل برابر است با
که در آن عبارت اول، درآمد بدست آمده از خدمتدهی به کمانهای اختصاص یافته به حامل، عبارت دوم، درآمد بدست آمده از خدمتدهی به کمانهای اشتراکی اختصاص یافته به حامل توسط حامل و عبارت سوم، درآمد بدست آمده از خدمتدهی به کمانهای اشتراکی اختصاص یافته به حامل توسط حامل است.
در این مقاله، اساسا دو نوع هزینه که مربوط به هزینهی پیمایش و هزینهی اضافهکاری هست وجود دارد.
هزینهی پیمایش حاملها: هزینهی پیمایش مسیر حامل برابر است با: 
هزینهی اضافهکاری حاملها: اگر
و
به ترتیب زمان پیمایش و خدمتدهی به مشتریان روی کمان باشد، معادلهی زیر زمان کاری مسیر حامل را بر حسب ساعت، نشان میدهد.
با استفاده از معادلهی (1)، عبارت زیر برای جریمهی ساعت کاری بیشتر از (هزینه اضافه کاری) برای حامل پیشنهاد میشود.
به عبارت دیگر، اگر زمان کاری حامل از
به تغییر کند، یعنی
، آنگاه مقدار
به هزینهی حامل اضافه میشود.
سود کل ائتلاف برابر با مجموع سود فردی تمام حاملهاست. بنابراین سود کل هر حامل که اختلاف بین درآمد و هزینه است به صورت زیر بدست میآید
در نتیجه تابع هدف مساله که به حداکثر رساندن سود ائتلاف حاملها هست به صورت زیر مشخص میگردد
3 – 2 – 1 خطی کردن تابع هدف
معادلهی (2) غیرخطی است و در ابتدا برای حل آن با استفاده از نرمافزار
، بایستی آن را خطی نمود. برای خطی کردن معادلهی (2)، از تغییر متغیر زیر برای هر حامل استفاده میکنیم
که این کار با اضافه کردن قیود زیر به مدل معادل است
با استفاده از (3)، معادلهی (2) به صورت خطی زیر در میآید
3 – 3 مدل صحیح خطی مساله
این بخش مدل صحیح خطی پیشنهادی را توصیف میکند.
تابع هدف (5)، مجموع سود ائتلاف حاملها را بیشینه میکند. قید (6) و (7) قیود خطی شدهی مربوط به زمان را نشان میدهند که در آنها،
نشاندهندهی اضافهکاری حامل است که توسط کران بالای محدود میشود. قید (8) تضمین میکند که تعداد کمانهای ورودی با تعداد کمانهای خروجی در هر راس، با هم برابر هستند. قیود (9) و (10) حاملها را مجبور میکنند که مسیرهایشان را از انبار خودشان شروع کنند. در حالی که قید (9) مسیر حامل، مسیری است که شامل مجموعه مشتریان ضروری است، یعنی در صورتی که حامل مشتری ضروری داشته باشد از انبار خارج میشود. ولی مسیرهای موجود در قید (10)، هیچ مشتری ضروری ندارد و فقط شامل بعضی از مجموعه مشتریان اشتراکی هست، یعنی در صورتی که
، حامل به مشتری خدمتدهی نمیکند و بنابراین وسیلهی نقلیهی حامل از انبار خارج نمیشود، در غیر اینصورت حداقل یک بار برای خدمتدهی به مشتریان اشتراکی از انبار خارج میشود. همبندی مسیرهای هر حامل توسط قید (11) تضمین میشود. برای هر
که تشکیل زیرتور میدهند، اگر حامل بخواهد به یک کمان
، یعنی کمان با هر دو سر در
، خدمتدهی کند حتما میبایستی در یکی از رئوس از زیرتور خارج شود. توجه داشته باشید که حتی با وجود محدودیتهای (11)، ممکن است زیرتورهایی ایجاد شوند که هیچ کمانی از آنها خدمتدهی نشده باشد، از آنجایی که چنین زیرتورهایی هیچ سودی ندارند، در هیچ جواب بهینهای وجود نخواهند داشت. قیود (8) تا (11) مطمئن میکنند که پایان مسیر هر حامل در انبار خودش باشد. قید (12) هر حامل را مجبور میکند که به کمانهای ضروری خودش خدمتدهی کند. قید (13) تضمین میکند که کمانهای اشتراکی حداکثر توسط یک حامل خدمتدهی شوند. قید (14) مطمئن میسازد در صورتی که کمان توسط حامل خدمتدهی شود حداقل یک بار توسط آن حامل پیمایش شود. قید (15) تضمین میکند که سود هر حامل در حالت همکاری از سود آن حامل در حالت بدون همکاری که با
نشان داده شده است، کمتر نباشد و در قید (16) دامنهی متغیرها نشان داده شده است.
4 – نتایج عددی
در این بخش، ابتدا برای مشاهدهی تاثیر زمان و اضافهکاری بر مدل ارایه شده، یک مثال ساده را بررسی میکنیم و سپس آن را بر روی مجموعهای از دادههای عمومی که توسط گروههای مختلفی ([31], [32], [33], [34]) گردآوری شده و در [13] و [25] نیز مورد استفاده قرار گرفته شده است، بکار میبریم.
4 – 1 مثال ساده
مثال: در شکل1، یک گراف کوچک با چهار راس
و دو حامل که انبار آنها به ترتیب در رئوس 1 و 2 قرار دارند در نظر گرفته شده که کمانها به صورت زیر تقسیمبندی شدهاند:
روی هر کمان، یک چهارتایی مرتب برچسب زده شده که عدد اول مربوط به هزینه، عدد دوم مربوط به درآمد، عدد سوم مربوط به زمان پیمایش و عدد چهارم مربوط به زمان خدمتدهی کمان است. در این مثال، هزینهی اضافهکاری برای حاملها به ازای هر ساعت را 2 واحد (
) و پرداختهای جانبی مربوط به هر کمان اشتراکی را برابر با نصف درآمد روی همان کمان در نظر گرفتهایم (
). از آنجایی که ساعت کاری مرسوم کشور 8 ساعت
انجام میشود، به منظور تاثیر اضافهکاری بر سود حاملها سه سناریو را پیادهسازی میکنیم. مساله را در حالات مختلف کاری یعنی با قید سخت
، قید نرم با 2 ساعت اضافهکاری
و قید نرم با 4 ساعت اضافهکاری
در نظر میگیریم.
در جداول 1 و 2 از علامت "
" برای کمان صرفا پیمایش شونده، علامت "
" برای کمان خدمتدهی شده، مدت زمان مسیر
و سود
برای هر حامل در هر سناریو و در حالتهای همکاری و بدون همکاری استفاده میکنیم.
جداول 1 و 2 و شکل 2 نشان میدهند که چگونه اضافهکاری میتواند سود ائتلاف را بهبود دهد. همانگونه که در شکل 2 دیده میشود، سود ائتلاف در حالت بدون همکاری و با سناریو اضافهکاری از 6 به 10 و در قسمت مسیرها، در جدول 1، تعداد کمانهای خدمتدهی شده از 3 به 7 افزایش پیدا کرده است. در جدول 2، برای سناریو اول سود ائتلاف برابر با 12 است و فقط 6 کمان از 8 کمان مساله خدمتدهی شده است در حالی که برای سناریو دوم و سوم، هم سود و هم تعداد کمانهای خدمتدهی شده بیشتر شده است و همانطور که در شکل 2 برای حالت همکاری دیده میشود سود ائتلاف از 12 به 7/14 افزایش یافته است. نکتهی قابل توجه در مثال این است که زمان و اضافهکاری، تاثیر زیادی در افزایش سود ائتلاف در حالت همکاری نسبت به حالت بدون همکاری دارد.
شکل1 (تاثیر اضافهکاری): گراف مساله
حامل | بدون همکاری | ||||||||
TO =0 (دقیقه) | TO=120 (دقیقه) | TO=240 (دقیقه) | |||||||
مسیر | Tl | P | مسیر | Tl | P | مسیر | Tl | P | |
حامل 1 |
| 420 | 3 |
| 560 | 4 |
| 720 | 6 |
حامل 2 |
| 220 | 3 |
| 510 | 4 |
| 570 | 4 |
سود کل |
|
| 6 |
|
| 8 |
|
| 10 |
جدول 1 (تاثیر اضافهکاری بر سود کل): جواب بهینه درحالت غیرهمکاری وقتی که سود بیشینه میشود.
جدول 2 (تاثیر اضافهکاری بر سود کل): جواب بهینه درحالت همکاری وقتی که سود بیشینه میشود.
حامل | با همکاری | ||||||||
TO =0 (دقیقه) | TO=120 (دقیقه) | TO=240 (دقیقه) | |||||||
مسیر | Tl | P | مسیر | Tl | P | مسیر | Tl | P | |
حامل 1 |
| 450 | 6 |
| 580 | 7/5 |
| 450 | 10 |
حامل 2 |
| 420 | 6 |
| 420 | 8 |
| 610 | 7/4 |
سود کل |
|
| 12 |
|
| 7 |
|
| 7/14 |
شکل 2 (تاثیر اضافهکاری بر سود کل): سودکل برای سناریوهای اضافهکاری در حالتهای همکاری و بدون همکاری.
4 – 2 آزمایش روی دادههای عمومی
در این قسمت با استفاده از نمونههای مرجع و معیار که از گروههای مختلفی جمعآوری شده است، مساله را مورد بررسی و آزمایش قرار می دهیم. کد نویسی این مساله با استفاده از برنامهنویسی
و نرمافزار روی لپتاپ شخصی با
8 گیگابایت و
19/1 گیگاهرتز اجرا شده است. علاوه بر اطلاعات دادههای عمومی استفاده شده در مقالات مختلف، نیاز به اطلاعات دیگری مانند زمان (زمان پیمایش و خدمتدهی) و هزینهی اضافهکاری برای هر حامل است. برای این کار از ایده ارایه شده به شرح زیر برای تولید دادههای زمانی استفاده می کنیم:
1- طول هر کمان (بر حسب کیلومتر) برابر با یکدهم هزینهی آن کمان است
[35].
2- در فیزیک، سرعت متوسط وسیلهی نقلیه برابر با مسافت پیموده شده تقسیم بر مدت زمان پیمایش است. اگر سرعت وسیلهی نقلیه را 35 کیلومتر بر ساعت در نظر بگیریم، آنگاه زمان پیمایش کمان برحسب دقیقه برابر است با
.
3- تعداد مشتریان روی هر کمان دارای تقاضا را عددی در بازهی
در نظر میگیریم
.
4- زمان خدمتدهی به هر مشتری روی هر کمان دارای تقاضا برابر با 5 دقیقه در نظر میگیریم. بنابراین مجموع زمان پیمایش و خدمتدهی به مشتریان روی کمان
برابر است با
[35].
بعلاوه، هزینهی اضافهکاری برحسب ساعت برای هر حامل
را به صورت زیر و با استعلام از چندین شرکت پیمانکاری بزرگ محاسبه می کنیم. ابتدا سود حامل را در حالت بدون همکاری بدست میآوریم و آن را بر مدت زمان انجام مسیر حامل تقسیم میکنیم، سپس چهل درصد حاصل این تقسیم را بعنوان هزینهی اضافهکاری حامل منظور میکنیم.
جدول3، اطلاعات مربوط به نمونهها را بر اساس ویژگیها و اندازههای آنها گروهبندی میکند. این نمونهها با دو و سه حامل تولید میشوند. تعداد نمونههای هر گروه و محدودهی تعداد راس هر نمونه گروه به ترتیب در ستونهای دوم و سوم نشان داده شده است. ستونها
و
تعداد کمانهای ضروری و اشتراکی حاملهای یک، دو و سه را نشان میدهند. جدول 4، اطلاعات مربوط به مقادیر پارامترهای مورد استفاده و تعداد نمونههای آزمایش شده در هر مورد را خلاصه میکند. مجموعه نمونهها از 1416 نمونه تشکیل شده است.
نمونه گروه | تعداد نمونهها | تعداد راسها | تعداد کمانهای ضروری | تعداد کمانهای اشتراکی | ||||||||
2 - حامل | 3 - حامل | 2 - حامل | 3 - حامل | |||||||||
|
|
|
|
|
|
|
|
|
| |||
A | 2 | 90-102 | 48-50 | 23-34 | 46-90 | 11-22 | 17 | 48-50 | 23-35 | 41-46 | 12-23 | 17 |
D | 36 | 16-100 | 5-67 | 7-50 | 2-61 | 6-40 | 1-29 | 5-67 | 8-50 | 2-62 | 6-40 | 2-29 |
G | 36 | 16-100 | 0-29 | 0-32 | 0-23 | 0-24 | 0-14 | 1-29 | 1-33 | 1-24 | 1-24 | 0-14 |
P | 24 | 7-50 | 0-48 | 2-46 | 1-43 | 1-42 | 1-22 | 1-48 | 3-47 | 2-44 | 1-42 | 1-23 |
R | 20 | 20-50 | 10-57 | 5-56 | 6-53 | 3-45 | 3-28 | 10-58 | 6-56 | 6-54 | 3-45 | 4-45 |
جدول 3: اطلاعات نمونه دادهها برای آزمایش
تعداد حاملها | سناریو (اضافهکاری)(سود - بدون همکاری) | سناریو (اضافهکاری)(سود - با همکاری) | ||||
|
|
|
|
|
| |
2 | 118 | 118 | 118 | 118 | 118 | 118 |
3 | 118 | 118 | 118 | 118 | 118 | 118 |
جدول 4: تعداد نمونهها برای ترکیب پارامترها و سناریوها
در آزمایش زیر، سه سناریو شامل بدون اضافهکاری، با استفاده از 25 درصد زمان کار به عنوان اضافهکاری و 50 درصد از زمان کار به عنوان اضافهکاری در نظر گرفته شده است. در این آزمایش، سود روی نمونههای جدول 3 به ترتیب با دو و سه حامل در حالت بدون همکاری و با همکاری به حداکثر میرسد که نتایج به ترتیب در جداول 5 و 6 نشان داده شده است. در هر ردیف از جداول، میانگین سود به دست آمده برای نمونههای هر گروه با در نظر گرفتن سه سناریو به ترتیب در ستونهای
،
و
نشان داده شده است.
در ستون های مربوط به سناریوی دوم و سوم علاوه بر میانگین سود، درصد افزایش میانگین سود سناریوی دوم و سوم نسبت به سناریوی اول با توجه به رابطهی
محاسبه شده و در پرانتز نشان داده شده است. نتایج به دست آمده نشان دهنده تاثیر مثبت فعالیت اضافهکاری بر سود در حالت همکاری نسبت به حالت بدون همکاری است.
در بخش محاسباتی، متوسط زمان CPU مورد نیاز برای حل نمونههای کوچک، مانند گروههایی با کمتر از 36 راس، کمتر از 2 ثانیه، گروههایی با رئوس بین 36 تا 50 راس بین 2 تا 48 ثانیه و گروههایی با بیش از 50 راس نیاز به تلاش محاسباتی بیشتری داشتند و متوسط زمان CPU به 194ثانیه رسیدند.
جدول 5: تاثیر اضافهکاری روی سود حاملها بدون همکاری برای سناریوهای مختلف با دو و سه حامل.
نمونه گروه | سناریو 1 ( | سناریو 2 ( | سناریو 3 ( | |||
|
|
| ||||
سود با 2 حامل (دلار) | سود با 3 حامل (دلار) | سود با 2 حامل (درصد افزایش) | سود با 3 حامل (درصد افزایش) | سود با 2 حامل (درصد افزایش) | سود با 3 حامل (درصد افزایش) | |
گروه A | 1/17389 | 19/20472 | (40/27+)670/23952 | (96/28+)427/28816 | (60/31+)791/25423 | (31/40+)684/34299 |
گروه D | 5/2434 | 067/3359 | (82/30+)2/3519 | (81/21+)836/4295 | (32/40+)552/4079 | (24/35+)571/5186 |
گروه G | 914/162 | 356/288 | (75/26+)4/222 | (79/19+)481/359 | (82/30+)504/247 | (19/28+)573/401 |
گروه P | 321/224 | 249/371 | (42/24+)783/296 | (09/15+)21/437 | (28/39+)428/369 | (18/27+)803/509 |
گروه R | 23/152192 | 381/219687 | (55/13+)581/176041 | (89/12+)087/252196 | (70/21+)594/194367 | (88/27+)92/304618 |
میانگین | 613/34480 | 649/48835 | (50/15+)527/40806 | (65/14+)008/57221 | (20/23+)574/44897 | (23/29+)310/69003 |
نمونه گروه | سناریو 1 ( | سناریو 2 ( | سناریو 3 ( | |||
|
|
| ||||
سود با 2 حامل (دلار) | سود با 3 حامل (دلار) | سود با 2 حامل (درصد افزایش) | سود با 3 حامل (درصد افزایش) | سود با 2 حامل (درصد افزایش) | سود با 3 حامل (درصد افزایش) | |
گروه A | 5/34832 | 9/36203 | (21/9+)189/38040 | (56/21+)348/44009 | (88/10+)898/38623 | (38/33+)574/48288 |
گروه D | 086/4778 | 15/5223 | (39/24+)427/5943 | (62/16+)117/6091 | (70/33+)095/6388 | (53/26+)729/6608 |
گروه G | 375/287 | 038/406 | (64/12+)698/323 | (71/11+)6/453 | (47/28+)188/369 | (91/17+)746/478 |
گروه P | 729/383 | 761/525 | (26/26+)486/484 | (99/14+)573/604 | (03/44+)686/552 | (18/26+)381/663 |
گروه R | 467/214209 | 411/343898 | (69/28+)125/275660 | (31/8+)81/372477 | (24/41+)459/302559 | (71/11+)512/384155 |
میانگین | 231/50898 | 452/77251 | (92/25+)385/64090 | (68/9+)290/84727 | (94/36+)665/69698 | (96/13+)988/88038 |
جدول 6: تاثیر اضافهکاری روی سود حاملها با همکاری برای سناریوهای مختلف با دو و سه حامل.
5 – نتیجه گیری
در این مقاله، یک نوع مساله از نوع مسایل مسیریابی روی کمان بدون ظرفیت مبتنی بر همکاری را معرفی کردهایم. از آنجایی که مقالات دیگر مساله را روی گراف هایی متفاوت مانند گراف بدون جهت یا گراف طوفانی یا مشابه به این مساله روی گراف جهت دار ولی بدون در نظر گرفتن زمان، سود ائتلاف و حاملهای درگیر را در نظر میگیرند، ما در این مقاله، مسالهی مطرح شده را با اضافه کردن زمان به صورت اضافهکاری حاملها در مدل، فرمولبندی و سود حاملها و ائتلاف را در سناریوهای مختلف اضافهکاری به صورت همکاری و بدون همکاری با استفاده از برنامهریزی خطی عدد صحیح با متغیرهای دودویی و عدد صحیح و الگوریتم شاخه و کران حل کردیم. در این مقاله مشاهده شد که اضافهکاری میتواند در تابع هدف با سود ادغام شود و همواره شانس سودآوری در بین
حاملها و ائتلاف را افزایش دهد. در اینجا مجموعهای از نمونههای معیار تعمیم و برای ارزیابی مدل و الگوریتم استفاده شد و نتایج آزمایشهای محاسباتی ارایه و تجزیه و تحلیل شد.
برای کار در آینده، از آنجایی که در دنیای واقعی همکاری و ائتلاف برای حاملهای بیشتری در نظر گرفته میشود و روش دقیق نمیتواند مدل ارایه شده با تعداد حاملهای زیاد را حل کند، لذا روشهای فراابتکاری میتوانند مفید باشند. همچنین علاوه بر اضافه کردن زمان کاری حاملها، رضایتمندی مشتریان نیز میتواند معیار مناسبی برای ماندن حاملها در ائتلاف و بقای ائتلاف موثر باشد. بنابراین روشهای فراابتکاری و بررسی رضایتمندی مشتریان برای کارهای آتی پیشنهاد میگردند.
منابع
[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.