Kar Yağışı Öncesinde Tuz Kamyonları için İkmalli Entegre Ağ Rotalama ve Çizelgeleme Problemi

Abstract

Timely salting of roads before the snowfall is an important preventive activity for improving traffic safety and avoiding traffic congestions. We study the problem of routing and scheduling of salt trucks on a city road network. The problem is motivated by the operational problem that the Istanbul Metropolitan Municipality face in case of a heavy snowfall, and thereby should be solved in a periodic manner.In this problem, the vehicle fleet consists of heterogeneous vehicles that differ in salt capacity and there are multiple salt replenishment points. At the beginning of the current planning horizon, given a set of salt needing roads with different urgency levels, the vehicles start from different points of the network (i.e., their final locations at the end of the former planning horizon) and should cover all salt needing roads with the objective of minimizing the total weighted completion time of salting operation of each service needing arc. Each service needing arc should be serviced by exactly one vehicle, however, can be traversed for deadheading by a vehicle as part of its route.Vehicles visit replenishment points when they run out of salt. We first develop a Mixed-Integer Programming model for the problem. Since the performance of the model degrades rapidly as the problem size increases, we propose a simulated annealing metaheuristic, which obtains an initial solution by a constructive heuristic in the first phase, and then improves the solution in the next phase. The efficiency of our solution approach is evaluated on randomly generated instances reflecting real life road networks.

Kar yağışı öncesinde ve sırasında yolların zamanında tuzlanması, trafik güvenliğini iyileştirmek ve trafik sıkışıklığını önlemek için önemli bir önleyici faaliyettir. Bu çalışmada, bir şehir yolu ağındaki tuz kamyonlarının rotalama ve çizelgeleme problemi ele alınmıştır. Ele alınan problem İstanbul Büyükşehir Belediyesinin yoğun kar yağışı durumlarında karşılaştığı bir operasyonel problemdir ve periyodik olarak çözülmelidir. Problemde, araç filosu tuz kapasitesi açısından heterojen araçlardan oluşmaktadır ve birden fazla tuz ikmal noktası bulunmaktadır. Hava şartları gerektirdiğinde, tuzlanması gereken yollar ve bu yollar için öncelik seviyeleri belirlenmektedir. Amaç, ağın farklı noktalarında konumlanmış olan araçların, tuzlanması gereken tüm yolları tuzlayacak şekilde ve yolların ağırlıklı tamamlanma süresini en küçükleyerek rotalanması ve çizelgelenmesidir. Tuza ihtiyacı olan her yol tek bir araç tarafından tuzlanmalıdır. Araçlar tuzlanması gereken bir yolu tuzlama yapmadan sadece geçiş yapmak amacıyla da kullanılabilir. Araçlar, tuzları bittiğinde tuz ikmal noktalarını ziyaret etmelidir. Problemin çözümü için ilk olarak bir karma tam sayılı programlama modeli geliştirilmiştir. Problem büyüklüğü arttıkça modelin performansının hızla düştüğü gözlemlenmiş ve iki aşamalı bir sezgisel yöntem geliştirilmiştir. Sezgiselin ilk aşamasında yapıcı algoritma ile olurlu bir başlangıç çözümü elde edilmektedir, ikinci aşamasında bulunan başlangıç çözümü bir komşuluk arama algoritması ile geliştirilmektedir. Çözüm yaklaşımımızın verimliliği, gerçek hayat yol ağlarını yansıtan rastgele oluşturulmuş örnekler üzerinde analiz edilmiştir.