A New neuristic procedure for capacitated arc routing problems

Abstract

IV ÇOK ARAÇLI AYRIT ÇİZELGELEME PROBLEMLERİ İÇİN YENİ BİR SEZGİSEL ÇÖZÜM YÖNTEMİ Bu çalışmada çok araçlı ayrıt çizelgelemesi problemi tanıtılmakta, uygulama alanları ve hesaplama zorlukları incelendikten sonra, yeni bir bulgusal çözüm yöntemi sunulmaktadır. Ayrıca, bu problemin tipik bir uygulama alanı olan katı atık (çöp) araçlarının çizelgelenmesi konusunda yapılmış olan bir uygulama da anlatılmaktadır. Önerilen yeni bulgusal çözüm yöntemi, herhangi bir ayrıta belli bir aracın hizmet götürmesi halinde, bazı komşu ayrıtlara da aynı aracın hizmet götüreceği gibi bir temel varsayıma dayanmaktadır. Bu varsayım doğrultusunda bulgusal çözüm yöntemi öncelikli olarak tek bir araçtan hizmet alacak temel ayrıt çemberleri yaratmaktadır (Yani, bir temel ayrıt çemberindeki ayrıtların değişik araçlara paylaştınlamayacağı öngörülmektedir). Daha sonra, bu ayrıt kümeleri maliyet minimizasyonu ve araç kapasite kısıtları göz önüne alınarak birleştirilmektedir. Bu birleştirme sırasında en kısa yol problemi ve kapasite kısıtlı en küçük bağlayan ağaç problemi önemli alt problemler olarak ortaya çıkmakta ve çözülmektedir.

Ill A NEW HEURISTIC METHOD FOR THE CAPACITATED ARC ROUTING PROBLEMS This study presents an investigation of multi-vehicle arc routing problems including problem definition, application areas, computational difficulties and a new heuristic solution procedure. One of the popular application areas, which is the routing of the solid waste collection vehicles in large municipalities is discussed in detail and an application in this area is presented. The heuristic solution procedure presented is based on a major assumption such that if an arc is serviced by a vehicle, some of its neighboring arcs will also be serviced by the same vehicle. According to this assumption the heuristic procedure generates a set of neighboring arcs and it assumes that each arc in that set will be serviced by the same vehicle. Then, the procedure merges these sets, while giving consideration to cost minimization and capacity limitations, to determine the final tours. During the merging process a shortest path problem and a minimum cost capacitated spanning tree problem are generated and solved as major sub problems.