Новый подход в решении проблемы незапланированного изменения маршрута транспорта во время доставки
Аннотация
Целью данной работы является описание нового подхода к решению проблемы нарушения маршрутизации транспортных средств (ПНМТС), который имеет дело с нарушениями, возникающими внезапно при выполнении первоначального плана. Затем в статье обсуждаются дальнейшие проблемы, связанные с поломкой транспортного средства, которые являются наиболее распространенной проблемой, возникающей при доставке товаров и услуг клиентам. Чтобы справиться с этим, нам нужно разработать новые планы маршрутизации, уменьшающие негативное воздействие, и решение должно быть найдено быстро, чтобы снизить ежегодные затраты. Алгоритм поиска с запретами выбирается для решения этих ПНМТС и оценивается с помощью других мета-эвристик, таких как муравьиная оптимизация и генетические алгоритмы. Основной вклад этой статьи заключается в определении комбинации метаэвристик, которая дает новые наиболее известные решения по эталонным задачам VRP. Были проведены численные тесты по набору соответствующих эталонных задач и представлены вычислительные результаты экспериментов с использованием других метаэвристических методов.
Литература
[2] Dantzig G.B., Ramser J.H. The Truck Dispatching Problem. Management Science. 1959; 6(1):80-91. (In Eng.) DOI: https://doi.org/10.1287/mnsc.6.1.80
[3] Laporte G. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research. 1992; 59(3):345-358. (In Eng.) DOI: https://doi.org/10.1016/0377-2217(92)90192-C
[4] Li J.-Q., Mirchandani P.B., Borenstein D. A Lagrangian heuristic for the real-time vehicle rescheduling problem. Transportation Research Part E: Logistics and Transportation Review. 2009; 45(3):419-433. (In Eng.) DOI: https://doi.org/10.1016/j.tre.2008.09.002
[5] Snyder L.V., Scaparra M.P., Daskin M.S., Church R.L. Planning for Disruptions in Supply Chain Networks. Models, Methods, and Applications for Innovative Decision Making. TutORials in Operations Research. INFORMS; 2006. p. 234-257. (In Eng.) DOI: https://doi.org/10.1287/educ.1063.0025
[6] Nguyen K.T.P. Meta-heuristic Solution Methods for Rich Vehicle Routing Problems. CIRRELT, CIRRELT-2014-31. Montreal, Canada; 2014. Available at: https://www.cirrelt.ca/documentstravail/cirrelt-2014-31.pdf (accessed 18.07.2020). (In Eng.)
[7] Mehrjerdi Y.Z. Vehicle Routing Problem: Meta-heuristic Approaches. International Journal of Applied Operational Research. 2012; 2(3):55-68. Available at: http://ijorlu.liau.ac.ir/article-1-178-en.html (accessed 18.07.2020). (In Eng.)
[8] Dorigo M., Maniezzo V., Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996; 26(1):29-41. (In Eng.) DOI: https://doi.org/10.1109/3477.484436
[9] Mohammed M.A., Abd Ghani M.K., Hamed R.I., Mostafa S.A., Ahmad M.S., Ibrahim D.A. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science. 2017; 21:255-262. (In Eng.) DOI: https://doi.org/10.1016/j.jocs.2017.04.003
[10] Baker B.M., Ayechew M.A. A genetic algorithm for the vehicle routing problem. Computers and Operations Research. 2003; 30(5):787-800. (In Eng.) DOI: https://doi.org/10.1016/S0305-0548(02)00051-5
[11] Jia H., Li Y., Dong B., Ya H. An Improved Tabu Search Approach to Vehicle Routing Problem. Procedia - Social and Behavioral Sciences. 2013; 96:1208-1217. (In Eng.) DOI: https://doi.org/10.1016/j.sbspro.2013.08.138
[12] Cordeau J.-F., Maischberger M. A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research. 2012; 39(9):2033-2050. (In Eng.) DOI: https://doi.org/10.1016/j.cor.2011.09.021
[13] Qiu M., Fu Z., Eglese R., Tang Q. A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups. Computers & Operations Research. 2018; 100:102-116. (In Eng.) DOI: https://doi.org/10.1016/j.cor.2018.07.021
[14] Paramestha D.L., Ai T.J., Wigati S.S. Applying Multi-objective Particle Swarm Optimization for Solving Capacitated Vehicle Routing Problem with Load Balancing. In: Ane B., Cakravastia A., Diawati L. (ed.) Proceedings of the 18th Online World Conference on Soft Computing in Industrial Applications (WSC18). WSC 2014. Advances in Intelligent Systems and Computing. 2019; 864:194-204. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-00612-9_17
[15] Glover F. Tabu Search – Part 1. ORSA Journal on Computing. 1989; 1(3):135-206. (In Eng.) DOI: https://doi.org/10.1287/ijoc.1.3.190
[16] Barman S.E., Lindroth P., Strömberg A.-B. Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types. In: Migdalas A., Karakitsiou A. (ed.) Optimization, Control, and Applications in the Information Age. Springer Proceedings in Mathematics & Statistics. 2015; 130:113-138. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-18567-5_6
[17] Janes G., Perinic M., Jurkovic Z. An efficient genetic algorithm for job shop scheduling problems. Tehnički vjesnik. 2017; 24(4):1243-1247. (In Eng.) DOI: https://doi.org/10.17559/TV-20150527133957
[18] Uchoa E., Pecin D., Pessoa A., Poggi M., Vidal T., Subramanian A. New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research. 2017; 257(3):845-858. (In Eng.) DOI: https://doi.org/10.1016/j.ejor.2016.08.012
[19] Christofides N., Eilon S. An Algorithm for the Vehicle-dispatching Problem. Journal of the Operational Research Society. 1969; 20(3):309-318. (In Eng.) DOI: https://doi.org/10.1057/jors.1969.75
[20] Gamboa D., Rego C., Glover F. Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems. European Journal of Operational Research. 2005; 160(1):154-171. (In Eng.) DOI: https://doi.org/10.1016/j.ejor.2004.04.023
[21] Vanderbeck F. On Dantzig-Wolfe Decomposition in Integer Programming and Ways to Perform Branching in a Branch-And-Price Algorithm. Operations Research. 2000; 48(1):111-128. Available at: http://www.jstor.org/stable/222919 (accessed 18.07.2020). (In Eng.)
[22] Kitchenham B.A., Budgen D., Brereton P. Evidence-Based Software Engineering and Systematic Reviews. Chapman & Hall/CRC; 2015. (In Eng.)
[23] Hu X., Sun L., Liu L. A PAM approach to handling disruptions in real-time vehicle routing problems. Decision Support Systems. 2013; 54(3):1380-1393. (In Eng.) DOI: https://doi.org/10.1016/j.dss.2012.12.014
[24] Holland J.H. Genetic Algorithm. Scientific American. 1992; 267:66-72. (In Eng.) DOI: http://dx.doi.org/10.1038/scientificamerican0792-66
[25] Eglese R., Zambirinis S. Disruption management in vehicle routing and scheduling for road freight transport: a review. TOP. 2018; 26(1):1-17. (In Eng.) DOI: https://doi.org/10.1007/s11750-018-0469-4
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
