Multi-period line planning in public transportation

Abstract

Kentsel ulaşım sistemleri, gün içinde yüksek talep dalgalanmaları ile karşılaşmaktadır. talepteki hem zamansal hem de mekânsal değişikliklerle baş etmek için, hat planlama problemine çok dönemli yaklaşımı önerilmektedir. Eğer ilgili sistemin kaynakları da sınırlı ise, planlama ufku boyunca bir hattan diğerine dinamik bir kaynak aktarımının da göz önünde bulundurulmalıdır. Bu bağlamda, hat planlama problemini çok dönemli bir planlama ufku için kaynakların transferini de göz önünde bulundurarak maliyet odaklı bir yaklaşımla çözmek üzere bir matematiksel modelleme çerçevesi geliştirilmektedir. Hat planlama probleminin NP-zor doğası göz önüne alındığında, ilk olarak iyi bilinen yerel dallanma algoritmasına dayalı bir sezgisel yaklaşımı sunulmaktadır. Bilgisayısal sonuçlar için gerçek hayattan alınan toplu taşıma ağı verileri kullanıyoruz. Algoritmalarnın verimliliğini göstermek için kapsamlı bilgisayısal deneyler yapıyoruz. Yerel dallanma algoritmasının, ticari bir çözücüye kıyasla çözüm kalitesini ve hesaplama süresini önemli ölçüde iyileştirdiğini gösteriyoruz. Çok dönemli hat planlama problemimizin çözümü için çeşitli Benders ayrıştırma yaklaşımları da geliştiriyoruz. Geleneksel Benders ayrıştırması umut verici bir performans göstermediğinden, kısıt türetme yaklaşımı da kullanan mantık tabanlı Benders ayrıştırmasına başvuruyoruz. Önerilen mantık tabanlı Benders ayrıştırmanın yerel dallanma algoritmasından daha iyi bir performansa sahip olduğunu gösteriyoruz; mantık tabanlı Benders ayrıştırma, orta ölçekli ve büyük ölçekli problem örneklerinde iyi kalitede çözümler bulabiliyor. Son olarak, ana problem daha küçükken alt problemin daha büyük ve dolayısıyla çözülmesinin daha zor olduğu ikinci bir mantık tabanlı Benders ayrıştırmasını sunuyoruz. Çözülmesi daha zor olan alt problemi, maksimum akış problemi olarak yeniden formüle ederek çözüyoruz; bu ayrıştırma çok etkin bir çözüm yönteminin ortaya çıkmasını sağlar. Bu algoritmanın diğer tüm yaklaşımlardan daha iyi performansa sahip olduğunu yaptığımız bilgisayısal deneylerle gösterebiliyoruz.

Urban transportation systems deal with high fluctuations in demand over the day. To capture both temporal and spatial changes in transit demand, we propose a multi-period line planning approach. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modeling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. Given the NP-hard nature of the line planning problem, we first present a heuristic approach based on the generic local branching algorithm. We use real-life public transportation network data for our computational results. We conduct extensive computational experiments to demonstrate the efficiency of the algorithms. We show that the local branching algorithm significantly improves solution quality and computing time in comparison to the commercial solver. We also develop various Benders decomposition schemes to solve our multi-period line planning problem. As the traditional Benders decomposition does not show a promising performance, we resort to logic-based Benders decomposition which uses constraint propagation. We demonstrate that the proposed logic-based decomposition outperforms the local branching algorithm; it is able to find high-quality solutions or medium and large instances. Finally, we present a second logic-based Benders decomposition with a smaller master problem while the subproblem is larger and more difficult to solve. We solve this challenging subproblem by reformulating it as a maximum flow problem; this decomposition produces a very effective solution method. Through computational experiments, we show that this algorithm performs better than all other approaches.