Проблемы с маршрутизацией транспортных средств возникают во многих практических ситуациях, включая доставку товаров клиентам (или например, организация переездов в Москве и МО), вывоз городских отходов на регулируемые свалки, разработку маршрутов для электромобилей с остановками на подзарядных станциях, перевозку людей с ограниченными возможностями, мобильность и ремонт оборудования в разных домах.
В литературе представлено несколько обзоров вариантов проблем, методов решения и реальных применений, таких как Bodin et al. (1983), Assad (1988), Ronen (1988), Osman (1993), Desroisiers et al. (1995), Cunha (2000), Breedam (2001), Bra¨ysy & Gendreau (2005a, 2005b), Parragh et al. (2008), Laporte (2009), Baldacci et al. (2010), Belfiore & Yoshizaki (2013) и Schneider et al. (2014). Большое количество материалов свидетельствует о том, что научное сообщество уже более 50 лет прилагает огромные усилия для решения этих проблем. Это связано не только с их практической значимостью, но и с трудностями, возникающими при их решении. Тем не менее, поскольку каждый изученный случай может иметь отличительные черты от того, что уже обсуждалось в литературе, новые вариации общей проблемы продолжают появляться и требуют дифференцированного лечения.
В этой статье мы рассмотрим вариант, который представляет ситуацию многих компаний, которые ежедневно поставляют большие количества товаров в очень плотные городские районы. Учитывая трудности в вождении и парковке, клиенты, находящиеся близко друг к другу, объединены в кластеры, и для каждого кластера используется одно парковочное место, предназначенное для обслуживания этих клиентов. Затем доставка осуществляется пешеходной бригадой из парковочного места. Относительно длительное время обслуживания в каждом кластере по сравнению со временем в пути транспортных средств оправдывает использование нескольких доставщиков, поскольку позволяет сократить время, необходимое одному доставщику для обслуживания кластера, и, следовательно, увеличивает количество клиентов, посещаемых в рабочее время. Предотвращение нарушения рабочего времени является основной целью таких компаний, учитывая ее прямое влияние на затраты на сверхурочные.
Ситуации, подобные описанной, распространены в бразильских компаниях по производству напитков и табачных изделий, для которых большое количество покупателей составляют мелкие и средние предприятия розничной торговли, расположенные в городских районах. В дополнение к традиционным решениям о маршруте и расписании, план маршрута должен выбирать размер экипажа в каждом транспортном средстве, так как время обслуживания зависит от числа нанятых доставщиков. Временные рамки для поставок часто присутствуют, поскольку они избегают конфликтов в критические часы (например, обеденное время в ресторанах) или с поставками от других поставщиков. Кроме того, из-за больших требований или ограничений, которые мешают некоторым клиентам посещать большие транспортные средства, часто необходимо, чтобы один или несколько транспортных средств совершили вторую поездку (поездку) со склада (склада) для обслуживания дополнительных клиентов. Следовательно, эту проблему можно назвать проблемой маршрутизации в нескольких поездках с временными окнами и множественными доставщиками (MTVRPTWMD).
Концепция маршрутов с несколькими поездками для каждого транспортного средства была впервые рассмотрена для VRP в рабочем документе Fleischmann (1990). Автор предлагает расширить экономическую эвристику Clark & Wright (1964) для генерации поездок и использовать эвристику для задачи упаковки бункеров для назначения поездок однородному автопарку. Как отмечается в Petch & Salhi (2004), возможность многократных поездок может иметь важное значение для тактического и стратегического планирования, позволяя экономить на всех транспортных расходах. Со времени введения этой концепции в нескольких работах рассматриваются эвристические подходы к решению, такие как поиск по табу (Taillard et al., 1996; Branda˜o & Mercer, 1997; Olivera & Viera, 2007; Alonso et al., 2008; Seixas & Mendes, 2013), генетические алгоритмы (Salhi & Petch, 2007) и точные алгоритмы (Azi et al., 2010).
Маршрутизация с несколькими доставщиками, в свою очередь, была введена в Ferreira & Pureza (2012) с вариантом Проблемы маршрутизации транспортных средств с несколькими доставщиками (VRPMD) и в Pureza et al. (2012) с проблемой маршрутизации транспортных средств с временными окнами и множественными доставщиками (VRPTWMD). Ferreira & Pureza представляют математическую модель для случая ограниченного парка идентичных транспортных средств, которая затем решается расширением эвристики экономии Кларка и Райта и алгоритмом поиска табу. Pureza et al. сформулировать задачу с неограниченным парком транспортных средств и предложить алгоритм оптимизации колонии муравьев и алгоритм поиска табу для решения модели. В обеих статьях, а также в изданиях Grancy & Reimann (2014), Alvarez Diaz & Munari (2016) и Munari & Morabito (2016) математические модели и подходы к решению мотивировались практической актуальностью проблемы; однако, никакие реальные случаи не обсуждаются и не решаются.
Наше исследование, с другой стороны, вдохновлено городскими операциями доставки производителя и дистрибьютора напитков, расположенного в штате Сан-Паулу, Бразилия. Доставка осуществляется несколькими доставщиками в каждом транспортном средстве (грузовике), и логистическая операция учитывает различные характеристики и дополнительные ограничения по сравнению с моделями предыдущих работ, такими как ограниченный гетерогенный парк, использование чартерных грузовиков, многократные поездки для одного и того же грузовик, разное количество доставщиков в каждой поездке, наличие опасных маршрутов, ограничения по срокам обращения типов грузовых автомобилей в центрах городов и несовместимость типов грузовых автомобилей и клиентов.
Операции по доставке в городских районах часто трудно осуществить из-за нескольких реальных ограничений. Рассмотрение нескольких доставщиков и нескольких поездок усложняет проблему, поэтому хорошо структурированные процедуры, способные обеспечить эффективные решения, представляют большой интерес для дистрибьюторов. Насколько нам известно, решение о количестве доставщиков не рассматривалось в современных вычислительных системах, предназначенных для поддержки решений о маршрутизации и планировании транспортных средств. Тем не менее, его практическая и теоретическая значимость подчеркивается в таксономии проблем маршрутизации, недавно предложенной в Braekers et al. (2015).
В дополнение к этой мотивации, в случае изучаемой компании, число доставщиков в каждом грузовике является фиксированным. Поэтому интересно проверить, может ли установка числа доставщиков на основе специфики каждой поездки принести выгоды, такие как снижение затрат, удовлетворение ранее нарушенных ограничений и увеличение количества кластеров спроса, посещенных в рабочие часы доставщиков. Последнее преимущество особенно актуально и напрямую связано с первым; в нашем исследовании мы видим, что даже при наличии нескольких доставщиков и нескольких поездок для удовлетворения ежедневных потребностей обычно требуется сверхурочная работа. Поскольку компания типична для сектора напитков, предложенные подходы к модели и решению могут быть полезны для других поставщиков, а также для компаний из других секторов с аналогичными операциями распределения. Помимо практической мотивации, проблемы маршрутизации транспортных средств с несколькими доставщиками остаются мало изученными, что означает, что его постоянное изучение может представлять вклад в совокупность знаний в области комбинаторной оптимизации и логистики распределения.
Использованные источники
[1] ALONSO F, ALVAREZ MJ & BEASLEY JE. 2007. A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. Journal of the Operational Research Society, 59: 963–976.
[2] ALVAREZ DIAZ AA & MUNARI P. 2016. Abordagens metaheur´ısticas para o problema de roteamento de ve´ıculos com janelas de tempo e mu´ ltiplos entregadores. Gesta˜ o e Produc¸a˜ o, 23: 279–293.
[3] ASSAD AA. 1988. Modeling and Implementation Issues in Vehicle Routing. In Vehicle Routing: Methods and Studies, B.L. Golden and A.A. Assad (eds.) North-Holland, Amsterdam, pp. 7–46.
[4] AZI N, GENDREAU M & POTVIN J-Y. 2010. An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 202: 756–763.
[5] BALDACCI R, TOTH P & VIGO P. 2010. Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operation Research, 175: 213–245.
[6] BELFIORE P & YOSHIZAKI HTY. 2013. Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Computers & Industrial Engineering, 63: 589–601.
[7] BODIN L, GOLDEN B, ASSAD A & BALL M. 1983. Special Issue – Routing and scheduling of vehicles and crews – the state of the art. Computers & Operations Research, 10.
[8] BRAEKERS K, RAMAEKERS K & NIEUWENHUYSE IV. 2015. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering.
[9] BRANDA˜ O J & MERCER A. 1997. A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Research, 100: 180–191.
[10] BRA¨ YSY O & GENDREAU M. 2005a. Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science, 39(1): 104–118.
[11] BRA¨ YSY O & GENDREAU M. 2005b. Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Science, 39: 119–139.
[12] BREEDAM AV. 2001. Comparing Descent Heuristic and Metaheuristics for the Vehicle Routing Problem. Computer & Operations Research, 28(4): 289–315.
[13] CLARKE G & WRIGHT WJ. 1964. Scheduling of Vehicle from a Central Depot to a Number of Delivery Points. Operations Research, 12: 568–581.
[14] CUNHA CB. 2000. Aspectos Pra´ticos da Aplicac¸a˜o de Modelos de Roteirizac¸a˜o de Ve´ıculos a Problemas Reais. Transportes, Rio de Janeiro, 8(2): 51–74.
[15] DESROISIERS J, DUMAS Y, SOLOMON MWP & SOUMIS F. 1995. Time constrained routing and scheduling. In: Network Routing, Handbooks in Operations Research and Management Science [edited by Ball MT, Magnanti L, Monma CL & Nemhauser GL.], North-Holland, Amsterdam, pp. 35– 139.
[16] FEO TA & RESENDE MGC. 1995. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6: 109–134.
[17] FERREIRA VO & PUREZA V. 2012. Some experiments with a savings heuristic and a tabu search approach for the vehicle routing problem with multiple deliverymen. Pesquisa Operacional, 32: 443– 463.
[18] FLEISCHMANN B. 1990. The vehicle routing problem with multiple use of vehicles. Working paper. Fachbereich Wirtschaftswissenschaften, Universita¨t Hamburg.
[19] GRANCY GS & REIMANN M. 2014a. Vehicle routing problems with time windows and multiple service workers: a systematic comparison between ACO and GRASP. Central European Journal of Operations Research.
[20] LAPORTE G. 2009. Fifty years of vehicle routing. Transportation Science, 43: 408–416.
MODELING AND SOLVING A RICH VEHICLE ROUTING
PROBLEM FOR THE DELIVERY OF GOODS IN URBAN AREAS
Jose Ferreira de Souza Neto; Vito´ria Pureza.
Received June 10, 2015 / Accepted October 25, 2016